基于核心度和偏移量的社区检测算法

辛慧英，刘向阳

(河海大学 理学院，江苏 南京 211100)

0 引 言

在复杂网络中，社区可以表示具有相似性、共同特点或关系的共同体，它具有“社区内部节点之间连接比较紧密，与外部节点连接相对稀疏”的特点。对复杂网络进行社区检测可以清晰地认识到社区内部的结构及组织，明确网络社区结构，有助于获得更多网络未知区域的信息，在物理、生物、计算机科学等诸多领域应用广泛。

Girvan和Newman在2002年提出了社区检测第一算法：基于模块度优化的划分算法[1](GN),该算法奠定了社区检测研究领域的基石，但该算法需要多次计算节点之间的边介数，大大增加了计算复杂度。而后，相继提出的一些基于标签传播的社区检测算法，基于信息流动的算法[2-3]，基于优化块模型的算法[4-5]，基于动态随机游走的算法[6]以及基于网络拓扑结构的算法[7]都在社区检测中得到了广泛的应用。在一定意义上，社区检测就是某种的聚类，这两者的区别在于：社区检测算法中可能存在孤立点，而聚类一般假设任意对象都是互相连接的，只是相似度不同，数据集可以表示为一张完全连通图，如：层次，密度聚类等。但这两个过程非常相似，因此产生许多将聚类算法的思想应用于社区检测算法的例子。黄岚等[8]通过网络中节点的相似度来定义节点间的距离，将密度峰值聚类算法[9]应用于社区检测中；文献[10]引入箱线图来确定核心节点，将密度峰值聚类算法应用于重叠社区检测中；文献[11]应用启发式算法来划分社区的自然结构；郭玉全[12-13]等以两阶段盒子覆盖法为基础，进一步提出分形聚类检测方法[14-15]，核心思想是通过两阶段盒子覆盖法来完成分形聚类过程,并且在分形聚类过程中形成分形树，最后通过对分形树进行分割进而得到复杂网络的社区结构。上述算法虽然成功将聚类算法引入到社区检测中，但是却由此引入一些新的参数，并且每个参数的选择都需要大量的实验数据来获取，大大增加了算法的复杂度，通常只对一种或某几种特定网络的结果较好，无法适应性地对多种社区进行划分，算法性能存在不足。

针对不依赖于大量实验数据获得参数的方法，文中提出一种基于偏移量和核心度的社区检测算法。首先求出网络中节点之间的距离矩阵，然后给出核心度、偏移量、核心社区的概念，并求出节点的核心度，来确定社区核心和核心社区，最后对其余节点进行分派，进而确定社区划分结果。该方法的优点在于，首先不需要过多的参数，不需要多次计算节点之间的边介数，其次不仅可以给出社区划分，而且可以很好地确定核心社区。实验结果充分验证了该方法的高效性和稳定性。

1 算法思想

社区检测算法的一个基本假设是：社区内部节点的相似度比较高，社区间节点相似度比较低；也可以理解为:社区内部节点间的距离比较小，社区间节点的距离比较大。基于节点间的距离求出节点的核心度，基于核心度确定社区核心，假设：(1)社区核心的核心度比它周围邻居节点的核心度高；(2)社区核心比其他任意核心度更高节点的相对偏移量更大。该算法不需要重复大量的计算，只需要一次计算，即可得出复杂网络的社区划分。算法流程如图1所示。

图1 算法流程

2 社区检测算法

社区检测算法基于两种基本的思想，一种是凝聚算法(agglomerative methods)，这类算法是从一个个孤立的节点开始，计算任意两个节点的相似度，相似度高则这两个节点在同一个社区。另一种社区检测的思想是分裂算法(divisive methods)，原始的输入是一个完整的网络图，要做得就是基于节点之间边的某些特性来删除图中的一些边。要删除的边是基于Newman[16]提出的删除具有最大边介数的边。文中具体思路的灵感来自于此，并不是要去删除节点之间的边，但是在最初完整的网路中计算边介数作为每条边的权重，基于完整网络中每条边的权重，计算提出的加权邻接矩阵。

2.1 计算加权邻接矩阵

首先计算网络中每个节点的权重w，节点权重为从源点s到该节点最短路径的数目：

(1)将初始节点s的w值设为1；

(2)每个与s相邻的节点i的权重w也设为1；

(3)对于每一个与(2)中节点i相邻的节点j，有如下计算规则：

(a)若j的权重还未设置，令w(j)=w(i)；

(b)若w(j)已经存在，则令w(j)=w(i)+w(j)。

计算得到每个节点的权重之后，计算每条边的边介数，自底向上，对边界的节点：即与之直接相连的边数为1，那么设该边介数为1；对于一个节点有多条边与之直接相连，则边介数为w(i)/w(j)，其中i是上方的节点。对于上层节点：其与更高一层节点连接的边介数等于所有与之直接相邻的子边介数之和加1，(如果该节点只有一个与之直接相连的上层节点)，或等于所有与之直接相邻的子边介数之和加1乘1/n(如果该节点有n个直接与之相连的上层节点)。计算完所有边介数，将以此作为节点间边的权重，计算得出网络的加权邻接矩阵。

2.2 全局距离矩阵

全局距离矩阵用来描述任意节点之间的最短距离，应用广度优先搜索算法求出复杂网络中的边介数作为边的权值，基于边的权值得到复杂网络的加权邻接矩阵，计算得到任意节点间的最短路径和最短距离。全局距离矩阵的计算步骤如下：

(1) 基于加权邻接矩阵生成网络的无向图；

(2) 基于加权无向图，用函数计算任意两点的最短路径和最短距离；

(3) 由任意两点的最短距离构成网络的全局距离矩阵。

2.3 节点的核心度和偏移量

2014年Alex Rodriguez[9]在新聚类算法中提出了局部密度和“距离”的概念，基于此，文中提出将网络中节点的核心度以及偏移量应用于复杂网络的社区检测。核心度和偏移量定义了任意节点作为社区核心的程度。

采用高斯核函数计算核心度，这样计算不同的节点具有相同的核心度的概率更小。计算公式为：

(1)

其中，exp(.)为指数函数，dc为截断距离，是算法中的可变参数，实验时取网络中所有节点间距离的1%～2%，dij为网络中节点之间的距离。当计算得到核心度ci后，让核心度按从大到小的顺序进行排列，即{c1,c2,…,cm}。

节点的偏移量计算公式为：

(2)

即当xi的核心度最大时，δi表示网络中与xi距离最大的节点到xi之间的距离；否则，δi表示在所有核心度大于xi的节点中，与xi距离最小的那个节点到xi之间的距离。

2.4 社区检测

2.4.1 确定社区核心和核心社区

根据假设，社区核心为核心度比它周围邻居节点的核心度高且与任意其他核心度更高节点的偏移量相对更大的节点，由公式(1)和公式(2)，可以计算得出网络中节点的核心度和偏移量，从而确定社区核心。核心社区“C”为社区中距离社区核心的距离相对比较小的节点集，确定核心社区的计算公式为：

(3)

其中，dz是核心社区内节点距离社区核心的距离阈值，实验中取网络中所有节点间距离的50%～60%，dhi为网络中节点与社区核心的距离。

2.4.2 对其他节点的处理

将其余节点按照核心度大小依次归类到比它们核心度更大，节点之间相似性更大的节点所属的类别。对社区边界的节点，首先定义社区边界区域，即分配到该社区又与其他社区节点的距离小于截断距离的节点的集合，然后为每个社区找到其边界区域中平均核心度的最大值，并以这个核心度作为阈值来筛选节点，对不满足该阈值的节点，排除在该社区之外。至此，即可完成社区划分。

3 实验与分析

为了验证算法的有效性、可行性和稳定性，选取了数据集Karate、Dolphins、Football进行实验。

3.1 实验数据集描述

选取三个真实数据集进行实验，数据集中的节点之间有一定的社会关系，所以这三个数据集都具有已知的社区结构，分别为空手道数据集(Karate)、海豚数据集(Dolphins)、美国大学橄榄球数据集(Football)。Karate数据集是由34个节点和78条边组成，其中每个空手道俱乐部成员代表一个节点，如果两个节点之间存在边，则表示相对应的成员之间联系交往密切，俱乐部会长和俱乐部的教练由于一些个人原因，他们之间存在一些分歧，所以最终俱乐部成员们形成了两个小团体(俱乐部)。Dolphins数据集是由62个节点和159条边组成，每只生活在新西兰Doubtful Sound海峡的宽吻海豚代表一个节点，如果两个节点之间存在边，那么代表对应的两只海豚有非常多的交流，经过很长一段时间的跟踪观察及记录，发现可以将这些海豚分为两个社区，但是更仔细观察分类，它们可以被分为5个社区。Football数据集是由115个节点和609条边组成，每支参加2000年美国大学秋季学期橄榄球赛的球队代表一个节点，如果两支球队曾经有过一场比赛，则表示两个节点之间存在边。这些球队隶属于12个不同的球会，且在球会内部进行的比赛比较多。

3.2 实验结果和分析

将文中算法在三个真实数据集上进行实验，图2～图5为文中算法在Karate、Dolphins数据集上的划分结果以及带有核心社区的社区划分结果，此时都取dz为网络中所有节点间距离的59%。图6为Dolphins数据集更仔细地被划分为5个社区的情况。图7为文中算法在Football数据集上的划分结果。

图2、图3表明，文中算法几乎完美地将Karate数据集的34个节点分为两个社区，只有一个节点(Karate数据集中的3号节点)被错误地分类，但该节点是在群体之间的边界上，所以可能是一个模糊的情况，是可以理解的。文中算法可以找出核心社区，在图3中，标签为3的节点和标签为4的节点分别为两个社区的核心社区，这些节点在网络中占据重要的地位，发现并准确定位这些节点将有很大的现实意义。

图2 Karate数据集社区划分结果

图3 Karate数据集带有核心社区的社区划分结果

图4～图6表明，文中算法可以准确将Dolphins数据集划分为2个社区，社区间有明显的界限，并且进一步划分，Dolphins数据集可以被划分为5个社区。文中算法可以找出核心社区，在图5中，标签为3的节点和标签为4的节点分别为两个社区的核心社区。

图4 Dolphins数据集社区划分结果

图5 Dolphins数据集带有核心社区的社区划分结果

图6 Dolphins数据集社区划分结果

图7 Football数据集社区划分结果

图7表明，文中算法将Football数据集中115个节点分为12个社区，图7中不同的节点标签分别代表不同的社区。可以看出，文中算法发现的社区数目与真实的社区数目相同，并且可视化效果良好，只有少数几个节点游离在社区之间。

4 结束语

提出一种基于节点核心度和偏移量进行社区检测的算法，在三个真实数据集上的实验结果表明，该算法简洁、高效、准确，算法运行良好，不仅可以准确地对数据集Karate、Dolphins、Football进行社区检测，而且可以找到核心社区。相比于一般的社区发现算法只能发现社区的一般整体划分，该算法可以检测出社区核心和核心社区，基于大多数网络具有拓扑结构的特性，核心社区的发现具有很好的现实意义，未来将尝试应用于更加复杂的网络。