搜索

x

留言板

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

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

基于复杂网络动力学模型的无向加权网络节点重要性评估

孔江涛 黄健 龚建兴 李尔玉

引用本文:
Citation:

基于复杂网络动力学模型的无向加权网络节点重要性评估

孔江涛, 黄健, 龚建兴, 李尔玉

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
导出引用
  • 定量分析识别复杂网络中的重要节点对于研究复杂网络鲁棒性和脆弱性意义重大,当前基于网络结构的节点重要性评估方法成果丰富,而基于复杂网络动力学模型的节点重要性评估方法较少.针对无向加权网络,本文首先提出了构建其对应的复杂网络动力学模型的方法,并证明了该类复杂网络动力学模型是大范围内一致渐近稳定的;然后建立了复杂网络动力学模型的偏离均值和基于偏离均值的方差两级节点重要性评估标准;最后给出了扰动测试和破坏测试两种基于复杂网络动力学模型的节点重要性评估方法.基于复杂网络动力学模型的节点重要性评估方法不仅结合了网络拓扑结构信息,同时又结合了节点自身的特性,所以评价结果更为全面.将这两种方法用于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.
      通信作者: 黄健, nudtjHuang@hotmail.com
      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] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [2] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [3] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [4] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [5] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [7] 段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [8] 李钊, 郭燕慧, 徐国爱, 胡正名. 复杂网络中带有应急恢复机理的级联动力学分析. 物理学报, 2014, 63(15): 158901. doi: 10.7498/aps.63.158901
    [9] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [10] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [11] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [12] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [13] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [14] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [15] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [16] 李树彬, 吴建军, 高自友, 林勇, 傅白白. 基于复杂网络的交通拥堵与传播动力学分析. 物理学报, 2011, 60(5): 050701. doi: 10.7498/aps.60.050701
    [17] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [18] 孙其诚, 张国华, 王博, 王光谦. 半柔性网络剪切模量的计算. 物理学报, 2009, 58(9): 6549-6553. doi: 10.7498/aps.58.6549
    [19] 魏高峰, 李开泰, 冯 伟, 高洪芬. 非协调数值流形方法的稳定性和收敛性分析. 物理学报, 2008, 57(2): 639-647. doi: 10.7498/aps.57.639
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  5744
  • PDF下载量:  527
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-10-24
  • 修回日期:  2018-02-12
  • 刊出日期:  2018-05-05

基于复杂网络动力学模型的无向加权网络节点重要性评估

  • 1. 国防科技大学机电工程与自动化学院, 长沙 410073
  • 通信作者: 黄健, nudtjHuang@hotmail.com

摘要: 定量分析识别复杂网络中的重要节点对于研究复杂网络鲁棒性和脆弱性意义重大,当前基于网络结构的节点重要性评估方法成果丰富,而基于复杂网络动力学模型的节点重要性评估方法较少.针对无向加权网络,本文首先提出了构建其对应的复杂网络动力学模型的方法,并证明了该类复杂网络动力学模型是大范围内一致渐近稳定的;然后建立了复杂网络动力学模型的偏离均值和基于偏离均值的方差两级节点重要性评估标准;最后给出了扰动测试和破坏测试两种基于复杂网络动力学模型的节点重要性评估方法.基于复杂网络动力学模型的节点重要性评估方法不仅结合了网络拓扑结构信息,同时又结合了节点自身的特性,所以评价结果更为全面.将这两种方法用于ARPA (advanced research project agency)网络、对称无向加权网络、社交网络、Dobbs-Watts-Sabel网络和Barrat-Barthelemy-Vespignani网络的重要节点评估,并与已有的复杂网络节点重要性分析方法进行比较,证明了所提出方法的有效性.

English Abstract

参考文献 (34)

目录

    /

    返回文章
    返回