Identifying influential spreaders in complex networks based on entropy weight method and gravity law

doi:10.1088/1674-1056/ab77fe

中国物理B ›› 2020, Vol. 29 ›› Issue (4): 48902-048902.doi: 10.1088/1674-1056/ab77fe

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇

Identifying influential spreaders in complex networks based on entropy weight method and gravity law

Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江)

1 Institute of Public Safety Research, Tsinghua University, Beijing 100084, China;
2 Department of Engineering Physics, Tsinghua University, Beijing 100084, China;
3 Beijing Key Laboratory of City Integrated Emergency Response Science, Beijing 100084, China

收稿日期:2019-11-21 修回日期:2020-01-30 出版日期:2020-04-05 发布日期:2020-04-05
通讯作者: Shun-Jiang Ni E-mail:sjni@tsinghua.edu.cn
基金资助:
Project support by the National Key Research and Development Program of China (Grant No. 2018YFF0301000) and the National Natural Science Foundation of China (Grant Nos. 71673161 and 71790613).

Identifying influential spreaders in complex networks based on entropy weight method and gravity law

Xiao-Li Yan(闫小丽)^1,2,3, Ya-Peng Cui(崔亚鹏)^1,2,3, Shun-Jiang Ni(倪顺江)^1,2,3

1 Institute of Public Safety Research, Tsinghua University, Beijing 100084, China;
2 Department of Engineering Physics, Tsinghua University, Beijing 100084, China;
3 Beijing Key Laboratory of City Integrated Emergency Response Science, Beijing 100084, China

Received:2019-11-21 Revised:2020-01-30 Online:2020-04-05 Published:2020-04-05
Contact: Shun-Jiang Ni E-mail:sjni@tsinghua.edu.cn
Supported by:
Project support by the National Key Research and Development Program of China (Grant No. 2018YFF0301000) and the National Natural Science Foundation of China (Grant Nos. 71673161 and 71790613).

摘要/Abstract

摘要： In complex networks, identifying influential spreader is of great significance for improving the reliability of networks and ensuring the safe and effective operation of networks. Nowadays, it is widely used in power networks, aviation networks, computer networks, and social networks, and so on. Traditional centrality methods mainly include degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, k-shell, etc. However, single centrality method is one-sided and inaccurate, and sometimes many nodes have the same centrality value, namely the same ranking result, which makes it difficult to distinguish between nodes. According to several classical methods of identifying influential nodes, in this paper we propose a novel method that is more full-scaled and universally applicable. Taken into account in this method are several aspects of node's properties, including local topological characteristics, central location of nodes, propagation characteristics, and properties of neighbor nodes. In view of the idea of the multi-attribute decision-making, we regard the basic centrality method as node's attribute and use the entropy weight method to weigh different attributes, and obtain node's combined centrality. Then, the combined centrality is applied to the gravity law to comprehensively identify influential nodes in networks. Finally, the classical susceptible-infected-recovered (SIR) model is used to simulate the epidemic spreading in six real-society networks. Our proposed method not only considers the four topological properties of nodes, but also emphasizes the influence of neighbor nodes from the aspect of gravity. It is proved that the new method can effectively overcome the disadvantages of single centrality method and increase the accuracy of identifying influential nodes, which is of great significance for monitoring and controlling the complex networks.

关键词: complex networks, influential nodes, entropy weight method, gravity law

Abstract: In complex networks, identifying influential spreader is of great significance for improving the reliability of networks and ensuring the safe and effective operation of networks. Nowadays, it is widely used in power networks, aviation networks, computer networks, and social networks, and so on. Traditional centrality methods mainly include degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, k-shell, etc. However, single centrality method is one-sided and inaccurate, and sometimes many nodes have the same centrality value, namely the same ranking result, which makes it difficult to distinguish between nodes. According to several classical methods of identifying influential nodes, in this paper we propose a novel method that is more full-scaled and universally applicable. Taken into account in this method are several aspects of node's properties, including local topological characteristics, central location of nodes, propagation characteristics, and properties of neighbor nodes. In view of the idea of the multi-attribute decision-making, we regard the basic centrality method as node's attribute and use the entropy weight method to weigh different attributes, and obtain node's combined centrality. Then, the combined centrality is applied to the gravity law to comprehensively identify influential nodes in networks. Finally, the classical susceptible-infected-recovered (SIR) model is used to simulate the epidemic spreading in six real-society networks. Our proposed method not only considers the four topological properties of nodes, but also emphasizes the influence of neighbor nodes from the aspect of gravity. It is proved that the new method can effectively overcome the disadvantages of single centrality method and increase the accuracy of identifying influential nodes, which is of great significance for monitoring and controlling the complex networks.

Key words: complex networks, influential nodes, entropy weight method, gravity law

中图分类号: (Networks and genealogical trees)

89.75.Hc

闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.

Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. Chin. Phys. B, 2020, 29(4): 48902-048902.

参考文献 49

[1]	Zanin M and Lillo F 2013 Eur. Phys. J. Spec. Top. 215 5
[2]	Lordan O, Sallan J M and Simo P 2014 J. Transp. Geogr. 37 112 doi: 10.1016/j.jtrangeo.2014.04.015
[3]	Li H J, Li H Y and Jia C L 2015 Int. J. Mod. Phys. C 26 1550043 doi: 10.1142/S0129183115500436
[4]	Arularasan A N, Suresh A and Seerangan K 2019 Cluster Comput. 22 4035 doi: 10.1007/s10586-018-2616-y
[5]	Shang Y L 2015 J. Syst. Sci. Complexity 28 96 doi: 10.1007/s11424-014-2186-x
[6]	Ma L L, Ma C, Zhang H F and Wang B H 2016 Physica A 451 205 doi: 10.1016/j.physa.2015.12.162
[7]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E and Makse H A 2010 Nat. Phys. 6 888 doi: 10.1038/nphys1746
[8]	Bae J and Kim S 2014 Phys. A Stat. Mech. Appl. 395 549 doi: 10.1016/j.physa.2013.10.047
[9]	Lü L Y, Zhang Y C, Yeung C H and Zhou T 2011 PLoS ONE 6 e21202
[10]	Chen D B, Lü L Y, Shang M S, Zhang Y C and Zhou T 2012 Physica A 391 1777 doi: 10.1016/j.physa.2011.09.017
[11]	Lü L Y, Chen D B and Zhou T 2011 New J. Phys. 13 123005 doi: 10.1088/1367-2630/13/12/123005
[12]	Mehta A and Gupta R 2015 arXiv:1509.07966v1 [cs.SI]
[13]	Wang X Y, Wang Y, Qin X M, Li R and Eustace J 2018 Chin. Phys. B 27 100504 doi: 10.1088/1674-1056/27/10/100504
[14]	Fei L G and Deng Y 2017 Chaos, Solitons and Fractals 104 257 doi: 10.1016/j.chaos.2017.08.010
[15]	Kang L, Xiang B B, Zhai S L, Bao Z K and Zhang H F 2018 Acta Phys. Sin. 67 198901 (in Chinese)
[16]	Freeman L C 1978 Soc. Netw. 1 215 doi: 10.1016/0378-8733(78)90021-7
[17]	Freeman L C 1977 Sociometry 40 35 doi: 10.2307/3033543
[18]	Bonacich P and Lloyd P 2001 Soc. Netw. 23 191 doi: 10.1016/S0378-8733(01)00038-7
[19]	Lü L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C and Zhou T 2016 Phys. Rep. 650 1 doi: 10.1016/j.physrep.2016.06.007
[20]	Wen T and Deng Y 2020 Inform. Sci. 512 549 doi: 10.1016/j.ins.2019.10.003
[21]	Fei L G, Zhang Q and Deng Y 2018 Physica A 512 1044 doi: 10.1016/j.physa.2018.08.135
[22]	Gao S, Ma J, Chen Z M, Wang G H and Xing C M 2014 Physica A 403 130 doi: 10.1016/j.physa.2014.02.032
[23]	Zhong L F, Liu J G and Shang M S 2015 Phys. Lett. A 379 2272 doi: 10.1016/j.physleta.2015.05.021
[24]	Wang Y C, Wang S S and Deng Y 2019 Pramana-J. Phys. 92 68 doi: 10.1007/s12043-019-1727-1
[25]	Zeng A and Zhang C J 2013 Phys. Lett. A 377 1031 doi: 10.1016/j.physleta.2013.02.039
[26]	Song B, Jiang G P, Song Y R and Xia L L 2015 Chin. Phys. B 24 100101 doi: 10.1088/1674-1056/24/10/100101
[27]	Yin R R, Yin X L, Cui M D and Xu Y H 2019 J. Wireless Com. Network 2019 234 doi: 10.1186/s13638-019-1563-5
[28]	Fei L G, Mo H M and Deng Y 2017 Mod. Phys. Lett. B 31 1750243
[29]	Du Y X, Gao C, Hu Y, Mahadevan S and Deng Y 2014 Physica A 399 57 doi: 10.1016/j.physa.2013.12.031
[30]	Liu Y J, Wu J and Liang C Y 2015 Kybernetes 44 1437 doi: 10.1108/K-02-2014-0040
[31]	Mo H M and Deng Y 2019 Physica A 529 121538 doi: 10.1016/j.physa.2019.121538
[32]	Bian T, Hu J T and Deng Y 2017 Physica A 479 422 doi: 10.1016/j.physa.2017.02.085
[33]	Hu J T, Du Y X, Mo H M, Wei D J and Deng Yong 2016 Physica A 444 73 doi: 10.1016/j.physa.2015.09.028
[34]	Li Z, Ren T, Ma X Q, Liu S M, Zhang Y X and Zhou T 2019 Sci. Rep. 9 8387 doi: 10.1038/s41598-019-44930-9
[35]	Ibnoulouafi A and Haziti M E 2018 Chaos, Solitons and Fractals 114 69 doi: 10.1016/j.chaos.2018.06.022
[36]	Kermack W O and McKendrick A G 1927 Proc. R. Soc. Lond. A 115 700 doi: 10.1098/rspa.1927.0118
[37]	http://konect.uni-koblenz.de/networks/moreno_health
[38]	http://konect.uni-koblenz.de/networks/advogato
[39]	https://icon.colorado.edu/#!/networks
[40]	http://vlado.fmf.uni-lj.si/pub/networks/data/collab/geom.htm
[41]	http://konect.uni-koblenz.de/networks/opsahl-usairport
[42]	http://networkrepository.com/bio-CE-GN.php
[43]	Li C, Wang L, Sun S W and Xia C Y 2018 Appl. Math. Comput. 320 512
[44]	Knight W R 1966 J. Amer. Statist. Assoc. 61 436 doi: 10.1080/01621459.1966.10480879
[45]	Kendall M G 1938 Biometrika 30 81 doi: 10.1093/biomet/30.1-2.81
[46]	Kendall M G 1945 Biometrika 33 239 doi: 10.1093/biomet/33.3.239
[47]	Ruan Y R, Lao S Y, Xiao Y D, Wang J D and Bai L 2016 Chin. Phys. Lett. 33 028901 doi: 10.1088/0256-307X/33/2/028901
[48]	Wang J Y, Hou X N, Li K Z and Ding Y 2017 Physica A 475 88 doi: 10.1016/j.physa.2017.02.007
[49]	Liu Y, Tang M, Zhou T and Do Y H 2015 Sci. Rep. 5 9602 doi: 10.1038/srep09602

