›› 2012, Vol. 27 ›› Issue (3): 468-479.doi: 10.1007/s11390-012-1236-x

• Special Issue on Social Network Mining • Previous Articles     Next Articles

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

Zhi-Hao Wu1 (武志昊), You-Fang Lin1 (林友芳), Steve Gregory2, Huai-Yu Wan1 (万怀宇), Student Member, CCF, and Sheng-Feng Tian1 (田盛丰)   

  1. 1. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;
    2. Department of Computer Science, University of Bristol, Bristol BS8 1UB, U.K.
  • Received:2011-08-31 Revised:2012-01-06 Online:2012-05-05 Published:2012-05-05
  • About author:Zhi-Hao Wu received the B.Sc. degree in computer science and tech-nology from Beijing Jiaotong Uni-versity (BJTU) in 2007. Now he is a Ph.D. candidate in computer sci-ence and technology at BJTU. His re-search interests include complex net-works and social networks analysis, data mining and machine learning. His current research focuses on com-munity detection and evolution in networks.
  • Supported by:

    This work was partially 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.

[1] Fortunato S. Community detection in graphs. Physics Re-ports, 2010, 486: 75-174.

[2] Raghavan U, Albert R, Kumara S. Near linear time algo-rithm to detect community structures in large-scale networks.Physical Review E, 2007, 76(3): 036106.

[3] Blondel V, Guillaume J, Lambiotte R et al. Fast unfoldingof communities in large networks. J. Statistical Mechanics:Theory and Experiment, 2008, 2008(10): P10008.

[4] Rosvall M, Bergstrom C. Maps of random walks on complexnetworks reveal community structure. Proc. the NationalAcademy of Sciences of U.S.A., 2008, 105(4): 1118-1123.

[5] Du N, Wang B, Wu B. Community detection in complex net-works. J. Comput. Sci. & Technol., 2008, 23(4): 672-683.

[6] Leung I X Y, Hui P, Lio P, Crowcroft J. Towards real-timecommunity detection in large networks. Physical Review E,2009, 79(6): 066107.

[7] Barber M J, Clark J W. Detecting network communities bypropagating labels under constraints. Physical Review E,2009, 80(2): 026129.

[8] Subelj L, Bajec M. Unfolding communities in large complexnetworks: Combining defensive and offensive label propaga-tion for core extraction. Physical Review E, 2011, 83(3):036103.

[9] Gregory S. Finding overlapping communities in networks bylabel propagation. New J. Physics, 2010, 12(10): 103018.

[10] Xie J, Szymanski B K, Liu X. Slpa: Uncovering overlappingcommunities in social networks via a speaker-listener interac-tion dynamic process. In Proc. IEEE ICDM Workshop onDMCCI 2011, Vancouver, Canada, Dec. 2011, pp.344-349.

[11] Palla G, Der?enyi I, Farkas I, Vicsek T. Uncovering the over-lapping community structure of complex networks in natureand society. Nature, 2005, 435(7043): 814-818.

[12] Lancichinetti A, Fortunato S, Kertesz J. Detecting the over-lapping and hierarchical community structure in complex net-works. New Journal of Physics, 2009, 11: 033015.

[13] Lee C, Reid F, McDaid A, Hurley N. Detecting highly over-lapping community structure by greedy clique expansion. InProc. the 4th SNA-KDD Workshop, Washington, DC, USA,July 25-28, 2010.

[14] Lancichinetti A, Radicchi F, Ramasco J J, Fortunato S. Find-ing statistically significant communities in networks. PLoSOne, 2011, 6(4): e18961.

[15] Ahn Y Y, Bagrow J P, Lehmann S. Link communities revealmultiscale complexity in networks. Nature, 2010, 466(7307):761-764.

[16] Girvan M, Newman ME J. Community structure in social andbiological networks. Proc. the National Academy of Sciencesof the U.S.A., 2002, 99(12): 7821-7826.

[17] Lancichinetti A, Fortunato S. Benchmarks for testing com-munity detection algorithms on directed and weighted graphswith overlapping communities. Physical Review E, 2009,80(1): 016118.

[18] Newman M E J, Girvan M. Finding and evaluating commu-nity structure in networks. Physical Review E, 2004, 69(2):026113.

[19] Nicosia V, Mangioni G, Carchiolo V et al. Extending thedefinition of modularity to directed graphs with overlappingcommunities. J. Statistical Mechanics: Theory and Experi-ment, 2009, P03024.

[20] Shen H, Cheng X, Cai K et al. Detect overlapping and hier-archical community structure in networks. Physica A: Statis-tical Mechanics and Its Applicat., 2009, 388(8): 1706-1712.

[21] Shen H, Cheng X, Guo J. Quantifying and identifying theoverlapping community structure in networks. Journal of Sta-tistical Mechanics: Theory and Experiment, 2009, P07042.

[22] Fortunato S, Barthelemy M. Resolution limit in communitydetection. Proceedings of the National Academy of Sciencesof the United States of America, 2007, 104(1): 36-41.

[23] Zachary W. An information flow model for conflict and fissionin small groups. J. Anthropological Research, 1977, 33(4):452-473.

[24] Lusseau D, Schneider K, Boisseau O J et al. The bottlenosedolphin community of doubtful sound features a large propor-tion of long-lasting associations —— Can geographic isolationexplain this unique trait?. Behavioral Ecology and Sociobiol-ogy, 2003, 54: 396-405.

[25] Guimera R, Danon L, D??az-Guilera A, Giralt F, Arenas A.Self-similar community structure in a network of human inte-ractions. Phys. Rev. E, 2003, 68: 065103.

[26] Gregory S. An algorithm to find overlapping communitystructure in networks. In Proc. the 11th PKDD, Sept. 2007,pp.91-102.

[27] Boguna M, Pastor-Satorras R, D??az-Guilera A, Arenas A.Models of social networks based on social distance attach-ment. Physical Review E , 2004, 70: 056122.

[28] Newman M E J. The structure of scientific collaboration net-works. Proceedings of the National Academy of Sciences ofthe United States of America, 2001, 98: 404-409.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved