基于节点聚类系数的网络社区结构发现

朱 玲，余本国，冀庆斌

(1.中北大学 理学院，山西 太原 030051；2.海南医学院 医学信息学院，海南 海口 570216；3.山西大学 计算机与信息技术学院，山西 太原 030006)

0 引 言

近年来，网络在很多专业领域已经被广泛应用，网络拓扑可以用来描述自然界中的多种网络系统，例如社交网络、计算机科学网络、电力通信网络等.社区结构是网络的一个基本特征.网络的社区结构性质是指网络中存在着一些聚集程度较高且被称为“社区”的模块[1-2].寻找网络中社区的技术称为社区检测或社区发现，指仅使用网络拓扑中编码的信息来识别社区[3-4].现实网络中的社区可能是重叠或非重叠的[5-6]，本文重点关注非重叠社区检测.非重叠社区检测的结果称为划分或社区划分[5]，指的是将网络的所有节点划成k≥2个互不相交的节点组.

1 相关工作

1.1 社区检测算法

学者们在研究网络社区结构的同时还提出了很多有关社区检测的算法.2002年，Girvan和Vewman提出了GN算法[1]；2004年，Radicchi等在GN算法的基础上提出了边聚类系数算法[7]；2007年，Raghavan等运用了标签传播算法[8]；2004年，Newman提出了Newman快速算法[9]；Newman在提出模块度概念的同时给出了一种基于模块度矩阵的谱算法[2]，2008年，这种谱算法被Leicht和Newman应用到有向网络中[10]；2010年，Guo等[11]用共邻矩阵与增益函数作为网络社区结构划分的目标函数，进一步推导出基于增益矩阵、增量矩阵这两种矩阵的特征值以及特征向量的社区检测划分算法.2014年，Ma等[12]通过判断两个节点与其共享邻居节点能否构成三角形来判断这两个节点是否属于同一社区，并提出了一种基于三角形的重叠社区检测划分算法.

在聚类分析处理算法中谱聚类是一种新型划分算法[13].传统谱划分算法通常基于凸形样本，一旦出现样本不为凸形的特殊情况，划分算法就会陷入一个局部最优.谱聚类算法与传统谱划分算法相比有一个优点，即它可以在任意样本空间上划分，并且划分结果能收敛于全局最优[14].除此之外，谱聚类划分算法还具有严格的逻辑推理划分过程，目前已发展成为多种不同领域的研究热点.

1.2 谱方法

谱方法最早是由图划分算法引出的.目前，人们在计算机中的图划分领域已经做了深入研究.网络中的图划分是指将网络中的节点划分成组，最后使各组之间的连接边数达到最小.其中，由Fiedler提出且由Pothon等人推广的谱划分，通过Laplacian矩阵的特征值以及特征向量完成图划分的方法使用最广泛.

Laplacian矩阵是由图划分问题引出的，定义为L=D-A，其中A是邻接矩阵，D是度矩阵，也是一个对角矩阵，对角线元素Dii表示第i个节点的度.Laplacian矩阵有一个基本特点是图的块数与0特征值的个数相同.当图为连通图时，其Laplacian矩阵有一个0特征值，与其对应一个元素都为1的特征向量，该Laplacian矩阵的特征值是非负的.假设λ1<λ2<…<λn，对于一个连通图，λ2是该Laplacian矩阵最接近0的特征值，此时，对应的特征向量称为Fiedler向量.基于Laplacian矩阵的社区二分划分算法就是计算该Laplacian矩阵特征值对应的特征向量，并且寻找一个和它最接近的索引向量来对节点进行划分，将索引所对应的特征向量中的非负元素划分到一个社区，负元素划分到另一个社区.

1.3 识别社区间边的CCE规则

在网络G中，给定社区划分P和一条社区间边e(i,j)，di>2，dj>2，节点i,j所属的社区分别是C(i)，C(j)，通过聚类系数的变化识别边界社区划分的社区间边[15].下面给出识别社区间边的一种判定准则.

(1)

若CCE(e)ij=1，则e(i,j)是社区间边.

2 相似度矩阵的构造与社区划分

2.1 相似度矩阵的构造

相似度矩阵的构造是决定谱聚类算法聚类性能最关键的一步[16].网络中的社区是由连接松散的边界分隔开的子图，社区检测划分方法的核心是寻找社区边界[2].由文献[15]知，网络中社区的边界也是一个子图.使用上述CCE规则可以刻画边界子图中节点间的相似性，因此可以构造一个相似图进行社区划分.在该相似图中利用CCE规则引出相似度矩阵并找出社区边界，本文中将相似度矩阵称为网络密度矩阵，记为C.则有

(2)

对于网络密度矩阵中的每一个元素cij，若cij=1，说明节点i,j之间相似且互为邻居节点，此时，e(i,j)构成社区间边，否则，e(i,j)构成社区内边.

2.2 图分割和Laplacian矩阵

在一个无向无权网络中，先定义一个网络密度矩阵C，即式(2).图划分是将较相似的节点划分成一组，使各组之间的连边数目达到最小，将连接两组之间的边定义为H，其中节点i,j在不同的组中，如式(3)所示.

(3)

定义一个包含n个元素的索引向量si，表示为

(4)

可得

(5)

当节点在同一组时，δij=0；不在同一组时，δij=1.此时，H可表示为

(6)

(7)

在式(6)中，

(8)

此时，H可以写为

(9)

将式(9)改写成矩阵形式为

(10)

(11)

式中：βi是L的特征值；ui是特征值βi所对应的特征向量，使连接各组之间的边数H达到最小.L的特征值由小到大的排列为β1≤β2≤β3≤…≤βn，最小化H的值即选择适合的ai的值，将最小化H的任务赋予第二小特征值β2对应的特征向量u2，即Fiedler向量.由于si=±1，因此，si不能与特征向量ui做平行选择，通过选择si与ui尽可能平行，最终可以获得一个近似解

(12)

2.3 算法流程

Input：网络G(V,E)

Output:网络社区划分的最终结果

Step 1 利用式(2)，得到网络G(V,E)的一个网络密度矩阵C；

Step 2 计算网络G(V,E)的度矩阵D，D是一个对角矩阵，对角线元素Dii为第i个节点的外部度；

Step 3 计算Laplacian矩阵L=D-C；

Step 6 用不同的形状标记已知分组情况的社区1和社区2；

Step 7 出图；

Step 8 算法结束.

2.4 算法分析

本文研究了网络中节点聚类系数与社区结构之间的关系，并且提出了使用局部度量节点聚类系数对网络进行社区结构检测的划分算法.对于一些大型网络，采用局部度量节点聚类系数将网络进行有效划分.下面分析本文算法的时间复杂度.计算一个聚类系数的时间为O(d2)，执行一次CCE度量需要计算4个聚类系数，每执行一次CCE度量可以识别一条社区间边.假设有m条社区间边，则计算网络密度矩阵的时间复杂度为O(4d2m);计算度矩阵D和Laplacian矩阵的时间复杂度为O(n)，n为矩阵维数.Lanczos[17]算法可以计算出第二小特征值对应的特征向量，时间复杂度是O(n).因此，整个算法的时间复杂度是O(4d2m+2n)，由此可看出，网络中社区间边数越少，算法的时间复杂度越小.

3 实验结果

评价一个算法优良的标准之一是对其划分结果进行综合分析.一般情况下，不能概括性地评价一个算法优于另外一个算法，因为通常一个好的算法往往只在某些方面具有优势.针对一些模块结构已知的网络图，将能否把模块结构正确划分出来作为最终目标，并且与其他实验的划分结果相比得出最终结论；针对模块结构未知的图，通过与传统谱划分算法的划分结果相比较，以验证本文提出的基于Laplacian矩阵的谱算法在划分社区网络中的有效性.真实网络的基本信息如表1 所示.

表1 真实网络的基本信息Tab.1 The basic data of the real network information

3.1 Karate网络实验

Karate网络是社会网络分析领域的经典数据集之一.20世纪70年代，Zachary[18]对美国一所大学的空手道俱乐部进行了两年左右的研究，最终发现俱乐部中的34名成员彼此之间存在社会关系.由于该俱乐部的现任校长和主管之间有了冲突，因此，该俱乐部被划分成相对较小的两部分，这两部分分别将俱乐部现任校长以及主管作为核心.该网络中有34个节点和78条边，每两个节点之间存在一条边表示对应的两个成员之间是联系频繁的朋友关系.根据该网络数据进行实验，如图1 所示为使用本文方法划分的最终结果，该俱乐部成员的真实划分情况分别用长方形和菱形表示.由图1 可知，本文算法比Newman的GN算法[9]得到的结果更准确.

