基于结构相似度仿射传播的社团检测算法.doc

基于结构相似度仿射传播的社团检测算法
　　摘要 复杂网络中普遍存在着一定的社团结构，社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能，提出了一种基于结构相似度仿射传播的社团检测算法。首先，选取结构相似度作为节点之间的相似性度量，并采用了一种优化的方法来计算复杂网络的相似度矩阵；其次，将计算得到的相似度矩阵作为输入，采用快速仿射传播（FAP算法进行聚类；最后，得到最终的社团结构。实验结果表明，所提算法在LFR（LancichinettiFortunatoRadicchi模拟网络上的社团检测平均标准化互信息（%，要高于标签传播算法（%以及CNM（%；%，%%，具有更好的社团检测能力，能够发现更高质量的社团结构。
　　关键词 复杂网络；社团结构；社团检测；结构相似度；仿射传播
　　中图分类号
　　0引言
　　大量研究表明，在复杂网络普遍存在着一定的社团结构，社团内部的节点联系紧密，而社团之间的联系则相对稀疏。社团结构在复杂网络中扮演着重要的角色，它可以帮助人们了解复杂网络的功能，发现复杂网络中的潜在规律和预测复杂网络的行为[1]。例如，在社会网中社团结构代表着具有相同兴趣爱好的团体；在Web领域，属于同一社团内部的Web页面拥有较多的链接；在文献网络中，相同社团内部的文献具有相关的研究主题。因此，检测复杂网络中的社团结构具有重要的理论意义和实际价值。
　　目前，复杂网络中的社团检测研究得到了一定的进展，相继提出了很多具有代表性的算法。例如，以层次为中心的算法，采用层次聚类的思想，将原始的复杂网络构建成一个层次性的社区结构，包括凝聚式方法和划分式方法两种，代表性的算法如GN（Girvan Newman[2]、PSNCD（Parallel Social network Community Discovery[3]等；以节点为中心的算法，是对复杂网络中的每个节点都要进行严格的要求，从而进行社区发现，代表性的算法如CPM（Clique Percolation Method[4]等；以链接为中心的算法，代表的算法如Link[5]、DBLINK（Density Based Link[6]；以群组为中心的算法，对网络中的一个社团进行定义，并根据在网络中找出所有满足该定义的社团，代表性的算法如LFM（Local Fitness Measure[7]、DOCA（Detecting Overlapping Community Algorithm[8]等；以网络为中心的算法，采用某种标准（如模块度[9]来衡量整个网络的划分，并通过找到最好的划分来代表社团结构，代表性的算法如CNM（ClausetNewmanMoore[10]、AdClust（Adaptive cluster[11]等；其他算法还包括标签传播算法[12-13]、基于信息传播的算法[14-15]等。
　　然而，上述的所有社团检测算法都是建立在传统聚类算法基础之上，存在传统聚类算法所具有的局限性。而且，现如今的许多复杂网络都存在一定的稀疏性，如果可以很好地利用网络的稀疏性，那么社团检测的速度与效果都会得到很大的提高。针对传统聚类算法的局限性与复杂网络的稀疏特性，本文提出了一种基于结构相似度仿射传播的社团检测算法。该算法的基本思想是：首先，选取结构相似度作为复杂网络中节点之间的相似性度量，并利用复杂网络中的节点只与其邻居节点和间接邻居节点之间具有相似性的特点对相似度计算过程进行优化；其次，将计算得到的相似度矩阵作为输入，利用具有更好的聚类性能的快速仿射传播（Fast Affinity Propagation， FAP算法[15]进行聚类，输出能够代表复杂网络中各个社团结构的代表点的集合。实验结果表明，与其他传统社团检测算法相比较，该算法能够更加有效地发现社团结构，具有更好的社区检测效果。
　　1节点相似性度量
　　本文采用了文献[16]所提出的结构相似度作为节点间的相似性度量，并提出了一种优化的方法来计算相似度。
　　在本文中，只专注于简单、无向以及非加权的图，设G（V，E是一个图，其中：V表示节点的集合，E表示边的集合。
　　
　　结构相似度是一种基于节点局部信息来计算节点相似度的方法，其基本思想是：如果在网络中两个节点有相同的邻居节点，那么这两个节点就具有相似性，而且任意节点与其本身都是完全相似的。
　　定义1节点结构。
　　对于V集合中的任意节点v，v的节点结构Γ（v定义为：
　　Γ（