Please wait a minute...
Chin. Phys. B, 2018, Vol. 27(10): 100504    DOI: 10.1088/1674-1056/27/10/100504
GENERAL Prev   Next  

Detecting overlapping communities based on vital nodes in complex networks

Xingyuan Wang(王兴元)1,2, Yu Wang(王宇)2, Xiaomeng Qin(秦小蒙)2, Rui Li(李睿)3, Justine Eustace2
1 School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China;
2 Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China;
3 School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
Abstract  

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm (DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.

Keywords:  complex networks      overlapping communities      vital nodes      seed communities  
Received:  21 March 2018      Revised:  09 August 2018      Accepted manuscript online: 
PACS:  05.10.-a (Computational methods in statistical physics and nonlinear dynamics)  
  02.10.Ox (Combinatorics; graph theory)  
Fund: 

Project supported by the National Natural Science Foundation of China (Grant Nos. 61672124, 61370145, 61173183, and 61503375) and the Password Theory Project of the 13th Five-Year Plan National Cryptography Development Fund, China (Grant No. MMJJ20170203).

Corresponding Authors:  Xingyuan Wang     E-mail:  wangxy@dlut.edu.cn

Cite this article: 

Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace Detecting overlapping communities based on vital nodes in complex networks 2018 Chin. Phys. B 27 100504

[1] Watts D J and Strogatz S H 1998 Nature 393 440
[2] Wang X Y and Zhao T F 2017 Commun. Nonlinear Sci. Numer. Simul. 48 63
[3] Newman M E J 2003 SIAM. Rev. 45 167
[4] Cui Y Z and Wang X Y 2014 Physica A 407 7
[5] Shen X J, Wang Z F and Wu L N 2006 Int. J. Mod. Phys. C 17 1055
[6] Chen Z, Jia M Y and Yang B 2015 Comput. Sci. Inf. Syst. 12 843
[7] Li J Q, Wang X Y and Eustace J 2013 Physica A 392 6125
[8] Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821
[9] Fortunato S 2010 Phys. Rep. 486 75
[10] Palla G Derényi I Farkas I and Vicsek T 2005 Nature 435 814
[11] Zhang Z W and Wang Z Y 2015 Physica A 421 25
[12] Zhang X W, You H B and Zhu W 2015 Physica A 421 233
[13] Kernighan B W and Lin S 1970 Bell. Syst. Tech. J. 49 291
[14] Fiedler M 1973 Czech Math. J. 23 298
[15] Nguyen N P, Dinh T N, Nguyen D T and Thai M T 2012 IEEE Third Int. Conf. Soc. Computing, January 3, 2012, Boston, USA, pp. 201, 35
[16] Wang X Y and Li J Q 2013 Physica A 392 2555
[17] Lu J G 2005 Chin. Phys. B 14 703
[18] Lancichinetti A, Fortunato S and Jnos K 2009 New J. Phys. 11 033015
[19] Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113
[20] Chen D B and Shang M S 2010 Physica A 389 4177
[21] Fortunato S and Barthélemy M 2007 Proc. Natl. Acad. Sci. USA 104 36
[22] Newman M E J 2004 Phys. Rev. E 70 056131
[23] Shen H, Cheng X and Cai K 2009 Physica A 388 1706
[24] Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110
[25] http://www-personal.umich.edu/~mejn/netdata/
[26] Zachary W W 1977 J. Anthropol. Res. 33 452
[27] Wang Y W, Liu M and Liu Z W 2014 Appl. Math. Comput. 246 572
[28] Yang W, Wang Y W and Zeng Z G 2015 Neurocomputing 164 252
[29] Eustace J, Wang X and Cui Y 2015 Physica A 421 510
[30] Li Z C and Tang J H 2015 IEEE Trans. Multimedia 17 1989
[31] Li Z C and Tang J H 2017 IEEE Trans. Image Process. 26 276
[32] Yang W, Wang Y W and Xiao J W 2017 Int. J. Control 90 1
[33] Wirth-Lima A J, Silva M G and Sombra A S B 2018 Chin. Phys. B 27 023201
[34] Liao H, Shen Q, Wu X T, Chen B K and Zhou M Y 2017 Chin. Phys. B 26 110505
[35] Zhang X Y, Meng Y Y and Zhang H 2011 Chin. Phys. Lett. 28 12070
[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] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] Influential nodes identification in complex networks based on global and local information
Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[10] Identifying influential spreaders in complex networks based on entropy weight method and gravity law
Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[11] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[12] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[13] Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms
Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[14] Coordinated chaos control of urban expressway based on synchronization of complex networks
Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[15] Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks
Zhi-gang Zheng(郑志刚), Yu Qian(钱郁). Chin. Phys. B, 2018, 27(1): 018901.
No Suggested Reading articles found!