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

来源：计算机应用杂志2015年第3期北京时间：

作者：孙贵宾, 周勇

单位：中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116

摘要：复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(Lancichinetti-Fortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。

关键词：复杂网络,社团结构,社团检测,结构相似度,仿射传播

基金资助：国家863计划项目(2012AA011004,2012AA0622022);教育部博士点基金资助项目(20100095110003,20110095110010)