Node importance based on the weighted K-order propagation number algorithm

Huang Li-Ya^{1,2}, Tang Ping-Chuan^{1}, Huo You-Liang^{1}, Zheng Yi^{1}, Cheng Xie-Feng^{1,2}

1. College of Electronic and Optical Engineering, College of Microelectronics, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
2. National and Local Joint Engineering Laboratory of RF Integration and Micro-Assembly Technology, Nanjing 210003, China

The measurement of node importance is significant for analyzing a network structure. To comprehensively reflect the global and local network features, in this paper we abstract the propagating process of epidemic diseases based on the network topology structure, and then respectively sets each node as an infection source. After a certain dissemination time K, the number of infected nodes in the network is defined as the K-order propagation number, and the weighted sum of K-order propagation numbers under different values of K is taken as the important index of nodes. The simulation experiments of Watts-Strogatz small-world networks and a dolphin network show that the weighted K-order propagation number algorithm is more effective than the traditional method in evaluating the importance of nodes. For the Watts-Strogatz small-world networks, it can reflect the influence of long-distance connections on information transmission in detail. For the dolphin network, the weighted K-order propagation number algorithm significantly raises the profile of those nodes which play a key role in the information communication between different dolphin communities. In addition, in this paper we use a deliberate attacking method to analyze the western power grid of the United States, the road transportation network of the Chicago region, the co-authorship network in network science and the axonal tracts' network between neurons of mouse. According to the specific order of the node importance from high to low, network nodes are attacked in turn, that is, all edges of the attacked nodes are removed. The analysis results of network parameters such as the network efficiency and the node number of the maximum sub-graph changing with the attacking times show that comparing with other evaluation indices of node importance such as degree, Ren method, Chen method, eigenvector method, Katz index, PageRank, CI method and K-shell, the weighted K-order propagation number algorithm focuses much on destroying the major structure, and all of the above four networks will break down if only a small number of important nodes are attacked. For example, after attacking only 100 nodes, the network efficiency of the western power grid of the United States is down by 90%, and after attacking 200 nodes, the network scale of the maximum sub-graph is nearly 3% of the original network.

Huang Li-Ya,Tang Ping-Chuan,Huo You-Liang et al.. Node importance based on the weighted K-order propagation number algorithm[J]. Acta Physica Sinica, 2019, 68(12):
.
doi:10.7498/aps.68.20190087.

Zhou X, Zhang F M, Zhou W P, Zhou W, Yang F 2012 Acta Phys. Sin. 61 190201[周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 物理学报 61 190201]

[2]

Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31[周涛, 柏文洁, 汪秉宏, 刘之景, 严钢 2005 物理 34 31]

[3]

Liu J G, Wang Z T, Dang Y Z 2005 Mod. Phys. Lett. B 19 785

[4]

Wang X F, Li X, Chen G R 2006 Complex Network Theory and Application (Beijing:Tsinghua University Press) p8 (in Chinese)[汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京:清华大学出版社) 第8页]

[5]

Dunne J A, Williams R J, Martinez N D 2002 Ecol. Lett. 5 558

[6]

Samant K, Bhattacharyya S 2004 Proceedings of the 37th Annual Hawaii International Conference on System Sciences Washington, USA, January 5-8, 2004 p289

[7]

Newman M E J, Forrest S, Balthrop A 2002 Phys. Rev. E 66 035101

[8]

Jeong H, Mason S, Barabasi A L 2001 Nature 411 41

[9]

Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901[任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901]

[10]

Chen D B, Lü L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

[11]

Freeman L C 1977 Sociometry 40 35

[12]

Sabidussi G 1966 Psyehometrika 31 581

[13]

Bavelas A 1950 J. Acoustical Soc. Amer. 22 725

[14]

Stephenson K, Zelen M 1989 Soc. Netw. 1 11

[15]

Borgatti S P 2005 Soc. Netw. 27 55

[16]

Katz L 1953 Psychometrika 18 39

[17]

Zhang J, Xu X K, Li P, Zhang K, Small M 2011 Chaos 21 016107

[18]

Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

[19]

Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

[20]

Bryan K, Leise T 2006 SIAM Rev. 48 569

[21]

Lü L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS One 6 e 2120 2

[22]

Zhong L F, Liu Q H, Wang W, Cai S M 2018 Physica A 511 78

[23]

Allen L J S 1994 Math. Biosci. 124 83

[24]

Huang L Y, Huo Y L, Wang Q, Cheng X F 2019 Acta Phys. Sin. 68 018901[黄丽亚, 霍宥良, 王青, 成谢锋 2019 物理学报 68 018901]

[25]

Watts D J, Strogatz S H 1998 Nature 393 440

[26]

Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396

[27]

Lusseau D, Newman M E J 2004 Proc. Biol. Sci. 271 477

[28]

Eash R W, Chon K S, Lee Y J, Boyce D E 1983 Transport. Res. Rec. 994 30

[29]

Newman M E J 2006 Phys. Rev. E 74 036104

[30]

Ryan A R, Nesreen K A 2015 Proceedings of the Twenty-Ninth AAAI Conference on Artificial Austin, Texas, January 25-30, 2015 p4292

[31]

Li P X, Ren Y Q, Xi Y M 2004 Syst. Eng. 22 13[李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13]

[32]

He N, Li D Y, Gan W Y, Zhu X 2007 Comput. Sci. 34 1[赫南, 李德毅, 淦文燕, 朱熙 2007 计算机科学 34 1]

[33]

Zhao Z Y, Meng X R, Sun R N 2018 Comput. Eng. 44 62[赵志远, 孟相如, 孙瑞男 2018 计算机工程 44 62]