基于相似度的社团划分算法

吴蔚蔚，刘功申，黄 晨

（上海交通大学信息内容分析技术国家工程实验室，上海，200240）

基于相似度的社团划分算法

吴蔚蔚，刘功申，黄 晨

（上海交通大学信息内容分析技术国家工程实验室，上海，200240）

为对复杂网络进行合理划分，找出真实存在的社团结构，提出一种基于局部模块度和相似度的社团划分算法。计算网络中相连节点之间的相似度，快速聚合关联性最高的节点，从而实现社团的初步划分。以局部模块度为阈值，根据社团相似度聚合社团，得到具有最佳模块度的结果，避免模块度缺陷，提高算法准确度。算法进行社团划分时只需要网络局部信息，降低了时间复杂度。在实际网络和计算机仿真网络实验中的应用结果表明，与NS1，CNM，LAP等算法相比，该算法具有较低的计算复杂度和较高的准确率。

节点；相似度；社团；复杂网络；模块度

1 概述

复杂网络作为生物系统、社会系统、网络、万维网等一系列复杂系统的抽象代表，近年来已经吸引来了来自众多领域学者的研究［1-2］。复杂网络中的社团结构预示着网络中的节点聚合的趋势，同一社团列的节点之间的联系会越发紧密，而社团与社团之间的节点联系会越发稀疏，所以，社团结构是复杂网络的一个非常重要的属性。对复杂网络进行社团划分同时也具有显著的应用意义，如收集具有相同话题的网页、发现代谢网络周期的功能单元等，此外，最近有很多研究结果显示，社团的属性与整体网络的属性有很大不同，忽略对社团结构的研究很可能会错失很多有意义的属性。

划分社团结构的优秀算法都需要满足以下两点要求：较高的社团划分准确度和较低的计算复杂度。在过去几年中，学者们就如何在复杂网络中划分社团提出了许多算法，但是大多都很难同时达到以上两点。

在目前已知的众多算法中，主要有2类聚类算法，一类是划分算法，另一类是层聚类算法。基于拉普拉斯矩阵谱图的特征向量的谱平分算法，和基于尽量增大2个端点都在同一社团的边的数量的贪心算法的KL算法［3］是划分算法中最经典的2种。但这类算法需要预先给定社团数量，不适合实际工作。层聚类算法在社会学领域中分为凝聚和分裂2种，这两类算法都需要先计算每对节点对的连接强度。链接强度的计算方法有很多种，如边界数、边聚集系数、相异性指数、信息度、基于随机游走的相似性等。凝聚算法会重复的聚合连接强度最高的节点对，分裂算法会重复的删除连接强度最低的节点对之间的边，从而获得划分网络的结果。文献［4］提出一种基于边界数分裂方法，即GN算法。该算法在许多网络都能成功应用，但它的复杂度不太理想，对任意一个m条边n个节点的网络，GN算法的时间复杂度是O（m2n），而在稀疏网络情况下，时间复杂度将达到O（n3）。文献［5］提出了相类似的层聚类算法，即CNM算法，其计算复杂度为O（md lb（n）），d是聚类分析时群落结构的深度，稀疏网络情况下为接近线性的O（n lb2（n）），但准确率都不是很高。其他小众但却有巨大影响力的算法有基于信息论的社团发现算法和标号转播算法等。文献［6］的信息论算法（InfoMap算法）以极高的计算复杂度O（n（n+m））为代价得到了极高的准确度。该算法是目前非重叠社团划分的众多算法中准确度较高的一种算法。

本文提出一种新的社团划分算法，首先根据节点相似度，通过只合并最相似节点对的方式实现对网络的初步社团划分，简化网络结构。再以局部模块度为阈值，根据社团相似度进一步聚合社团，从而避免文献［7］算法每次聚合都要计算模块度的缺点，降低时间复杂度。

2 背景知识

