ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (9): 1959-1971.doi: 10.7544/issn1000-1239.2018.20180277

Special Issue: 2018优青专题

Previous Articles     Next Articles

A Two-Stage Community Detection Algorithm Based on Label Propagation

Zheng Wenping1,2,3, Che Chenhao2, Qian Yuhua1,2,3, Wang Jie2   

  1. 1(Research Institute of Big Data Science and Industry, Shanxi University, Taiyuan 030006); 2(School of Computer and Information Technology, Shanxi University, Taiyuan 030006); 3(Key Laboratory of Computational Intelligence and Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006)
  • Online:2018-09-01

Abstract: Due to the random process in node selection and label propagation, the stability of the results of traditional LPA is poor. A two-stage community detection algorithm is proposed based on label propagation, abbreviated as LPA-TS. In the first step of LPA-TS, the labels of nodes are updated according to their participation coefficients in non-decreasing order, and the node label is determined according to the similarity of nodes in the process of node label updating. Some clusters found by Step1 might not satisfy the weak community condition. If a cluster is not a weak community, in the beginning of Step2, we will merge it with the cluster that has most connections with it. Next, we treat each community as a node, and the number of edges between two communities as their edge weights between corresponding nodes. We compute the participation coefficients of each node of the resulted network, and use similar process to get the final results of the communities. The proposed algorithm LPA-TS reduces the randomness in the process of node selection and label propagation; hence, we might obtain stable communities by LPA-TS. In addition, LPA-TS combines small scale communities with adjacent communities in the second phase of the algorithm to improve the quality of community detection. Compared with other classical community detection algorithms on some real networks and artificial networks, the proposed algorithm shows preferable performance on stability, NMI, ARI and modularity.

Key words: complex network, community detection, label propagation, participation coefficient, weak community

CLC Number: