Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models

Kong Jiang-Tao Huang Jian Gong Jian-Xing Li Er-Yu

Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models

Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • Identifying the most important nodes is significant for investigating the robustness and vulnerability of complex network. A lot of methods based on network structure have been proposed, such as degree, K-shell and betweenness, etc. In order to identify the important nodes in a more reasonable way, both the network topologies and the characteristics of nodes should be taken into account. Even at the same location, the nodes with different characteristics have different importance. The topological structures and the characteristics of the nodes are considered in the complex network dynamics model. However, such methods are rarely explored and their applications are restricted. In order to identify the important nodes in undirected weighted networks, in this paper we propose a method based on dynamics model. Firstly, we introduce a way to construct the corresponding dynamics model for any undirected weighted network, and the constructed model can be flexibly adjusted according to the actual situation. It is proved that the constructed model is globally asymptotic stable. To measure the changes of the dynamic model state, the mean deviation and the variance are presented, which are the criteria to evaluate the importance of the nodes. Finally, disturbance test and destructive test are proposed for identifying the most important nodes. Each node is tested in turn, and then the important nodes are identified. If the tested node can recover from the damaged state, the disturbance test is used. If the tested node is destroyed completely, the destructive test is used. The method proposed in this paper is based on the dynamics model. The node importance is influenced by the network topologies and the characteristics of nodes in these two methods. In addition, the disturbance test and destructive test are used in different situations, forming a complementary advantage. So the method can be used to analyze the node importance in a more comprehensive way. Experiments are performed on the advanced research project agency networks, the undirected networks with symmetric structures, the social network, the Dobbs-Watts-Sabel networks and the Barrat-Barthelemy-Vespignani networks. If the nodes in the network have the same dynamic model, the network is considered to be the homogeneous network; otherwise, the network is heterogeneous network. And experiments can be divided into four categories, namely, the disturbance test, the destructive test on the homogeneous network, the disturbance test and the destructive test on the heterogeneous network. The experimental results show that the methods proposed in this paper are effective and credible.
      Corresponding author: Huang Jian, nudtjHuang@hotmail.com
    [1]

    Zhao M, Zhou T, Wang B H, Wang W X 2005 Phys. Rev. E 72 057102

    [2]

    Zemanov L, Zhou C, Kurths J 2006 Physica D 224 202

    [3]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [4]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [5]

    Estrada E, Rodrguez-Velzquez J A 2005 Phys. Rev. E 71 056103

    [6]

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

    [7]

    L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [8]

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

    [9]

    Ruan Y R, Lao S Y, Wang J D, Bai L, Chen L D 2017 Acta Phys. Sin. 66 038902 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 陈立栋 2017 物理学报 66 038902]

    [10]

    Freeman L C, Borgatti S P, White D R 1991 Soc. Networks 13 141

    [11]

    Estrada E, Higham D J, Hatano N 2009 Physica A 388 764

    [12]

    Li Q, Zhou T, L L Y, Chen D B 2014 Physica A 404 47

    [13]

    Zhou Y B, Lei T, Zhou T 2011 Europhys. Lett. 94 48002

    [14]

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

    [15]

    Gao C, Wei D J, Hu Y, Mahadevan S, Deng Y 2013 Physica A 392 5490

    [16]

    Wang Y, Guo J L 2017 Acta Phys. Sin. 66 050201 (in Chinese) [王雨, 郭进利 2017 物理学报 66 050201]

    [17]

    L L, Zhang Y C, Chi H Y, Zhou T 2011 Plos One 6 e21202

    [18]

    Yan G, Zhou T, Wang J, Fu Z Q, Wang B 2005 Chin. Phys. Lett. 22 510

    [19]

    Brummitt C D, DSouza R M, Leicht E A 2012 Proceedings of the National Academy of Sciences of the United States of America 109 E680

    [20]

    Du W J, Yu J L, An X L, Ma C X 2015 Transport Research 1 14 (in Chinese) [杜文举, 俞建宁, 安新磊, 马昌喜 2015 交通运输研究 1 14]

    [21]

    Liu Y Y, Slotine J J, Barabasi A L 2011 Nature 473 167

    [22]

    Jia T, Barabsi A L 2013 Sci. Rep. 3 2354

    [23]

    Chen T P, Lu W L 2013 Theory of Coordination in Complex Networks (Beijing: Higher Education Press) p14 (in Chinese) [陈天平, 卢文联 2013 复杂网络协调性理论 (北京: 高等教育出版社) 第14 页]

    [24]

    Wang E F, Shi S M 2005 Advanced Algebra (3rd Ed.) (Beijing: Higher Education Press) p160 (in Chinese) [王萼芳, 石生明 2005 高等代数 第三版 (北京: 高等教育出版社) 第160页]

    [25]

    Zhong Q H 2004 Modern Control Theory 2004 (Beijing: Higher Education Press) p142 (in Chinese) [钟秋海 2004 现代控制理论 (北京: 高等教育出版社) 第142页]

    [26]

    Liang H L 2015 Ph. D. Dissertation (Shanghai: Shanghai Jiao Tong University) (in Chinese) [梁海丽 2015 博士学位论文 (上海: 上海交通大学)]

    [27]

    Wang B, Ma R N, Wang G, Chen B 2015 J. Comput. Appl. 35 1820 (in Chinese) [王班, 马润年, 王刚, 陈波 2015 计算机应用 35 1820]

    [28]

    Brin S, Page L 1998 Computer Networks and ISDN Systems 30 107

    [29]

    Yao Z Q, Shang K K, Xu X K 2012 J. Univ. Shanghai Sci. Technol. 34 18 (in Chinese) [姚尊强, 尚可可, 许小可 2012 上海理工大学学报 34 18]

    [30]

    Dodds P S, Watts D J, Sabel C F 2003 PNAS 100 12516

    [31]

    Yuan M 2014 Acta Phys. Sin. 63 220501 (in Chinese) [袁铭 2014 物理学报 63 220501]

    [32]

    Zachary W W 1977 J. Anthropol. Res. 33 452

    [33]

    Pan Z F, Wang X F 2006 Acta Phys. Sin. 55 4058 (in Chinese) [潘灶烽, 汪小帆 2006 物理学报 55 4058]

    [34]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

  • [1]

    Zhao M, Zhou T, Wang B H, Wang W X 2005 Phys. Rev. E 72 057102

    [2]

    Zemanov L, Zhou C, Kurths J 2006 Physica D 224 202

    [3]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [4]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [5]

    Estrada E, Rodrguez-Velzquez J A 2005 Phys. Rev. E 71 056103

    [6]

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

    [7]

    L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [8]

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

    [9]

    Ruan Y R, Lao S Y, Wang J D, Bai L, Chen L D 2017 Acta Phys. Sin. 66 038902 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 陈立栋 2017 物理学报 66 038902]

    [10]

    Freeman L C, Borgatti S P, White D R 1991 Soc. Networks 13 141

    [11]

    Estrada E, Higham D J, Hatano N 2009 Physica A 388 764

    [12]

    Li Q, Zhou T, L L Y, Chen D B 2014 Physica A 404 47

    [13]

    Zhou Y B, Lei T, Zhou T 2011 Europhys. Lett. 94 48002

    [14]

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

    [15]

    Gao C, Wei D J, Hu Y, Mahadevan S, Deng Y 2013 Physica A 392 5490

    [16]

    Wang Y, Guo J L 2017 Acta Phys. Sin. 66 050201 (in Chinese) [王雨, 郭进利 2017 物理学报 66 050201]

    [17]

    L L, Zhang Y C, Chi H Y, Zhou T 2011 Plos One 6 e21202

    [18]

    Yan G, Zhou T, Wang J, Fu Z Q, Wang B 2005 Chin. Phys. Lett. 22 510

    [19]

    Brummitt C D, DSouza R M, Leicht E A 2012 Proceedings of the National Academy of Sciences of the United States of America 109 E680

    [20]

    Du W J, Yu J L, An X L, Ma C X 2015 Transport Research 1 14 (in Chinese) [杜文举, 俞建宁, 安新磊, 马昌喜 2015 交通运输研究 1 14]

    [21]

    Liu Y Y, Slotine J J, Barabasi A L 2011 Nature 473 167

    [22]

    Jia T, Barabsi A L 2013 Sci. Rep. 3 2354

    [23]

    Chen T P, Lu W L 2013 Theory of Coordination in Complex Networks (Beijing: Higher Education Press) p14 (in Chinese) [陈天平, 卢文联 2013 复杂网络协调性理论 (北京: 高等教育出版社) 第14 页]

    [24]

    Wang E F, Shi S M 2005 Advanced Algebra (3rd Ed.) (Beijing: Higher Education Press) p160 (in Chinese) [王萼芳, 石生明 2005 高等代数 第三版 (北京: 高等教育出版社) 第160页]

    [25]

    Zhong Q H 2004 Modern Control Theory 2004 (Beijing: Higher Education Press) p142 (in Chinese) [钟秋海 2004 现代控制理论 (北京: 高等教育出版社) 第142页]

    [26]

    Liang H L 2015 Ph. D. Dissertation (Shanghai: Shanghai Jiao Tong University) (in Chinese) [梁海丽 2015 博士学位论文 (上海: 上海交通大学)]

    [27]

    Wang B, Ma R N, Wang G, Chen B 2015 J. Comput. Appl. 35 1820 (in Chinese) [王班, 马润年, 王刚, 陈波 2015 计算机应用 35 1820]

    [28]

    Brin S, Page L 1998 Computer Networks and ISDN Systems 30 107

    [29]

    Yao Z Q, Shang K K, Xu X K 2012 J. Univ. Shanghai Sci. Technol. 34 18 (in Chinese) [姚尊强, 尚可可, 许小可 2012 上海理工大学学报 34 18]

    [30]

    Dodds P S, Watts D J, Sabel C F 2003 PNAS 100 12516

    [31]

    Yuan M 2014 Acta Phys. Sin. 63 220501 (in Chinese) [袁铭 2014 物理学报 63 220501]

    [32]

    Zachary W W 1977 J. Anthropol. Res. 33 452

    [33]

    Pan Z F, Wang X F 2006 Acta Phys. Sin. 55 4058 (in Chinese) [潘灶烽, 汪小帆 2006 物理学报 55 4058]

    [34]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

  • [1] Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [2] Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [3] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [4] Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong. Node importance measurement based on the degree and clustering coefficient information. Acta Physica Sinica, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [5] Wang Yu, Guo Jin-Li. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix. Acta Physica Sinica, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [6] Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng. Node importance based on the weighted K-order propagation number algorithm. Acta Physica Sinica, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [7] Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [8] Su Zhen, Gao Chao, Li Xiang-Hua. Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [9] Zhang Guo-Hua, Wang Bo, Sun Qi-Cheng, Wang Guang-Qian. Shear modulus of semi-flexible networks in two dimensions. Acta Physica Sinica, 2009, 58(9): 6549-6553. doi: 10.7498/aps.58.6549
    [10] Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [11] Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [12] Lin Yong, Fu Bai-Bai, Gao Zi-You, Li Shu-Bin, Wu Jian-Jun. The analysis of traffic congestion and dynamic propagation properties based on complex network. Acta Physica Sinica, 2011, 60(5): 050701. doi: 10.7498/aps.60.050701
    [13] Gao Zhong-Ke, Jin Ning-De, Yang Dan, Zhai Lu-Sheng, Du Meng. Complex networks from multivariate time series for characterizing nonlinear dynamics of two-phase flow patterns. Acta Physica Sinica, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [14] Li Zhao, Guo Yan-Hui, Xu Guo-Ai, Hu Zheng-Ming. Analysis of cascading dynamics in complex networks with an emergency recovery mechanism. Acta Physica Sinica, 2014, 63(15): 158901. doi: 10.7498/aps.63.158901
    [15] Duan Dong-Li, Zhan Ren-Jun. Evolution mechanism of node importance based on the information about cascading failures in complex networks. Acta Physica Sinica, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [16] Feng Wei, Gao Hong-Fen, Li Kai-Tai, Wei Gao-Feng. Stability and convergence analysis of incompatible numerical manifold method. Acta Physica Sinica, 2008, 57(2): 639-647. doi: 10.7498/aps.57.639
    [17] Wang Bing-Hong, Zhou Tao, Wang Wen-Xu, Li Ji, Jiang Pin-Qun. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
    [18] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [19] LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [20] Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
  • Citation:
Metrics
  • Abstract views:  1200
  • PDF Downloads:  381
  • Cited By: 0
Publishing process
  • Received Date:  24 October 2017
  • Accepted Date:  12 February 2018
  • Published Online:  05 May 2018

Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models

    Corresponding author: Huang Jian, nudtjHuang@hotmail.com
  • 1. College of Mechatronics Engineering and Automation, National University of Defense Technology, Changsha 410073, China

Abstract: Identifying the most important nodes is significant for investigating the robustness and vulnerability of complex network. A lot of methods based on network structure have been proposed, such as degree, K-shell and betweenness, etc. In order to identify the important nodes in a more reasonable way, both the network topologies and the characteristics of nodes should be taken into account. Even at the same location, the nodes with different characteristics have different importance. The topological structures and the characteristics of the nodes are considered in the complex network dynamics model. However, such methods are rarely explored and their applications are restricted. In order to identify the important nodes in undirected weighted networks, in this paper we propose a method based on dynamics model. Firstly, we introduce a way to construct the corresponding dynamics model for any undirected weighted network, and the constructed model can be flexibly adjusted according to the actual situation. It is proved that the constructed model is globally asymptotic stable. To measure the changes of the dynamic model state, the mean deviation and the variance are presented, which are the criteria to evaluate the importance of the nodes. Finally, disturbance test and destructive test are proposed for identifying the most important nodes. Each node is tested in turn, and then the important nodes are identified. If the tested node can recover from the damaged state, the disturbance test is used. If the tested node is destroyed completely, the destructive test is used. The method proposed in this paper is based on the dynamics model. The node importance is influenced by the network topologies and the characteristics of nodes in these two methods. In addition, the disturbance test and destructive test are used in different situations, forming a complementary advantage. So the method can be used to analyze the node importance in a more comprehensive way. Experiments are performed on the advanced research project agency networks, the undirected networks with symmetric structures, the social network, the Dobbs-Watts-Sabel networks and the Barrat-Barthelemy-Vespignani networks. If the nodes in the network have the same dynamic model, the network is considered to be the homogeneous network; otherwise, the network is heterogeneous network. And experiments can be divided into four categories, namely, the disturbance test, the destructive test on the homogeneous network, the disturbance test and the destructive test on the heterogeneous network. The experimental results show that the methods proposed in this paper are effective and credible.

Reference (34)

Catalog

    /

    返回文章
    返回