Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks
详细信息 查看全文
- 作者：Zhi-Hao Wu (1) zhihaowu@bjtu.edu.cn
You-Fang Lin (1) yflin@bjtu.edu.cn
Steve Gregory (2) steve@compsci.bristol.ac.uk
Huai-Yu Wan (1) huaiyuwan@bjtu.edu.cn
Sheng-Feng Tian (1) sftian@bjtu.edu.cn - 关键词：overlapping community detection – ; multi ; label propagation – ; social network
- 刊名：Journal of Computer Science and Technology
- 出版年：2012
- 出版时间：January 2012
- 年：2012
- 卷：27
- 期：3
- 页码：468-479
- 全文大小：4.2 MB
- 参考文献：1. Fortunato S. Community detection in graphs. Physics Reports, 2010, 486: 75–174.
2. Raghavan U, Albert R, Kumara S. Near linear time algorithm 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 unfolding of communities in large networks. J. Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
4. Rosvall M, Bergstrom C. Maps of random walks on complex networks reveal community structure. Proc. the National Academy of Sciences of U.S.A., 2008, 105(4): 1118–1123.
5. Du N, Wang B, Wu B. Community detection in complex networks. J. Comput. Sci. & Technol., 2008, 23(4): 672–683.
6. Leung I X Y, Hui P, Lio P, Crowcroft J. Towards real-time community detection in large networks. Physical Review E, 2009, 79(6): 066107.
7. Barber M J, Clark J W. Detecting network communities by propagating labels under constraints. Physical Review E, 2009, 80(2): 026129.
8. Šubelj L, Bajec M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction. Physical Review E, 2011, 83(3): 036103.
9. Gregory S. Finding overlapping communities in networks by label propagation. New J. Physics, 2010, 12(10): 103018.
10. Xie J, Szymanski B K, Liu X. Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Proc. IEEE ICDM Workshop on DMCCI 2011, Vancouver, Canada, Dec. 2011, pp.344–349.
11. Palla G, Der茅nyi I, Farkas I, Vicsek T. Uncovering the over-lapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814–818.
12. Lancichinetti A, Fortunato S, Kertesz J. Detecting the over-lapping and hierarchical community structure in complex networks. 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. In Proc. the 4th SNA-KDD Workshop, Washington, DC, USA, July 25-28, 2010.
14. Lancichinetti A, Radicchi F, Ramasco J J, Fortunato S. Finding statistically signi炉cant communities in networks. PLoS One, 2011, 6(4): e18961.
15. Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks. Nature, 2010, 466(7307): 761–764.
16. Girvan M, Newman ME J. Community structure in social and biological networks. Proc. the National Academy of Sciences of the U.S.A., 2002, 99(12): 7821–7826.
17. Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 2009, 80(1): 016118.
18. Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113.
19. Nicosia V, Mangioni G, Carchiolo V et al. Extending the definition of modularity to directed graphs with overlapping communities. J. Statistical Mechanics: Theory and Experiment, 2009, P03024.
20. Shen H, Cheng X, Cai K et al. Detect overlapping and hierarchical community structure in networks. Physica A: Statistical Mechanics and Its Applicat., 2009, 388(8): 1706–1712.
21. Shen H, Cheng X, Guo J. Quantifying and identifying the overlapping community structure in networks. Journal of Statistical Mechanics: Theory and Experiment, 2009, P07042.
22. Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36–41.
23. Zachary W. An information flow model for conflict and fission in small groups. J. Anthropological Research, 1977, 33(4): 452–473.
24. Lusseau D, Schneider K, Boisseau O J et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations — Can geographic isolation explain this unique trait?. Behavioral Ecology and Sociobiology, 2003, 54: 396–405.
25. Guimer脿 R, Danon L, D铆az-Guilera A, Giralt F, Arenas A. Self-similar community structure in a network of human interactions. Phys. Rev. E, 2003, 68: 065103.
26. Gregory S. An algorithm to find overlapping community structure in networks. In Proc. the 11th PKDD, Sept. 2007, pp.91–102.
27. Bogu帽a M, Pastor-Satorras R, D铆az-Guilera A, Arenas A. Models of social networks based on social distance attachment. Physical Review E, 2004, 70: 056122.
28. Newman M E J. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences of the United States of America, 2001, 98: 404–409. - 作者单位：1. School of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044 China2. Department of Computer Science, University of Bristol, Bristol, BS8 1UB U.K.
- 刊物类别：Computer Science
- 刊物主题：Computer Science, general
Software Engineering
Theory of Computation
Data Structures, Cryptology and Information Theory
Artificial Intelligence and Robotics
Information Systems Applications and The Internet
Chinese Library of Science - 出版者：Springer Boston
- ISSN：1860-4749
文摘
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.