摘 要： 发现网络中的社团结构有助于更好地理解网络结构和分析网络属性。通过定义边的聚类系数和基于局部信息的方法，提出了一种寻找复杂网络中社团结构的算法。该算法首先在网络的剩余节点中寻找度最大的节点，然后利用该节点的局部信息、边的聚类系数和凝聚的思想，得到复杂网络的社团结构。在两个典型网络上的测试结果表明了该方法的可行性。
关键词： 复杂网络；社团结构；边的聚类系数；节点的度
近年来，复杂网络已经成为众多领域的关注对象。例如，万维网、人类社会网、生物技术网络和科学家合作关系网[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网络的划分，表明了该算法的可行性。
由结果可以看出，边C67较大，而C36较小。说明节点6和节点7具有较强的凝聚性，即这两个节点在同一个社团内的可能性较大。
2 算法描述
给定一个具有n个节点的无向无权网络。首先选取度最大的节点作为社团的初始节点，通过邻接矩阵构造该社团的邻居集合。然后判断该集合中节点vi与社团连接的紧密程度。如果节点vi满足以下两个条件之一，说明vi与该社团连接紧密，将该点加入到社团中去，更新社团及其邻居集合。
(1)vi有不小于一半的邻居节点在社团中；
(2)在与社团相连的所有边中，节点vi的一条边eij的聚类系数在这些边中是最大的，并且vi的其他边的聚类系数小于该边的聚类系数。
重复这个过程，直到社团的邻居节点中没有节点能够加入社团，标记所得到的社团。然后从其余节点中重复 上述过程，直到整个网络划分完毕。
具体算法如下：
首先选取网络中度最大的节点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条边组成，节点代表俱乐部的成员，边代表成员之间的关系。
根据本文的算法，以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. Social network 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 social and biological networks[J]. Proceedings of the Natlional Academy Sciences of the United States of America， 2002，99(12)：7821-7826.
[9] BREIGER R L， BOORMAN S A， ARABIE P. An algorithm for cluster relations data with applications to 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.