A novel parallel community detection scheme based on label propagation

作者：Chen, Naiyue; Liu, Yun^*; Cheng, Junjun; Liu, Qing

来源：World Wide Web-internet and Web Information Systems, 2018, 21(5): 1377-1398.

DOI：10.1007/s11280-017-0519-0

• Social network
• Community detection
• Label propagation
• Parallel computation

Community detection is one of the most important ways to reflect the structures and mechanisms of a social network. The overlapping communities are more in line with the reality of the social networks. In society, the phenomenon of some members sharing memberships among different communities reflects as overlapping communities in the networks. Dealing with big data networks, it is a challenging and computationally complex problem to detect overlapping communities. In this paper, we propose highly scalable variants of a community-detection algorithm in a parallel manner called Label Propagation with nodes Confidence (PLPAC). We introduce MapReduce into our scheme to process the big data in a parallel manner and guarantee the efficiency of community detection. We implemented the algorithm on artificial networks as well as real networks to evaluate the accuracy and speedup of the proposed method. Experimental results on datasets from different scenarios illustrate that the improved label propagation method outperforms the state-of-the-art methods in terms of accuracy and time efficiency.

• 出版日期2018-9
• 单位中国信息安全测评中心; 北京交通大学