|
|
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.
|
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
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|