复杂网络是彼此错综联系在一起的节点组成集合，本节着重介绍社团结构的衡量标准和相似度衡量标准，这些是本文算法的知识基础。

2.1 社团结构

用G=（V，E）表示一个无权重无方向的网络，其中，V表示网络中节点的集合；E表示网络中边的集合。

社团结构是一个定性的定义，一般将网络中具有相同属性的节点划分在一个社团。学者们尝试用不同的算法将其量化，其中以Newman根据社团内节点连接紧密、社团间节点联系稀疏而提出的模块度Q最为著名，在无权重网络中其定义如下：

其中，ai=∑jeij，eij表示网络中横跨社团Ci和社团Cj的边的数量占所有边数的比例。

模块度Q越高代表社团结构划分得越优秀，由此产生了众多基于模块度的贪心思想的社团划分算法。由于模块度Q的计算量很大，该类算法具有较高的计算复杂度，文献［7］提出了局部模块度Q′，只需计算局部信息而不用考虑全局，计算量得到大幅减少，其定义如下：

其中，Lin表示社团内的边数；Lout表示该社团与外界连接的边数。

尽管使用模块度来评价社团划分结果是业界比较流行的，但该方式仍有其局限性，如不能发现网络中心的强连通小社区和当网络不具有社区结构时，也有比较大的模块度等。所以，本文使用NM I（Normalized M utual Information）来作为算法准确度评价的指标［8］。基于信息论的NM I用于量化衡量分区的相似性，已经被证明是可靠的指标，其被应用于网络社团中的公式为：

其中，A表示实际社团；B表示通过算法划分的社团；CA表示A社团数量；CB表示B社团数量；在N矩阵中，Nij表示在记在A的社团i又在B的社团j的所有节点数量；Ni.表示N矩阵第i行的和；N.j表示N矩阵第j列的和。

2.2 相似度

2.2.1 节点相似度

节点相似度用来量化节点对的连接强度。节点相似度有很多种计算方式，如Jaccard指标、Adam ic-Adar指标、Leicht-Holme-Newman指标等。据文献［9］中对社团划分节点相似度的计算公式如式（4）所示。

其中，T（i）表示节点ni的邻节点集；z∈T（i）∩T（j）表示节点ni和节点nj的公共邻节点集；k（z）表示节点z的度。但是式（1）不能区分出直接相连的节点对与不直接相连的节点对的相似度。如在Zachary棒球俱乐部网络中，通过式（4）计算，节点3与节点34的相似度极高。但事实上这2个节点分属不同社团，故进一步修正式（4）为式（5）：

对于一些特殊情况：如当z∈Ø时，即相邻节点ni和节点nj没有公共邻节点时，如果ni的度为1，则Sij=1，否则Sij=0。如图1所示，n8和n9没有公共邻节点，但显然n9完全依赖n8，S98应为一个极大值。

图1 节点相似度计算示意图

2.2.2 社团相似度

将节点相似度推广到社团相似度，可得到下式：

其中，T（Ci）表示与社团Ci有边直接连接的社团集合；K（Cz）表示社团Cz中与其他社团连接的边数。当Cz∈Ø时，即社团Ci和社团Cj没有公共邻社团时，如果，则SCij=1，否则SCij=0。

2.3 基于节点相似度的聚类社团发现算法

基于节点相似度的聚类社团发现算法于近期提出，步骤如下：（1）随机选取某未划分社团的节点；（2）聚合与该节点相似的邻节点；（3）网络中所有节点都划分社团，算法结束，反之重复步骤（1）。

