An algorithm Walktrap-SPM for detecting overlapping community structure

作者：Hu, Fang; Zhu, Youze; Shi, Yuan; Cai, Jianchao; Chen, Luogeng; Shen, Shaowu^*

来源：International Journal of Modern Physics B, 2017, 31(15): 1750121.

DOI：10.1142/S0217979217501211

• Walktrap-SPM algorithm
• overlapping community detection
• modularity
• normalized mutual information

In this paper, based on Walktrap algorithm with the idea of random walk, and by selecting the neighbor communities, introducing improved signed probabilistic mixture (SPM) model and considering the edges within the community as positive links and the edges between the communities as negative links, a novel algorithm Walktrap-SPM for detecting overlapping community is proposed. This algorithm not only can identify the overlapping communities, but also can greatly increase the objectivity and accuracy of the results. In order to verify the accuracy, the performance of this algorithm is tested on several representative real-world networks and a set of computer-generated networks based on LFR benchmark. The experimental results indicate that this algorithm can identify the communities accurately, and it is more suitable for overlapping community detection. Compared with Walktrap, SPM and LMF algorithms, the presented algorithm can acquire higher values of modularity and NMI. Moreover, this new algorithm has faster running time than SPM and LMF algorithms.

• 出版日期2017-6-20
• 单位中国地质大学（北京）; 湖北中医药大学; 华中师范大学