Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks  

作　　者：武志昊 林友芳 Steve Gregory 万怀宇 田盛丰 

机构地区：[1]School of Computer and Information Technology,Beijing Jiaotong University [2]Department of Computer Science,University of Bristol,Bristol BS81UB,U.K.

出　　处：《Journal of Computer Science & Technology》2012年第3期468-479,共12页计算机科学技术学报（英文版）

基　　金：supported by the Fundamental Research Funds for the Central Universities of China;the National Natural Science Foundation of China under Grant No. 60905029;the Natural Science Foundation of Beijing of China under Grant No. 4112046

摘　　要：In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate ＂rough cores＂, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.In this paper, we propose a balanced multi-label propagation algorithm （BMLPA） for overlapping community detection in social networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate ＂rough cores＂, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.

关 键 词：overlapping community detection multi-label propagation social network 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]