BGLL社团划分案例

分析具有复杂相互作用的大量个体系统，复杂网络是常用的工具。大多数复杂网络呈现社团结构，即节点组织成紧密相连的群组，在同一个群组内的节点连接相对紧密，而不同群组间的节点连接相对稀疏。一个群组通常对应着一个功能单元，例如代谢网同一群组内的代谢物可能实现的是同一功能。因此复杂网络的社团划分可以大大简化复杂系统的功能分析，在药物功能分析、商品推荐、网络导航、万维网结构设计等有广泛应用。

数据描述：

network.txt为无向网络，没有自边或者重边,网络节点数115，节点从1开始编号。每一行为一个二元组，二元组的两个数表示两个节点间有无向边相连。

问题：

请将该网络划分为你认为合适的社团数目。

提交结果：

请在正文(结果汇总.pdf)中详细描述解答过程，包括解题思路，算法，及分析划分的结果，并提交以下2个附录文件：

1. 代码；

2. 网络的划分结果,用Community_Detection.csv命名，格式如下：

(节点1 所属社团编号i)

(节点2 所属社团编号j)

社团编号从1开始

数据如下：

社团划分

1. 社团划分预备知识

一个图通常表示为G=(V,E)，其中V表示点集合，E表示边集合，通常我们用n表示图的节点数，m表示边数。一个图中，与一个点的相关联的边的数量称为该点的度。对于一个图，图中所有点的度的和恰好等于边数的两倍。图通常用邻接矩阵A表示，邻接矩阵的(i,j)位置元素是1表示点i到点j右边，0表示无边。

本文中我们会用到随机图的概念，所谓随机图，就是指一个图中任何两个点之间连边的概率相等。首先确定n个点，然后以固定概率p去给图中的一对顶点连边，就形成了一个随机图。在研究中,随机图通常用来作为一个空模型来与实际网络进行比较，从而得出一些性质结论。

研究社团的划分，一个需要解决的问题是，如何来衡量一个社团的划分的好坏？一个比较简单直观的原则是使得社区内部的边尽可能地多，社区之间的边间可能地少。另外一个稍微复杂点但是更为常用的度量是Newman等人提出的模块度(modularity)的概念，基本的想法是这样的：我们假设在随机图中是不存在这种社团结构的，将实际网络跟其相应的随机网络进行比较，如果一个网络跟随机网络之间的差异越大，表示社团结构越明显。这样，我们对划分后的每一个子网络计算一个“密度”，然后计算该子网络随机情况下的“密度”，这两个“密度”存在一个差值，表示了该子网络偏离随机情况的一种程度，并且这个值越大表示这个子网络相对随机网络越稠密。一个网络中包含的所有子网络的这个差值加到一起的和就是这个复杂网络的模块度，数学公式表示如下：

其中Aij表示图的邻接矩阵，ki 表示点i 的度，m是图的边数，ki*kj/2m表示点 i 和点 j之间边的期望。进一步将模块度可以化为等式右边的形式，nc是社团的总个数，lc是社团c内的边数，dc是社团内的点的度数之和 (note: 社团内的每一个点可能跟本社团内部的点有边，也可能有跟其他社团点连边，故通常 dc> lc)

2. BGLL算法

BGLL算法就属于基于模块度优化中的聚合类算法，自底向上的不断聚合。

BGLL算法主要分为两步:

第一步：假设网络中有N个节点，首先我们给每个节点分配一个社区，所以初始阶段有多少个节点就有多少个社区。然后，对于网络中每个节点i,我们考虑他所有的邻居节点j,我们评估当把节点i从它所在的社区移动到其邻居j所在的社区时，模块度的增量变化，我们把节点i移动到使模块度增加最大的节点j所在的社区。如果所有计算出来的增益都不是正数，则将该节点仍处于原社区中。该过程对所有的节点重复并且按顺序应用，直到没有节点移动，则第一个过程停止，也就是任何一个节点的移动都不会导致模块度的增加。从该过程可以肯定，有些节点会被不止一次的考虑到。当然节点考虑顺序对算法最后的输出也是有影响的，但是最后对最后所划分的社区的模块度影响不大。但是节点的排序顺序是可以影响算法的运行时间的。

每一次节点移动一个孤立节点到其邻居所在的社团模块度增益为ΔQ：

其中∑in∑in是社区C内部的所有边的权重之和，∑tot∑tot是社区C中所有节点相关的边的权重之和。ki是发生在节点i上的所有边的权重之和。ki,in是节点i到社区C中的所有节点的边的权重和，m是网络中所有边的权重之和。

第二步：用第一部分所划分出来的社区当作节点组成一个新的网络。新节点之间的边的权重为两个新节点之间(其实是两个社区之间)原本的权重之和。处在同一个社区中的节点之间的边导致新网络中该新节点有自环的边。然后对于构建的新网络使用第一部分的方法进行迭代。当网络不再改变也就是出现了最大模块度的时候停止迭代。

Python数据分析及代码如下：

中心点，以及中心点包含的类点

点及对应的中心点

按照划分结果分类：

DBSCAN密度聚类案例

数据集描述：

DataSet.csv: 1024行，3列

每一行代表一个样本点，前两列表示样本点的两个特征，最后一列表示样本点所属类别。例如样本点(1.6, 0.8, 1)表示特征一值为1.6，特征二值为0.8，属于第1类。

问题：

数据集包含两类样本点，请用密度聚类正确划分数据集。

提交结果：

请在正文(结果汇总.pdf)中详细描述解答过程，包括解题思路，算法，及分析划分的结果，并提交以下3个附录文件：

1. 代码；

2. 数据集的划分结果,用DataSet_Cate.csv命名，格式如下：

(1.6, 0.8, c_pred), c_pred表示你的划分结果；

3. 数据集上的准确率，用Precision.csv命名，格式如下：

(DataSet, precision)

准确率计算公式：.

数据如下：

DBSCAN

1.相关介绍

基于密度的聚类方法的主要目标是寻找被低密度区域分离的高密度区域。与基于距离的聚类算法不同的是，基于距离的聚类算法的聚类结果是球状的簇，而基于密度的聚类算法可以发现任意形状的簇。

基于密度的聚类方法是从数据对象分布区域的密度着手的。如果给定类中的数据对象在给定的范围区域中，则数据对象的密度超过某一阈值就继续聚类。这种方法通过连接密度较大的区域，能够形成不同形状的簇，而且可以消除孤立点和噪声对聚类质量的影响，以及发现任意形状的簇。基于密度的聚类方法中最具代表性的是DBSAN算法、OPTICS算法和DENCLUE算法。

2.DBSCAN

2.1算法描述

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一个出现得比较早（1996年），比较有代表性的基于密度的聚类算法。算法的主要目标是相比基于划分的聚类方法和层次聚类方法，需要更少的领域知识来确定输入参数；发现任意形状的聚簇；在大规模数据库上更好的效率。DBSCAN能够将足够高密度的区域划分成簇，并能在具有噪声的空间数据库中发现任意形状的簇。

2.2基本概念

直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

当邻域半径R内的点的个数大于最少点数目minpoints时，就是密集。

邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

如果P为核心点，Q在P的R邻域内，那么称P到Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果P到Q密度直达，那么Q到P不一定密度直达。

如果存在核心点P2，P3，……，Pn，且P1到P2密度直达，P2到P3密度直达，……，P(n-1)到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具有对称性。

如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。

如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

2.3 算法的流程

DBSCAN的算法步骤分成两步。

a)寻找核心点形成临时聚类簇。扫描全部样本点，如果某个样本点R半径范围内点数目>=MinPoints，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇。

b)合并临时聚类簇得到聚类簇。对于每一个临时聚类簇，检查其中的点是否为核心点，如果是，将该点对应的临时聚类簇和当前临时聚类簇合并，得到新的临时聚类簇。重复此操作，直到当前临时聚类簇中的每一个点要么不在核心点列表，要么其密度直达的点都已经在该临时聚类簇，该临时聚类簇升级成为聚类簇。继续对剩余的临时聚类簇进行相同的合并操作，直到全部临时聚类簇被处理。

Python数据分析及代码如下：

原图的结果是

参数是eps = 0.1,min_samples=20，结果很差，没有完全分开。

划分后的结果，参数是（eps = 0.2,min_samples=20）最优。

蓝色表示离群点

准确率97.9%

可视化作图优化

原来的：

可视化作图优化：