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

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      Published:  05 October 2018
PACS:  05.10.-a (Computational methods in statistical physics and nonlinear dynamics)  
  02.10.Ox (Combinatorics; graph theory)  

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:

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
[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] 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.
[2] 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.
[3] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇), Christian Böhm(陈学恩), Xueen Chen. Chin. Phys. B, 2020, 29(10): 108901.
[4] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[5] 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.
[6] 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.
[7] Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks
Zhi-gang Zheng(郑志刚), Yu Qian(钱郁). Chin. Phys. B, 2018, 27(1): 018901.
[8] Ranking important nodes in complex networks by simulated annealing
Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟). Chin. Phys. B, 2017, 26(2): 020201.
[9] Empirical topological investigation of practical supply chains based on complex networks
Hao Liao(廖好), Jing Shen(沈婧), Xing-Tong Wu(吴兴桐), Bo-Kui Chen(陈博奎), Mingyang Zhou(周明洋). Chin. Phys. B, 2017, 26(11): 110505.
[10] A local fuzzy method based on “p-strong” community for detecting communities in networks
Yi Shen(沈毅), Gang Ren(任刚), Yang Liu(刘洋), Jia-Li Xu(徐家丽). Chin. Phys. B, 2016, 25(6): 068901.
[11] An improved genetic algorithm with dynamic topology
Kai-Quan Cai(蔡开泉), Yan-Wu Tang(唐焱武), Xue-Jun Zhang(张学军), Xiang-Min Guan(管祥民). Chin. Phys. B, 2016, 25(12): 128904.
[12] Subtle role of latency for information diffusion in online social networks
Fei Xiong(熊菲), Xi-Meng Wang(王夕萌), Jun-Jun Cheng(程军军). Chin. Phys. B, 2016, 25(10): 108904.
[13] Synchronization of Markovian jumping complex networks with event-triggered control
Shao Hao-Yu, Hu Ai-Hua, Liu Dan. Chin. Phys. B, 2015, 24(9): 098902.
[14] Load-redistribution strategy based on time-varying load against cascading failure of complex network
Liu Jun, Xiong Qing-Yu, Shi Xin, Wang Kai, Shi Wei-Ren. Chin. Phys. B, 2015, 24(7): 076401.
[15] Degree distribution and robustness of cooperativecommunication network with scale-free model
Wang Jian-Rong, Wang Jian-Ping, He Zhen, Xu Hai-Tao. Chin. Phys. B, 2015, 24(6): 060101.
No Suggested Reading articles found!