该类算法的问题在于步骤（2）中，如何选定与指定节点相似的节点。目前衡量节点相似度的算法有很多，但相似度阈值的确认问题还未能被有效的解决，从而影响了算法的准确度。阈值过高，会使得最终社团划分得过于碎片零散；阈值过低，会使得最终社团划分得过于粗犷，将实际上应属于不同的社团的节点合并在了一个社团中。文献［9］直接规避了这个问题，提出根据不同网络，实时调整阈值，但具体如何调整阈值，没有展开。文献［7］提出以公共邻节点数量作为节点相似度、用模块度作为每一次合并节点的阈值的算法，记该算法为NS1，这样做虽然保证了准确度却提高了计算复杂度；文献［10］提出的算法，首先使用基于节点相似度和宽松的阈值聚类网络中节点，再依次计算每个节点在其他社团时的模块度，从而以模块度增大的方向对当前社团划分做微调整，记该算法为NS2，这种做法仅适用于个别节点划分错误的情况，对于大规模节点划分错误无效（如前期阈值选择过低，错误的将不同社团合并到一个社团），而且增加了算法的复杂度。

3 本文算法

3.1 算法描述

对网络进行社团划分，是为了将具有相同属性的节点聚合在一起，从而让人们更进一步研究网络子结构属性。由此可以推论出相似度越大的2个节点，越有可能属于同一个社团。

对于网络G=（V，E），计算出节点相似度矩阵S，首先不断合并具有最大相似度的节点对，完成社团初步划分。再根据局部模块度的增量进步一合并社团，直到获取最大的模块度。

算法具体描述如下：

输入 一个无向无权重网络G=（V，E）

输出 网络的社团结构

步骤1 如果V=Ø，算法结束。否则，根据2.3节知识获得nxn的节点相似度矩阵S=｛Sij｝，其中，n为G的节点数，即n=|V|。新建V′=V。

步骤2 在V中任意选取节点ni，根据相似度矩阵S，选取其最相似节点集N。V′=V′-ni。

步骤3 如果节点ni和节点集N不属于任何社团，新建社团Ci，Ci=ni+N。如果节点ni或节点集N中的任意节点有社团属性，分别属于为Cx，Cy等，则合并这些社团为Cz，使ni∈Cz，N∈Cz。

步骤4 当V′≠Ø时，跳转步骤2。

步骤5 定义局部模块度Q′=0。

步骤6 新建社团集C，集合中包含网络当前划分的社团。新建Qmax=Q′。

步骤7 根据2.2节知识获得社团相似度矩阵SC=｛SCij｝。

步骤8 在C中任取一社团Ci，根据社团相似度矩阵SC，选取其最相似社团集CN。C=C-Ci。

步骤9 合并社团Ci和最相似社团集CN组成新的社团C′i。计算局部模块度Q′i，如果Q′i＞Qmax，则Qmax=Q′i；反之，退回步骤8。

步骤10 当C≠Ø时，跳转步骤8；当C=Ø时，如果Qmax＞Q′，Q′=Qmax，跳转步骤6。

步骤11 输出结果

3.2 可行性分析

基于相似度的聚类算法和依据模块度的聚类算法如CNM算法思维类似，都是以局部最优获取最终结果，这就不可避免地造成结局不是最优，所以该类贪心算法准确度很难达到100%，但目前已有算法中，没有能达到完全准确的算法。所以，本文提出的这种依据相似度的贪心算法，若能实现比已知同类算法时间复杂度低且准确度高，就是一个优秀的社团发现算法。本节将着重分析本文提出的算法如何降低了时间复杂度和提高了准确性。

3.2.1 时间复杂度分析

本文提出的算法计算花费主要由2个部分构成：一是通过节点相似度初步划分网络，二是通过局部模块度和社团相似度对进一步聚合社团。初步依据最相似聚类节点，所有节点需遍历一次，且每个节点都要需要在其邻节点中找出最相似的节点，故时间复杂度为O（kn），k为节点度数。进一步聚合网络阶段，依据模块度和社团相似度，至多需要合并O（lg m）次，m为网络中边的数目，每次合并计算社团相似度和模块度增量的时间复杂度为O（n），故该部分的时间复杂度为O（n lg m）。综上所示，本文提出的算法时间复杂度为O（n lg m）。而NS1算法的时间复杂度为O（mn），NS2算法复杂度为O（n2m）。因此，本文算法的时间复杂度远高于同类基于节点相似度的聚类算法，在一定程度上提高了运行效率。

