Detecting overlapping communities in networks via dominant label propagation

doi:10.1088/1674-1056/24/1/018703

Abstract Community detection is an important methodology for understanding the intrinsic structure and function of a real-world network. In this paper, we propose an effective and efficient algorithm, called Dominant Label Propagation Algorithm (Abbreviated as DLPA), to detect communities in complex networks. The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously. Our algorithm is very efficient, since its computational complexity is almost linear to the number of edges in the network. Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.

Keywords: overlapping community detection dominant label propagation complex network

Received: 14 July 2014
Revised: 15 August 2014
Accepted manuscript online:

PACS:	89.75.Fb	(Structures and organization in complex systems)
	89.75.Hc	(Networks and genealogical trees)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 61173093 and 61202182), the Postdoctoral Science Foundation of China (Grant No. 2012 M521776), the Fundamental Research Funds for the Central Universities of China, the Postdoctoral Science Foundation of Shannxi Province, China, and the Natural Science Basic Research Plan of Shaanxi Province, China (Grant Nos. 2013JM8019 and 2014JQ8359).

Corresponding Authors: Sun He-Li
E-mail: hlsun@mail.xjtu.edu.cn

Cite this article:

Sun He-Li (孙鹤立), Huang Jian-Bin (黄健斌), Tian Yong-Qiang (田勇强), Song Qin-Bao (宋擒豹), Liu Huai-Liang (刘怀亮) Detecting overlapping communities in networks via dominant label propagation 2015 Chin. Phys. B 24 018703

[1]	Clauset A, Newman M E J and Moore C 2004 Phys. Rev. E 70 066111
[2]	Raghavan U N, Albert R and Kumara S 2007 Phys. Rev. E 76 036106
[3]	Rosvall M and Bergstrom C T 2008 Proc. Natl. Acad. Sci. USA 105 1118
[4]	Huang J B, Sun H L, Song Q B, Deng H B and Han J W 2013 IEEE Trans. Knowl. Data Eng. 25 1876
[5]	Baumes J, Goldberg M and Malik M I 2005 Intelligence and Security Informatics (Berlin: Springer) pp. 27-36
[6]	Steve G 2010 New J. Phys. 12 103018
[7]	Lancichinetti A and Fortunato S 2009 Phys. Rev. E 80 016118
[8]	Lee C, Reid F, McDaid A and Hurley N 2010 arXiv:1002.1827
[9]	Palla G, Derényi I, Farkas I and Vicsek T 2005 Nature 435 814
[10]	Xie J R, Szymanski B K and Liu X M 2011 Proceedings of the 11th International Conference on Data Mining Workshops, December 11-14, 2011 Canada, pp. 344-349
[11]	Liang Z W, Li J P, Yang F and Athina P 2014 Chin. Phys. B 23 098902
[12]	Zhang C, Shen H Z, Li F and Yang H Q 2012 Acta Phys. Sin. 61 148902 (in Chinese)
[13]	Liu X, Xie Z and Yi D Y 2012 Chin. Phys. Lett. 29 048902
[14]	Yuan C and Chai 2012 Acta Phys. Sin. 61 218901 (in Chinese)
[15]	Shen Y and Xu H L 2010 Acta Phys. Sin. 59 6022 (in Chinese)
[16]	Huang J B, Sun H L, Liu Y G, Song Q B and Weninger T 2011 PloS One 6 e23829
[17]	Ahn Y Y, Bagrow J P and Lehmann S 2010 Nature 466 761
[18]	Psorakis I, Roberts S, Ebden M and Sheldon B 2011 Phys. Rev. E 83 066114
[19]	Coscia M, Rossetti G, Giannotti F and Pedreschi D 2012 Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 12-16, 2012 China, p. 615
[20]	Adamcsek B, Palla G, Farkas I J, Derényi I and Vicsek T 2006 Bioinformatics 22 1021
[21]	http://snap.stanford.edu/data/
[22]	http://www-personal.umich.edu/ mejn/netdata/
[23]	Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110
[24]	Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577
[25]	Nicosia V, Mangioni G, Carchiolo V and Malgeri M 2009 J. Stat. Mech. 23 03024

[1]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3]	Effect of observation time on source identification of diffusion in complex networks Chaoyi Shi(史朝义), Qi Zhang(张琦), and Tianguang Chu(楚天广). Chin. Phys. B, 2022, 31(7): 070203.
[4]	An extended improved global structure model for influential node identification in complex networks Jing-Cheng Zhu(朱敬成) and Lun-Wen Wang(王伦文). Chin. Phys. B, 2022, 31(6): 068904.
[5]	Characteristics of vapor based on complex networks in China Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[6]	Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[7]	Explosive synchronization: From synthetic to real-world networks Atiyeh Bayani, Sajad Jafari, and Hamed Azarnoush. Chin. Phys. B, 2022, 31(2): 020504.
[8]	Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[9]	Explosive synchronization in a mobile network in the presence of a positive feedback mechanism Dong-Jie Qian(钱冬杰). Chin. Phys. B, 2022, 31(1): 010503.
[10]	LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[11]	Complex network perspective on modelling chaotic systems via machine learning Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[12]	Dynamical robustness of networks based on betweenness against multi-node attack Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Chin. Phys. B, 2021, 30(5): 050501.
[13]	Exploring individuals' effective preventive measures against epidemics through reinforcement learning Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[14]	Improving robustness of complex networks by a new capacity allocation strategy Jun Liu(刘军). Chin. Phys. B, 2021, 30(1): 016401.
[15]	Manufacturing enterprise collaboration network: An empirical research and evolutionary model Ji-Wei Hu(胡辑伟), Song Gao(高松), Jun-Wei Yan(严俊伟), Ping Lou(娄平), Yong Yin(尹勇). Chin. Phys. B, 2020, 29(8): 088901.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Detecting overlapping communities in networks via dominant label propagation

Cite this article:

Online attention