基于局部信息的复杂网络社团结构发现算法＊

赵晓慧 ，刘 微 ，谢凤宏 ，赵凤霞

(1.辽宁师范大学 计算机与信息技术学院，辽宁 大连 116081；2.秦皇岛职业技术学院 信息工程系，河北 秦皇岛 066100)

近年来，复杂网络已经成为众多领域的关注对象。例如，万维网、人类社会网、生物技术网络和科学家合作关系网[1-4]等。复杂网络已成为当前最重要的多学科交叉研究领域之一[5]。社团结构是复杂网络的一个重要特性，它把网络中的点分到不同的“组”或“团”之中。其中社团内部节点连接比较稠密，但是社团之间节点连接则比较稀疏[6]。发现网络中的社团结构，对于了解网络结构和网络性质具有非常重要的意义[7]。

复杂网络中社团结构的发现方法，根据向网络中添加边还是删除边，可以分为凝聚方法和分裂方法。具有代表性的是GIRVAN和NEWMAN提出的基于边介数的GN分裂算法[8]和 BREIGER提出的 Concor算法[9]。GN算法是通过不断地从网络中移除介数最大的边对网络进行划分。而Concor算法则是利用对相关系数的重复迭代产生一个相关系数矩阵，进而对网络进行聚类。图形分割中比较著名的方法是基于贪婪方法的Kernighan-Lin算法[10]和基于Laplace图特征值谱平分法[11]。Kernighan-Lin算法是一种基于贪婪思想的社团发现方法，该方法可以把一个复杂网络划分为两个大小已知的社团。谱平分法是利用网络Laplace矩阵的特征值近似相等的原理进行社团结构划分。Zhang等人在2010年提出了一种复杂网络中社团结构的模糊分析方法[12]。该方法利用节点与社团核连接的紧密程度，判断将节点并入某个社团核中，从而实现了发现社团结构的目的。

一般来说，使用网络中的整体信息来划分网络得到的精度较高，但时间复杂度往往也很高；而利用局部信息划分网络，虽然可以得到较低的时间复杂度[13]，但划分精度往往不够理想。因此，如何利用局部信息而又能得到比较好的划分结果，是一个十分值得研究的问题。

本文通过定义边的聚类系数，提出了基于节点局部信息的社团发现算法。该方法通过不断地计算局部边的聚类系数，并利用凝聚算法的思想得到了网络的社团结构。通过对三个社团网络和Zachary网络的划分，表明了该算法的可行性。

1 预备知识

给定一个具有n个节点的无向无权网络G=＜V，E＞，其 中 ，V={vi|i=1…n}，E={(vi，vj)|vi，vj∈V}。 A 是 G 的 邻接矩阵，其中，若 i、j两节点有边相连，则 aij=1；否则，aij=0。Ni={j|aij=1}表示节点 i的邻居集合，用 di表示节点i的度。

节点 i的聚类系数 Xi为[6]：

其中，Si表示di个节点之间实际存在的边的集合，(di(di-1)/2)表示在di个节点之间最多可能存在的边数。从几何上看，节点i的聚类系数Xi表示包含节点 i在内的实际的三角形数量和包含节点i在内的可能存在的三角形数量之比。如果aij=1，那么可以定义边eij的聚类系数 Cij为：

其中，Nij=Ni∩Nj，表示节点i和j的公共邻居集合[14]，|Nij|表示以eij为边组成的实际三角形的数量，(di+dj-|Nij|-2)表示包含节点i和j在内的可能存在的三角形数量。

边的聚类系数表示边所连接的两个节点的连接强度，值越大表明这两个节点在同一个社团的可能性越大。 显然，0≤Cij≤1。

以图1所示的简单网络为例，计算边e36和e67的聚类系数。节点 3 的度 d3=4，其邻居集合 N3={1，2，4，6}；节点 6 的度 d6=6，N6={1，3，5，7，9}； 节点 7 的度 d7=5，N7={5，6，8，9，10}。 因此， 节点 3 和节点 6 的公共邻居集合N36={1}，节点6和节点7的公共邻居集合N67={5，8，9}。计算边 e36和 e67的聚类系数分别为 C36=|N36|/(d3+d6-|N36|-2)=1/(5+6-1-2)=1/9，C67=|N67|/(d7+d6-|N67|-2)=3/(5+6-3-2)=1/2。

图1 简单网络

由结果可以看出，边C67较大，而C36较小。说明节点6和节点7具有较强的凝聚性，即这两个节点在同一个社团内的可能性较大。

2 算法描述

给定一个具有n个节点的无向无权网络。首先选取度最大的节点作为社团的初始节点，通过邻接矩阵构造该社团的邻居集合。然后判断该集合中节点vi与社团连接的紧密程度。如果节点vi满足以下两个条件之一，说明vi与该社团连接紧密，将该点加入到社团中去，更新社团及其邻居集合。