3.2.2 准确度分析

社团划分的目的是社团内节点连接紧密、社团间节点联系稀疏，依据此提出模块度Q是目前对社团划分算法的评价标准，但其存在自身局限，Q值越高不代表越接近真实情况。下面通过一个简单的例子来说明。考虑2个社团构成的网络，社团S1为100个节点的完全图（任意节点之间都存在边），社团S2为4个节点的完全图，社团S1与社团S2之间以一条边连接，如图2（a）所示。很明显的这个网络应该被划分为S1和S2两个社团，但对于指着这种划分，模块度Q才为0.002 417 38，而对于图2（b）这种划分方式，模块度Q为0.002 564 459，比前者要高，但划分结果却远离社团实际真实情况。

图2 社团S1和社团S2组成的网络及其划分

所以，以模块度最大化作为每一步节点合并的标准，对个别情况（如上文举例的社团大小差异过大）中的部分节点的社团归类不适用，即模块度不适用于单个节点对聚类。但是用节点相似度就避免了这类情况，再次考虑图2（a）所示网络，连接S1和S2的2个节点没有公共邻节点，故两个点的相似度为0，从而自然将2个社团划分开。

本文尝试用比较粗犷的方式定义算法评价标准：使社团间的边数最小化。即如式（7）所示，i，j表示网络中的节点，eij当且仅当节点i，j相连是为1，否则为0。

如果节点i，j被划分到不同社团，则社团间的边数至少为公共邻节点数量。即：

其中，T（i）表示节点i的邻节点。所以可以通过以公共邻节点数量作为相似度，将公共邻节点多的节点对划分在一个社团，从而实现社团间的边数最小。文献［6］根据实验表明，增加考虑公共邻节点的度数，可以提高算法的准确度。因此，本文算法采用包含公共邻节点和其度数的RA指标作为衡量两相邻节点相似度的标准，以最相似作为阈值聚合节点保证初步快速社团划分的准确度。

由此可以得出，本文提出的算法比以依据模块度增量的聚类算法（如CNM算法）和以模块度增量作为每次聚类单个节点的阈值的算法（如NS1算法）准确度高。后续实验数据也证明了本文算法比同类聚类算法具有更高的准确度。

4 实验与结果分析

为了评估本文提出算法的效果，本节将该算法应用于一些实际网络，如海豚社团网、Zachary空手道俱乐部网络、足球队网络和计算机仿真网络。所有实验均在2.3 GH的处理器和3 GB内存的笔记本上运行。

4.1 现实网络

4.1.1 海豚社团网络

Lusseau通过7年的观察，总结了生活在新西兰附近海域的62只海豚的社团网络，这个网络也是如今复杂网络领域中重要的测试用例［11］。海豚群渐渐分化为成年海豚群和年幼海豚群，成年海豚群又进一步分化成更小的海豚群。

使用本文算法划分海豚社团，过程如图3所示。其中，图3（a）为Lusseau观察总结出的海豚网络；图3（b）为基于节点相似度快速聚合社团的结果，该过程将网络初步划分出10个社团。图中节点代表海豚个体，点与点之间的连线代表这2个海豚相似度最高。图3（c）为基于社团相似度和局部模块度进一步聚合社团结果，图中4中颜色代表本算法划分出的4个不同社团。

图3 本文算法处理海豚网络过程

本文算法与其他算法的准确度及时间复杂度对比结果如表1表示，本文算法运算时间最低，可近似于忽略不计，准确度NM I为0.580 1，比InfoM ap算法高2.4%，比NS1算法高1.0%。同时本文算法在时间和NM I上相比于CNM算法、LAP算法和M ultiLevel算法都有一定优势。

表1 海豚网络社团划分算法对比