图1 Karate网络社团划分Fig.1 Community division of Karate network

为了更直观地分析实验划分结果，做了以下数据处理.如图2 所示，以0值为界反映了此俱乐部成员的划分情况.其中横坐标表示节点标号，纵坐标表示与第二小特征值β2=0.468 5相对应的特征向量中元素的取值结果.显然，0值以上有18个数据，0值以下有16个数据，因此，使用本文提出的网络社区划分算法得到的划分结果与实际划分情况相符.

图2 Karate网络社团划分特征向量中元素的取值分布Fig.2 Value distribution of feature vector elements for community division of Karate network

3.2 Dolphin网络

Dolphin网络也是网络社区划分的一个经典数据集.Lusseau等对新西兰海湾中62只海豚种群的生活习性进行了实地考察.通过研究发现，当其中一只海豚离开后，该海豚种群就会被划分成两个相对较小的种群，由此他们构造了一个包含62个节点和159条边的社会网络.如果出现某两只海豚经常一起频繁活动的情况，那么网络中对应的两个节点之间就会存在一条边.如图3 所示为使用本文方法进行划分的最终结果，形状的区分表示网络的真实划分情况.由图3 可知，实验划分结果没有把标号是29，31，40的节点准确地划分到所属社区中，但与网络的真实划分结果相接近.因此，实验结果表明使用本文算法与文献[19]中使用模块度矩阵的谱算法得到的划分结果都相对准确，由此说明了本文所述算法的合理性.

图3 Dolphin网络社区划分Fig.3 Community division of Dolphin network

同上述实验，做以下数据处理.如图4 所示，横坐标表示节点标号，纵坐标表示与第二小特征值β2=0.173 0所对应的特征向量中元素的取值结果.以0值为界反映了Dolphin网络的划分情况.很明显，图中0值以上数据有41个，0值以下数据有21个.由此可见，使用本文算法可以将该网络划分成两个明显的社区.

图4 Dolphin网络社团划分特征向量中元素的取值分布Fig.4 Value distribution of feature vector elements for community division of Dolphin network

3.3 Blogs网络

Blogs网络包含1 222个节点和16 714条边.图5 所示为传统谱划分算法划分网络的节点分布图，以0值为界展示了Blogs网络的节点分组情况，其中，横坐标表示节点标号，纵坐标表示与第二小特征值β2=0.117 6相对应的特征向量中元素的取值情况.可以看出，有1 200个数据几乎分布在0值上，显然没有将0值两端的数据很好地区分开，因此，传统谱划分算法对Blogs网络的划分结果不能令人满意.

图5 传统谱划分算法节点分布图Fig.5 Node distribution of traditional spectral classification algorithm

图6 所示为用本文所述的基于Laplacian矩阵的谱算法对Blogs网络进行划分的节点分布图.对比图5，图6 中0值左右的数据能被明显地区分开，其中有453个数据分布在0值以上，624个数据分布在0值以下，145个数据分布在0值附近.与传统谱划分算法划分网络的结果相比，本文方法可以把Blogs网络划分成两个相对明显的社区.

图6 Laplacian矩阵节点分布图Fig.6 Node distribution of Laplacian matrix

4 结 论

本文研究了从微观角度定义的节点聚类系数与网络社区结构之间的关系，并且提出了使用局部度量节点聚类系数对网络进行社区结构检测的高效划分算法.通过在3个真实网络数据中的测试，验证了本文算法不仅能够将模块结构正确无误地划分出来，还能提高划分算法的时间效率.然而，对于一些存在大量星型模块结构的网络，多数节点的聚类系数为零，此时，CCE规则不适用，本文提出的算法很难在此类型网络中发现有意义的社区结构.此外，随着科技的发展，人类研究的网络规模也越来越大，到目前为止，在大规模的网络上进行社区结构检测仍是一个难题，如何将局部社区发现进一步应用于大规模网络局部结构分析等实际问题将是下一步研究工作的重点.