-
定量分析识别复杂网络中的重要节点对于研究复杂网络鲁棒性和脆弱性意义重大，当前基于网络结构的节点重要性评估方法成果丰富，而基于复杂网络动力学模型的节点重要性评估方法较少.针对无向加权网络，本文首先提出了构建其对应的复杂网络动力学模型的方法，并证明了该类复杂网络动力学模型是大范围内一致渐近稳定的；然后建立了复杂网络动力学模型的偏离均值和基于偏离均值的方差两级节点重要性评估标准；最后给出了扰动测试和破坏测试两种基于复杂网络动力学模型的节点重要性评估方法.基于复杂网络动力学模型的节点重要性评估方法不仅结合了网络拓扑结构信息，同时又结合了节点自身的特性，所以评价结果更为全面.将这两种方法用于ARPA （advanced research project agency）网络、对称无向加权网络、社交网络、Dobbs-Watts-Sabel网络和Barrat-Barthelemy-Vespignani网络的重要节点评估，并与已有的复杂网络节点重要性分析方法进行比较，证明了所提出方法的有效性.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.
-
Keywords:
- complex network /
- node importance /
- network dynamics /
- stability analysis
[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
计量
- 文章访问数: 9852
- PDF下载量: 661
- 被引次数: 0
下载:
