Detecting overlapping communities based on vital nodes in complex networks

doi:10.1088/1674-1056/27/10/100504

中国物理B ›› 2018, Vol. 27 ›› Issue (10): 100504-100504.doi: 10.1088/1674-1056/27/10/100504

• SPECIAL TOPIC—Recent advances in thermoelectric materials and devices • 上一篇下一篇

Detecting overlapping communities based on vital nodes in complex networks

Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace

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

收稿日期:2018-03-21 修回日期:2018-08-09 出版日期:2018-10-05 发布日期:2018-10-05
通讯作者: Xingyuan Wang E-mail:wangxy@dlut.edu.cn
基金资助:
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).

Detecting overlapping communities based on vital nodes in complex networks

Xingyuan Wang(王兴元)^1,2, Yu Wang(王宇)², Xiaomeng Qin(秦小蒙)², Rui Li(李睿)³, Justine Eustace²

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

Received:2018-03-21 Revised:2018-08-09 Online:2018-10-05 Published:2018-10-05
Contact: Xingyuan Wang E-mail:wangxy@dlut.edu.cn
Supported by:
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).

摘要/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.

关键词: complex networks, overlapping communities, vital nodes, seed communities

Abstract:

Key words: complex networks, overlapping communities, vital nodes, seed communities

中图分类号: (Computational methods in statistical physics and nonlinear dynamics)

05.10.-a

02.10.Ox (Combinatorics; graph theory)

王兴元, 王宇, 秦小蒙, 李睿, Justine Eustace. Detecting overlapping communities based on vital nodes in complex networks[J]. 中国物理B, 2018, 27(10): 100504-100504.

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

参考文献 35

[1]	Watts D J and Strogatz S H 1998 Nature 393 440 doi: 10.1038/30918
[2]	Wang X Y and Zhao T F 2017 Commun. Nonlinear Sci. Numer. Simul. 48 63 doi: 10.1016/j.cnsns.2016.12.019
[3]	Newman M E J 2003 SIAM. Rev. 45 167 doi: 10.1137/S003614450342480
[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 doi: 10.1142/S012918310600976X
[6]	Chen Z, Jia M Y and Yang B 2015 Comput. Sci. Inf. Syst. 12 843 doi: 10.2298/CSIS141021029C
[7]	Li J Q, Wang X Y and Eustace J 2013 Physica A 392 6125 doi: 10.1016/j.physa.2013.07.066
[8]	Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821 doi: 10.1073/pnas.122653799
[9]	Fortunato S 2010 Phys. Rep. 486 75 doi: 10.1016/j.physrep.2009.11.002
[10]	Palla G Derényi I Farkas I and Vicsek T 2005 Nature 435 814 doi: 10.1038/nature03607
[11]	Zhang Z W and Wang Z Y 2015 Physica A 421 25 doi: 10.1016/j.physa.2014.11.023
[12]	Zhang X W, You H B and Zhu W 2015 Physica A 421 233 doi: 10.1016/j.physa.2014.10.095
[13]	Kernighan B W and Lin S 1970 Bell. Syst. Tech. J. 49 291 doi: 10.1002/j.1538-7305.1970.tb01770.x
[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 doi: 10.1016/j.physa.2013.01.039
[17]	Lu J G 2005 Chin. Phys. B 14 703 doi: 10.1088/1009-1963/14/4/011
[18]	Lancichinetti A, Fortunato S and Jnos K 2009 New J. Phys. 11 033015 doi: 10.1088/1367-2630/11/3/033015
[19]	Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113 doi: 10.1103/PhysRevE.69.026113
[20]	Chen D B and Shang M S 2010 Physica A 389 4177 doi: 10.1016/j.physa.2010.05.046
[21]	Fortunato S and Barthélemy M 2007 Proc. Natl. Acad. Sci. USA 104 36 doi: 10.1073/pnas.0605965104
[22]	Newman M E J 2004 Phys. Rev. E 70 056131 doi: 10.1103/PhysRevE.70.056131
[23]	Shen H, Cheng X and Cai K 2009 Physica A 388 1706 doi: 10.1016/j.physa.2008.12.021
[24]	Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110 doi: 10.1103/PhysRevE.78.046110
[25]	http://www-personal.umich.edu/~mejn/netdata/
[26]	Zachary W W 1977 J. Anthropol. Res. 33 452 doi: 10.1086/jar.33.4.3629752
[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 doi: 10.1016/j.neucom.2015.02.064
[29]	Eustace J, Wang X and Cui Y 2015 Physica A 421 510 doi: 10.1016/j.physa.2014.11.039
[30]	Li Z C and Tang J H 2015 IEEE Trans. Multimedia 17 1989 doi: 10.1109/TMM.2015.2477035
[31]	Li Z C and Tang J H 2017 IEEE Trans. Image Process. 26 276 doi: 10.1109/TIP.2016.2624140
[32]	Yang W, Wang Y W and Xiao J W 2017 Int. J. Control 90 1 doi: 10.1080/00207179.2017.1257561
[33]	Wirth-Lima A J, Silva M G and Sombra A S B 2018 Chin. Phys. B 27 023201 doi: 10.1088/1674-1056/27/2/023201
[34]	Liao H, Shen Q, Wu X T, Chen B K and Zhou M Y 2017 Chin. Phys. B 26 110505 doi: 10.1088/1674-1056/26/11/110505
[35]	Zhang X Y, Meng Y Y and Zhang H 2011 Chin. Phys. Lett. 28 12070

Detecting overlapping communities based on vital nodes in complex networks

Detecting overlapping communities based on vital nodes in complex networks

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 35

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[2]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.
[3]	Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Characteristics of vapor based on complex networks in China[J]. 中国物理B, 2022, 31(4): 49201-049201.
[4]	Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks[J]. 中国物理B, 2022, 31(2): 20503-020503.
[5]	Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control[J]. 中国物理B, 2022, 31(10): 100504-100504.
[6]	Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks[J]. 中国物理B, 2021, 30(8): 88901-088901.
[7]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[8]	杨远志, 胡敏, 黄泰愚. Influential nodes identification in complex networks based on global and local information[J]. 中国物理B, 2020, 29(8): 88903-088903.
[9]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.
[10]	石勇, 李博, 龙文. Pyramid scheme model for consumption rebate frauds[J]. 中国物理B, 2019, 28(7): 78901-078901.
[11]	朱世钊, 王玉青, 汪秉宏. Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms[J]. 中国物理B, 2019, 28(10): 108901-108901.
[12]	庞明宝, 黄玉满. Coordinated chaos control of urban expressway based on synchronization of complex networks[J]. 中国物理B, 2018, 27(11): 118902-118902.
[13]	郑志刚, 钱郁. Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks[J]. 中国物理B, 2018, 27(1): 18901-018901.
[14]	孙昱, 姚佩阳, 万路军, 申健, 钟赟. Ranking important nodes in complex networks by simulated annealing[J]. 中国物理B, 2017, 26(2): 20201-020201.
[15]	廖好, 沈婧, 吴兴桐, 陈博奎, 周明洋. Empirical topological investigation of practical supply chains based on complex networks[J]. 中国物理B, 2017, 26(11): 110505-110505.