(1)vi有不小于一半的邻居节点在社团中；

(2)在与社团相连的所有边中，节点vi的一条边eij的聚类系数在这些边中是最大的，并且vi的其他边的聚类系数小于该边的聚类系数。

重复这个过程，直到社团的邻居节点中没有节点能够加入社团，标记所得到的社团。然后从其余节点中重复上述过程，直到整个网络划分完毕。

具体算法如下：

输入：一个无向网络，G=＜V，E＞，其中，V={vi|i=1…n}，E={(vi，vj)|vi，vj∈V}。

输出：网络的社团结构。

(1)初始社团 Ci为空。

(2)选取剩余网络中度最大的节点vm作为社团Ci的初始节点。令Ci=Ci+vm，V=V-vm，并建立社团Ci的邻居集合。

(3)计算社团 Ci的邻居集合，计算与社团 Ci相连的所有边的聚类系数，找到聚类系数最大的边所对应的节点vn，计算节点vn其他边的聚类系数。如果节点vn满足条 件(1)或(2)，则 将 该 节 点 并 入 社 团 Ci， 令 Ci=Ci+vn、V=V-vn，更新社团 Ci的邻居集合。

(4)重复步骤(3)，直到 Ci的邻居集合中不再有新的节点加入到社团中为止，输出社团Ci。令V=V-Ci，若V不空，令 i=i+1，返回步骤(1)。

(5)输出结果。

3 实验与分析

3.1 三个社团网络

下面以计算机生成的三个社团网络为例，如图2所示，该网络包含19个节点和37条边。利用本文提出的算法详细分析该网络，结果如表1所示。表中①表示该节点具有当前网络中最大的度数值；②表示该节点有不小于一半的邻居节点与上一节点所在的社团相连；③表示该节点是上一节点所在社团的邻居并集中具有最大聚类系数的节点，并且该点的其他聚类系数小于该点与社团连接的边的聚类系数。③中内容指的是聚类系数值(具有最大聚类系数的边)。

图2 由19个点组成的三个社团网络

表1 三社团网络算法分析表

首先选取网络中度最大的节点7作为社团C1的初始节点，然后判断社团 C1的邻居集合{3，4，5，6，8}是否有点可以加入。发现节点6的度数值为2，并且有一条边与社团C1相连，因此有不小于一半的节点与社团C1相连符合算法条件(1)，所以可以将节点6加入到社团C1中去，得到社团 C1的邻居集合为{3，4，5，8}。经计算发现，与社团C1相连的边聚类系数中 e74=0.400 0，是所有与社团相连的边中聚类系数最大的。但是与节点4相连的边中聚类系数最大的是边e42，然而节点2不在社团C1中，不符合算法条件(2)，因此不能将节点4加入到社团中去。观察到社团C1的邻居集合中节点5的度数值为 4，与社团 C1相连的边数为 2，符合算法条件(1)，因此可将节点5加入到社团C1中去，此时社团C1的邻居集合为 {2，3，4，8}。发现与社团 C1相连的边中还是 e74的聚类系数最大，并且e42是节点4聚类系数最大的边，节点2不在社团C1内，故节点4不能加入社团C1。但是社团C1的邻居集合中节点4的度数值为4，与社团C1相连的边数为 2，符合算法条件(1)，故将节点 4加入到社团中去，则更新社团的邻居集合为{2，3，8}。经计算可知，e42=0.500 0是与社团C1相连的聚类系数中最大的，而节点2的聚类系数最大的边是e23而非e24，因此不能将节点2加入到社团C1中。然而在更新后的社团邻居集合中，节点 2和节点3的度数值都为4，并且都有两条边与社团C1相连，符合算法条件(1)，因此将节点2和节点3加入到社团C1中，则社团的邻居集合变为{1，8}。此时得出与社团C1相连的边中聚类系数最大的是e21=0.333 3，而且节点1的聚类系数最大的边也是e21，符合算法条件(2)，所以将节点 1加入到社团 C1中去，更新社团的邻居集合为{8}，发现节点8的度数值为5，与社团 C1有一条边相连，不符合算法条件(1)，而且节点8与社团C1的聚类系数为0，小于其他边的聚类系数，亦不符合算法条件(2)，因此不能将节点8加入到社团C1中去。此时邻居集合中没有其他节点可以再加入到社团C1中去，该社团发现完毕。将社团C1从网络中移除，邻居集合清空。同理，分析剩余网络，分别得到社团C2和社团C3，这时对应的结构被认为是网络的实际社团结构，实验结果与原图一致。

3.2 实例

20世纪70年代初期，ZACHARY W用了两年的时间观察美国一所大学空手道俱乐部成员间的相互社会关系。基于这些成员在俱乐部内部及外部的社会关系，ZACHARY W 构造了它们之间的关系网[15]，如图 3(a)所示。整个网络是由34个节点和78条边组成，节点代表俱乐部的成员，边代表成员之间的关系。

图3 空手道俱乐部内部成员的关系网络

根据本文的算法，以 Zachary网络为例，Zachary网络进行划分。由于篇幅有限，以第一社团为例分析该算法。首先选取当前网络中度最大的节点34作为社团C1的初始节点，得到社团 C1的邻居集合为{9，10，14，15，16，19，20，21，23，24，27，28，29，30，31，32，33}。 根据算法条件(1)将节点 10、15、16、19、21、23 和 27 号节点加入到社团 C1中 ， 更 新 后 社 团 的 邻 居 节 点 为 {9，14，20，24，28，29，30，31，32，33}。 查找到社团 C1的最大聚类系数为e34，33=0.588 2，发现该聚类系数同时是节点 33的最大的边聚类系数，因此将节点33加入到社团C1中去，社团C1的邻居节点变为{9，14，20，24，28，29，30，31，32}。根据算法条件 (1)可以将节点30和31加入到社团C1中去，然后更新邻居节点{9，14，20，24，28，29，32}，再根据算法条件(2)，得到最大聚类系数 e30，24=0.400 0，判断可以将节点24加入到社团C1中去，则社团C1的邻居集合变为 {9，14，20，26，28，29，32}。 接下来根据 算法条件(1)，将节点 9和 28加入到社团 C1中，更新邻居结合为{1，3，14，20，25，26，29，32}。 计 算 发 现 最 大 聚 类 系 数e93=0.181 8，但是e93不是节点3聚类系数最大的边，故不能将节点3加入到社团C1中去。然后根据算法条件(1)可陆续将节点29、32、25和26号节点加入到社团C1中去。更新邻居集合为{1，3，14，20}，发现其他邻居节点不能再加入到社团C1中，至此社团C1发现完毕。将社团C1从网络中移除，并且清空邻居集合。同理对剩余网络进行判断，实验结果将网络划分为三个社团，如图3(b)所示。

通过定义边的聚类系数，本文提出一个基于局部信息的社团结构发现算法。从网络中的节点和边出发，通过不断计算边的聚类系数进行节点合并。由于该算法是基于局部信息的，所以降低了时间复杂度。同时利用边聚类系数能够处理很多易混淆的节点，这样既节省了大量的计算时间又提高了计算的精度。通过对算法进行测试，实验结果证明了该方法的可行性和有效性。

[1]ALBERT R， JEONG H， BARABÁSI A L.Diameter of the world-wide Web[J].Nature(London)， 1999， 401：130–131.

[2]SCOOT J.Socialnetwork analysis： a handbook [M].London： Sage Publications， 2002.

[3]HOLME P， HUSS M， JEONG H.Subnetwork hierarchies of biochemical pathways[J]， Bioinformatics， 2003， 19：532–538.

[4]NEWMAN M E J.Scientific collaboration networks[J].Physical.Review E， 2001， 64(1).

[5]杨博，刘大有，Liu Jiming，等.复杂网络聚类算法[J].软件学报，2009，20(1)：54-56.

[6]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006.

[7]王立敏，高学东，马红权.基于最大节点接近度的局部社团结构探测算法[J].计算机工程，2010，36(1)：25-29.

[8]GIRVAN M，NEWMAN M E J.Community structure in socialand biologicalnetworks [J].Proceedings ofthe Natlional Academy Sciences of the United States of America， 2002，99(12)：7821-7826.

[9]BREIGER R L， BOORMAN SA， ARABIE P.An algorithm forclusterrelationsdatawith applicationsto social network analysis and comparison with multidimensional scaling[J].Journal of Mathematical Psychology， 1975，12：328-383.

[10]KERNIGHAN B W，LIN S.A efficient beuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970， 49：291-307.

[11]POTHEN A，SIMON H，LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J Matrix Anal Appl，1990，11(3)： 430-452.

[12]Zhang Dawei， Xie Fuding， Zhang Yong， et al.Fuzzy analysis of community detection in complex networks[J].Physica a： Statistical Mechanics and its Applications，2010，389(22)： 5319-5327.

[13]刘绍海，刘青昆，谢福鼎，等.复杂网络基于局部模块度的社团划分方法[J].计算机工程与设计，2009，3(20)：4708-4714.

[14]解亻刍，汪小帆.复杂网络的一种快速局部社团划分算法[J].计算机仿真，2007，24(11)：82-85.

[15]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research， 1977， 33：452-473.