Detecting community structure using label propagation with consensus weight in complex network

doi:10.1088/1674-1056/23/9/098902

Abstract Community detection is a fundamental work to analyse the structural and functional properties of complex networks. The label propagation algorithm (LPA) is a near linear time algorithm to find a good community structure. Despite various subsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the basic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these consensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the edge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number of partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps, by computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter to adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an approach named the label propagation algorithm with consensus weight (LPAcw), and the experimental results showed that the LPAcw could enhance considerably both the stability and the accuracy of community partitions.

Keywords: label propagation algorithm community detection consensus cluster complex network

Received: 13 January 2014
Revised: 26 March 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 No. 61370073) and the China Scholarship Council, China (Grant No. 201306070037).

Corresponding Authors: Liang Zong-Wen
E-mail: zongwen-liang@hotmail.com

Cite this article:

Liang Zong-Wen (梁宗文), Li Jian-Ping (李建平), Yang Fan (杨帆), Athina Petropulu Detecting community structure using label propagation with consensus weight in complex network 2014 Chin. Phys. B 23 098902

[1]	Girvan M and Newman M E 2002 Proc. Natl. Acad. Sci. USA 99 7821
[2]	Seifi M, Junier I, Rouquier J B, Iskrov S and Guillaume J L 2013 Complex Networks (Berlin-Heidelberg: Springer) pp. 87-98
[3]	Fortunato S 2010 Phys. Rep. 486 75
[4]	Fortunato S and Castellano C 2012 Computational Complexity (New York: Springer) pp. 490-512
[5]	Zou S R, Peng Y J, Liu A F, Xu X L and He D R 2011 Chin. Phys. B 20 018902
[6]	Tang S X, Chen L and He Y G 2011 Chin. Phys. B 20 110502
[7]	Wang L, Wang J, Shen H W and Cheng X Q 2013 Chin. Phys. B 22 108903
[8]	Blondel V D, Guillaume J L, Lambiotte R and Lefebvre E 2008 J. Stat. Mech.-Theory Exp. 10 P10008
[9]	Newman M E and Girvan M 2004 Phys. Rev. E 69 026113
[10]	Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z and Wagner D 2007 Graph-Theoretic Concepts in Computer Science (Berlin-Heidelberg: Springer) pp. 121-132
[10]	Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z and Wagner D 2007 Graph-Theoretic Concepts in Computer Science (Berlin-Heidelberg: Springer) pp. 121-132
[11]	Fortunato S and Barthelemy M 2007 Proc. Natl. Acad. Sci. USA 104 36
[12]	Guimera R, Sales-Pardo M and Amaral L A N 2004 Phys. Rev. E 70 025101
[13]	Lou H, Li S and Zhao Y 2013 Physica A 392 3095
[14]	Raghavan U N, Albert R and Kumara S 2007 Phys. Rev. E 76 036106
[15]	Šubelj L and Bajec M 2011 Phys. Rev. E 83 036103
[16]	Šubelj L and Bajec M 2011 Eur. Phys. J. B 81 353
[17]	Xie J and Szymanski B K 2013 arXiv.1303.0868
[18]	Topchy A, Jain A K and Punch W 2005 IEEE Trans. Pattern. Anal. Mach. Intell. 27 1866
[19]	Goder A and Filkov V 2008 Alenex 8 109
[20]	Strehl A and Ghosh J 2003 J. Mach. Learn. Res. 3 583
[21]	Lancichinetti A and Fortunato S 2012 Sci. Rep. 2 336
[22]	Monti S, Tamayo P, Mesirov J and Golub T 2003 Mach. Learn. 52 91
[23]	Radicchi F, Castellano C, Cecconi F, Loreto V and Parisi D 2004 Proc. Natl. Acad. Sci. USA 101 2658
[24]	Qinna W and Eric F 2009 ECCS
[25]	Danon L, Diaz-Guilera A, Duch J and Arenas A 2005 J. Stat. Mech.-Theory Exp. 09 P09008
[26]	Liu X and Murata T 2010 IEEE Second International Conference 2010 pp. 576-581
[27]	Leung I X, Hui P, Lio P and Crowcroft J 2009 Phys. Rev. E 79 066107
[28]	Liu X and Murata T 2010 Physica A 389 1493
[29]	Cordasco G and Gargano L 2010 IEEE Int. Workshop Bus. Appl. Soc. Netw. Anal. pp. 1-8
[30]	Shen Y 2013 Chin. Phys. B 22 058903

[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]	Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns Jing Wang(王晶) and Kan Li(李侃). Chin. Phys. B, 2021, 30(12): 120518.
[15]	Improving robustness of complex networks by a new capacity allocation strategy Jun Liu(刘军). Chin. Phys. B, 2021, 30(1): 016401.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Detecting community structure using label propagation with consensus weight in complex network

Cite this article:

Online attention