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

Community detection algorithm based on structural similarity affinity propagation

作　　者：孙贵宾[1] 周勇[1] 

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116

出　　处：《计算机应用》2015年第3期633-637,共5页journal of Computer Applications

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

摘　　要：复杂网络中普遍存在着一定的社团结构,社团检测具有重要的理论意义和实际价值。为了提高复杂网络中社团检测的性能,提出了一种基于结构相似度仿射传播的社团检测算法。首先,选取结构相似度作为节点之间的相似性度量,并采用了一种优化的方法来计算复杂网络的相似度矩阵;其次,将计算得到的相似度矩阵作为输入,采用快速仿射传播(FAP)算法进行聚类;最后,得到最终的社团结构。实验结果表明,所提算法在LFR(LancichinettiFortunato-Radicchi)模拟网络上的社团检测平均标准化互信息(NMI)值为65.1%,要高于标签传播算法(LPA)的45.3%以及CNM(Clauset-Newman-Moore)算法的49.8%;在真实网络上的社团检测平均模块度值为53.1%,要高于LPA算法的39.9%以及CNM算法的47.8%,具有更好的社团检测能力,能够发现更高质量的社团结构。The community structure exists generally in the complex network, so the community detection has important theoretical significance and practical value. In order to improve the performance of community detection in the complex network, a community detection algorithm based on structural similarity affinity propagation was proposed. Firstly, the algorithm selected structural similarity as a similarity measurement between nodes, and applied an optimized method to calculate the similarity matrix of complex networks. Secondly, the algorithm made the similarity matrix as an input, and used a Fast Affinity Propagation （FAP） algorithm to cluster. Finally, the algorithm got the final community structure. The experimental results show that in the LFR （Lancichinetti-Fortunato-Radicchi） simulated network, the average community detection Normalized Mutual Information （NMI） value of the proposed algorithm is 65.1%, which is higher than 45.3% of the Label Propagation Algorithm （LPA） and 49.8% of CNM （Clauset-Newman-Moore） algorithm. And in the real network, the average community detection modularity value of the proposed algorithm is 53.1%, which is also higher than 39.9% of the LPA and 47.8% of the CNM algorithm. The proposed algorithm has better ability of community detection, but also can find a higher quality of community structure.

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

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]