4.1.2 大学足球队网络

大学足球队网络［12］代表的是某个赛季中大学足球队的比赛情况。该网络由115个节点组成，代表了115个参赛足球队，节点之间用边相连，表示2个足球队之间有比赛。由于比赛将115个足球队划分为12个小组，因此小组内的球赛会比与组间球赛数量更多。使用本文算法划分结果如表2所示。本文算法与其他算法的准确度及时间复杂度对比结果如表3所示。与CNM算法、InfoM ap算法和LAP算法相比，本文算法的运算时间最短，为0.000 8 s，准确度NM I为0.954 5，与InfoM ap差距4.7%，但是却高出NS1算法8.2%，高出LAP算法1.3%，高出CNM算法25.7%，虽和M ultiLevel算法准确度持平，但用时仅为MultiLevel算法的40%。可见，相比于一些常见的算法，本文算法在现实网络具有一定的优势。

表2 本文算法处理足球队网络的社团划分结果

表3 足球队网络社团划分算法对比

通过将本文算法运用于海豚等3个现实网络，可以很容易的发现本文提出的算法准确率可以达到InfoMap算法的水平，同时算法用时略低于LAP标签算法。由此可见，本文算法在现实网络中具有很高的准确度和较低的时间复杂度，是一种优秀的算法。

4.1.3 微博网络

以上通过小规模实际网络方面说明了本文算法的有效性。本节将选用大规模实际网络来验证本文算法。通过调用新浪微博API接口，下载存储新浪用户网络信息。这里以用户为节点，用户之间相互关注为边，从而截取构建出10万个节点、100万条边的微博网络。由于不知该网络的正确社团划分结果，所以这里以模块度Q作为标准比较各类算法的准确度，一般认为，模块度Q值越高，社团划分效果越理想。本文算法与其他算法处理该网络结果如表4所示。NS1算法获得最高的Q值，但由于该算法每一步都需计算一次模块度Q导致用时过多，本文算法取得与NS1差不多的模块度（Q值相差2.4%），但用时仅为其用时的4.2%。

表4 微博网络社团划分算法对比

4.2 模拟网络

基准图［13］是由Lancichinetti等人提出的计算机模拟网络，它的网络拥有与现实网络相类似的社团规模和节点度的异构分布，适合作为评估社团发现算法的测试用例。在基准图中节点度分布和社团大小按照幂律分布。节点度幂律分布的指数为γ，社团规模幂律分布指数为β，μ称为拌和参数，1-μ表示节点与所在社团内的节点连接的概率。

将本文提出的算法应用在平均节点度k=20、节点度分布指数γ=2.5、社团规模分布指数β=1.5、拌和参数μ从0.1到0.6的基准图中。社团划分结果如图4所示。其中的3个图分别代表节点数为1 000，50 000，10 000的基准图。随着拌合参数μ的增大，社团之间的区分越发模糊，即划分社团难度越大。在图4中可以看出，除了InfoMap算法一直以极高的时间复杂度为代价保持着NM I接近1的准确度，其他算法都随着μ值增大，用时增加而准确率在下降。本文提出的算法无论在用时还是准确度上，都远远高于CNM算法。与MultiLevel算法相比，本文算法准确率与其持平，但用时略低于M ultiLevel算法。当μ≤0.6时，本文提出的算法的准确度NM I始终保持在0.8以上。虽然本文算法应用于计算机模拟网络的优势没有应用于现实网络那么明显，但它能在极短的用时下，达到较高的准确度，实验效果优于CNM算法，时间也略优于M ultiLevel算法。

图4 基准图

5 结束语

本文提出的基于相似度和局部模块度的算法，是一种能够在网络中快速划分社团结构的算法。该算法不需要事先确定社团数目和网络的全局信息，只需要节点局部信息就能够得到较好的结果，大幅降低了算法的时间复杂度。在具体实验中以不同节点作为算法入口，发现最后的社团划分结果都一致，即说明本文算法具有很好的稳定性。进一步通过与其他算法的对比实验，实验结果也证明了本文算法不仅具有着较高的准确率，同时时间复杂度也较低。不过目前对本文算法的分析还局限于社团非重叠网络，后续工作是研究如何将该算法应用于重叠社团网络中。

［1］ Newman M E J.The Structure and Function of Complex Networks［J］.SIAM Review，2003，45（2）：167-256.

［2］ Albert R，Barabasi A L.Statistical Mechanics of Complex Networks［J］.Reviews of Modern Physics，2002，74：47-97.

［3］ Kernighan B W，Lin S.An Efficient Heuristic Procedure for Partitioning Graphs［J］.Bell System Technical Journal，1970，49（2）：291-307.

［4］ Girvan M，Newman M E J.Community Structure in Social and Biological Networks［J］.PNAS Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826

［5］ Newman M E J.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E，2004，69（6）.

［6］ Rosvall M，Bergstrom C T.Maps of Radom Walks on Complex Networks［J］.Proceedings of the National Academy of Science，2008，105（4）：1118-1123.

［7］ 刘 微.基于共享邻居数的社团结构发现算法［J］.计算机工程，2011，37（6）：172-174.

［8］ Xuan V N，Julien E，James B.Information Theoretic Measures for Clusterings Comparison：Variants，Properties，Normalization and Correction for Chance［J］.The Journal of Machine Learning Research，2011，11（10）：2837-2854.

［9］ Ying Pan.Detecting Community Structure in Complex Networks via Node Similarity［J］.Physica A，2010，389：2849-2857.

［10］ 胡 琼.社会网络结构划分算法研究［D］.上海：上海交通大学，2014.

［11］ Lusseau D.The Emergent Properties of a Dolphin Social Network［J］.Proceedings of the Royal Society of London，Series B，2003，270（Suppl.）：186-188.

［12］ Sun PG，Gao L，Han Shanshan.Identification of Overlapping and Non-overlapping Community Structure by Fuzzy Clustering in Complex Networks［J］.Information Sciences，2011，181（6）：1060-1071.

［13］ Andrea L，Santo F，Filippo R.Benchmark Graphs for Testing Comm unity Detection Algorithm s［J］.Physical Review E，2008，78（4）.

编辑 金胡考

Comm unity Partition Algorithm Based on Similarity

WU Weiwei，LIU Gongshen，HUANG Chen
（National Engineering Laboratory of Information Content Analysis Technology，Shanghai Jiaotong University，Shanghai 200240，China）

The partition of complex network is useful to find the real community structure and help people research the real world，so this paper proposes a new algorithm of communities partition in network based on the local module degree and similarities.The algorithm calculates the similarities between the nodes in the network and aggregates the nodes which have the highest correlation.It aggregates the communities based on the local module degree and community similarity. Then the results is gotten which has the best local module degree.To verify the validity of the algorithm，this paper applies it in the real network and computer simulation network，and com pares the algorithm with other algorithm s.The result shows that the proposed algorithm has lower computational complexity and higher accuracy compared with NS1，CNM，LAP algorithm s，etc..

nodes；similarity；community；complex network；module degree

吴蔚蔚，刘功申，黄 晨.基于相似度的社团划分算法［J］.计算机工程，2015，41（11）：67-72，83.

英文引用格式：Wu Weiwei，Liu Gongshen，Huang Chen.Community Partition Algorithm Based on Similarity［J］. Computer Engineering，2015，41（11）：67-72，83.

1000-3428（2015）11-0067-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.012

国家“973”计划基金资助项目（2013CB329603）；国家自然科学基金资助项目（61171173）。

吴蔚蔚（1990-），女，硕士，主研方向：复杂网络；刘功申，副教授；黄 晨，硕士。

2014-10-09

2014-12-02 E-m ail：vivibear@sjtu.edu.cn