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

被引:108
作者
Wu, Zhi-Hao [1 ]
Lin, You-Fang [1 ]
Gregory, Steve [2 ]
Wan, Huai-Yu [1 ]
Tian, Sheng-Feng [1 ]
机构
[1] Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing 100044, Peoples R China
[2] Univ Bristol, Dept Comp Sci, Bristol BS8 1UB, Avon, England
基金
中国国家自然科学基金;
关键词
overlapping community detection; multi-label propagation; social network; COMPLEX NETWORKS;
D O I
10.1007/s11390-012-1236-x
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:468 / 479
页数:12
相关论文
共 28 条
[1]   Link communities reveal multiscale complexity in networks [J].
Ahn, Yong-Yeol ;
Bagrow, James P. ;
Lehmann, Sune .
NATURE, 2010, 466 (7307) :761-U11
[2]  
[Anonymous], 2011, 2011 IEEE 11 INT C D, DOI DOI 10.1109/ICDMW.2011.154
[3]   Detecting network communities by propagating labels under constraints [J].
Barber, Michael J. ;
Clark, John W. .
PHYSICAL REVIEW E, 2009, 80 (02)
[4]   Fast unfolding of communities in large networks [J].
Blondel, Vincent D. ;
Guillaume, Jean-Loup ;
Lambiotte, Renaud ;
Lefebvre, Etienne .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,
[5]   Models of social networks based on social distance attachment -: art. no. 056122 [J].
Boguñá, M ;
Pastor-Satorras, R ;
Díaz-Guilera, A ;
Arenas, A .
PHYSICAL REVIEW E, 2004, 70 (05) :8-1
[6]   Community detection in complex networks [J].
Du, Nan ;
Wang, Bai ;
Wu, Bin .
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2008, 23 (04) :672-683
[7]   Resolution limit in community detection [J].
Fortunato, Santo ;
Barthelemy, Marc .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (01) :36-41
[8]   Community detection in graphs [J].
Fortunato, Santo .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2010, 486 (3-5) :75-174
[9]   Community structure in social and biological networks [J].
Girvan, M ;
Newman, MEJ .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (12) :7821-7826
[10]  
Gregory S, 2010, NEW J PHYS, V12