Identifying influential spreaders in complex networks based on entropy weight method and gravity law

Identifying influential spreaders in complex networks based on entropy weight method and gravity law

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 49

相关文章 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]	Jing-Cheng Zhu(朱敬成) and Lun-Wen Wang(王伦文). An extended improved global structure model for influential node identification in complex networks[J]. 中国物理B, 2022, 31(6): 68904-068904.
[4]	Yuan Jiang(蒋沅), Song-Qing Yang(杨松青), Yu-Wei Yan(严玉为),Tian-Chi Tong(童天驰), and Ji-Yang Dai(代冀阳). A novel method for identifying influential nodes in complex networks based on gravity model[J]. 中国物理B, 2022, 31(5): 58903-058903.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	Jing-En Wang(王静恩), San-Yang Liu(刘三阳), Ahmed Aljmiai, and Yi-Guang Bai(白艺光). Detection of influential nodes with multi-scale information[J]. 中国物理B, 2021, 30(8): 88902-088902.
[10]	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.
[11]	杨远志, 胡敏, 黄泰愚. Influential nodes identification in complex networks based on global and local information[J]. 中国物理B, 2020, 29(8): 88903-088903.
[12]	石勇, 李博, 龙文. Pyramid scheme model for consumption rebate frauds[J]. 中国物理B, 2019, 28(7): 78901-078901.
[13]	朱世钊, 王玉青, 汪秉宏. 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.
[14]	庞明宝, 黄玉满. Coordinated chaos control of urban expressway based on synchronization of complex networks[J]. 中国物理B, 2018, 27(11): 118902-118902.
[15]	王兴元, 王宇, 秦小蒙, 李睿, Justine Eustace. Detecting overlapping communities based on vital nodes in complex networks[J]. 中国物理B, 2018, 27(10): 100504-100504.