基于平均互信息的最优社区发现方法  

Optimal community detection method based on average mutual information

作　　者：李东[1] 程鸣权 徐杨[1] 袁峰 陈奕男 付雅晴 Dong LI;Mingquan CHENG;Yang XU;Feng YUAN;Yinan CHEN;Yaqing FU(School of Software Engineering, South China University of Technology, Guangzhou 510006, China;Institute of Software Application Technology, Guangzhou & Chinese Academy of Sciences, Guangzhou 511458, China)

机构地区：[1]华南理工大学软件学院,广州510006 [2]广州中国科学院软件应用技术研究所,广州511458

出　　处：《中国科学：信息科学》2019年第5期613-629,共17页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61602186);广东省科技计划项目(批准号:2015B010103002;2016B050502001)资助

摘　　要：本文提出一种基于平均互信息的最优社区发现方法 AMI (average mutual information),该方法通过计算社区划分时的平均互信息值找出最优的社区划分.将AMI方法作用在非重叠社区发现算法GN和重叠社区发现算法COPRA上分别获得改进的AMI-GN算法和AMI-COPRA算法.将AMI-GN算法与GN, FN, IE算法进行对比实验,实验结果表明AMI-GN算法相较于其他算法提高了社区发现的质量.将AMI-COPRA算法与COPRA, LPPB算法进行对比实验,实验结果表明AMI-COPRA算法大幅度提升原始COPRA算法的稳定性,大大减少了平均迭代次数,加快了算法的收敛速度.相较于LPPB算法,发现社区的质量相差不大,但AMI-COPRA算法比LPPB算法更加稳定.研究表明,运用AMI方法可有效地改进典型的非重叠社区发现算法和重叠社区发现算法的性能.This study proposes an optimal community detection method based on average mutual information(AMI). We calculate the optimal community partition using AMI. This method is applied to the non-overlapping community detection algorithm(GN) and the overlapping community detection algorithm(COPRA), and the AMI-GN algorithm and the AMI-COPRA algorithm are generated respectively. Compared with the performance of the original GN, FN, and IE algorithm, experimental results show that AMI-GN algorithm improves the quality of community detection. Furthermore, compared with the performance of the original COPRA algorithm and the LPPB algorithm, experimental results show that the AMI-COPRA algorithm improves the stability of the original COPRA algorithm, reduces the average number of iterations, and accelerates the convergence speed of the algorithm. Moreover, compared with the LPPB algorithm, the AMI-COPRA algorithm reveals that the quality of the community shows a little difference, but is more stable than the LPPB algorithm. Our study shows that the AMI-based methods can improve the performance of typical non-overlapping community discovery algorithms and overlapping community discovery algorithms.

关 键 词：AMI-COPRA算法 AMI-GN算法 平均互信息 AMI方法 社区发现 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]