基于相继故障信息的网络节点重要度演化机理分析

段东立; 战仁军

doi:10.7498/aps.63.068902

摘要

分析了过载机制下节点重要度的演化机理. 首先，在可调负载重分配级联失效模型基础上，根据节点失效后其分配范围内节点的负载振荡程度，提出了考虑级联失效局域信息的复杂网络节点重要度指标. 该指标具有两个特点：一是值的大小可以清晰地指出节点的失效后果；二是可以依据网络负载分配范围、负载分配均匀性、节点容量系数及网络结构特征分析节点重要度的演化情况. 然后，给出该指标的仿真算法，并推导了最近邻择优分配和全局择优分配规则下随机网络和无标度网络节点重要度的解析表达式. 最后，实验验证了该指标的有效性和可行性，并深入分析了网络中节点重要度的演化机理，即非关键节点如何演化成影响网络级联失效行为的关键节点.

关键词:

Abstract

This paper mainly focuses on the evolution mechanism of node importance based on the information about cascading failures. Firstly, a novel node importance indicator is proposed according to the load turbulence of each node in the redistribution range based on a tunable load redistribution model. The indicator has two characteristics: one is that the failure consequence of the considered node can be clearly pointed out by its value, and the other is that the evolution mechanism of node importance can be analyzed with the factors of load redistribution rule, node capacity, and structural characteristics of the network. Then, an evaluation algorithm is presented. The indicator analytic formulas of Erdös-Rényi networks and Barabási-Albert networks are also presented respectively with the neighbor preferential and global preferential allocation rules. The experiments demonstrate the effectiveness and feasibility of the indicators and its algorithm, with which we also analyze the node importance evolution mechanism in-depth, namely how the not-so-great nodes in structure turns into the critical nodes to trigger cascading failure in complex networks.

Keywords:

作者及机构信息

1.
武警工程大学装备工程学院, 西安 710008

基金项目: 国家自然科学基金（批准号：70771111，71031007）资助的课题.

Authors and contacts

1.
College of Equipment Engineering, Engineering University of Armed Police Force, Xi’an 710008, China

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 70771111, 71031007).

参考文献

[1]	Albert R, Jeong H, Barabási A L 2000 Nature 406 378
[2]	Wu J, Li Y, Zou A Q 2010 Chin. Phys. Lett. 27 068901
[3]	Yu H, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 020204 (in Chinese) [于会, 刘尊, 李勇军 2013 物理学报 62 020204]
[4]	Albert R, Jeong H, Barabási A L 1999 Nature 401 130
[5]	Freeman L C 1977 Sociometry 40 35
[6]	Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[7]	Comellas F, Gago S 2007 Linear Algebra Appl. 423 74
[8]	Mantrach A, Yen L, Callut J, Francoisse K, Shimbo M, Saerens M 2010 IEEE Trans. Pattern Anal. Mach. Intell. 32 1112
[9]	Estrada E, Rodríguez-Velázquez J A 2005 Phys. Rev. E 71 056103
[10]	Stevanovi D 2013 Phys. Rev. E 88 026801
[11]	Sabidussi G 1966 Psychometrika 31 581
[12]	An S H, Du Y B, Qu J L 2006 Chin. J. Manage. Sci. 14 106 (in Chinese) [安世虎, 都艺兵, 曲吉林 2006 中国管理科学 14 106]
[13]	Corley H W, Sha D Y 1982 Oper. Res. Lett. 1 157
[14]	Nardelli E, Proietti G, Widmayer P 2001 Inform. Proces. Lett. 79 81
[15]	Tan Y J, Wu J, Deng H Z 2006 Syst. Eng. Theory Pract. 26 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 26 79]
[16]	Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]
[17]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]
[18]	Yan G, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chin. Phys. Lett. 22 510
[19]	Borge-Holthoefer J, Rivero A, Moreno Y 2012 Phys. Rev. E 85 066123
[20]	Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[21]	Klemm K, Serrano M A, Eguíluz V M, San Miguel M 2012 Sci. Rep. 2 292
[22]	Aral S, Walker D 2012 Science 337 337
[23]	Liu J G, Wu Z X, Wang F 2007 Int. J. Mod. Phys. C 18 1087
[24]	Sergey V B, Roni P, Gerald P, Eugene S H, Shlomo H 2010 Nature 464 1025
[25]	Chen S M, Pang S P, Zou X Q 2013 Chin. Phys. B 22 058901
[26]	Hu K, Hu T, Tang Y 2010 Chin. Phys. B 19 080206
[27]	Zheng J F, Gao Z Y, Fu B B, Li F 2009 Chin. Phys. B 18 4754
[28]	Wang J W, Rong L L 2009 Acta Phys. Sin. 58 3714 (in Chinese) [王建伟, 荣莉莉 2009 物理学报 58 3714]
[29]	Wu Z H, Fang H J 2008 Chin. Phys. Lett. 25 3822
[30]	Wang J W, Rong L L 2008 Chin. Phys. Lett. 25 3826
[31]	Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102
[32]	Xia Y X, Fan J, Hill D 2010 Physica A 389 1281
[33]	Crucitti P, Latora V, Marchiori M 2004 Phys. Rev. E 69 045104
[34]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[35]	Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103
[36]	Wu J J, Gao Z Y, Sun H J 2007 Physica A 378 505
[37]	Bao Z J, Cao Y J, Ding L J, Wang G Z 2009 Physica A 388 4491
[38]	Wang J W, Rong L L 2009 Safety Sci. 47 1332
[39]	Wang J W, Rong L L 2009 Physica A 388 1289
[40]	Duan D L, Wu J, Deng H Z, Sha F, Wu X Y, Tan Y J 2013 Syst. Eng. Theory Pract. 33 203 (in Chinese) [段东立, 吴俊, 邓宏钟, 沙飞, 武小悦, 谭跃进 2013 系统工程理论与实践 33 203]
[41]	Barabási A L, Albert R 1999 Science 286 509

施引文献

[1]	Albert R, Jeong H, Barabási A L 2000 Nature 406 378
[2]	Wu J, Li Y, Zou A Q 2010 Chin. Phys. Lett. 27 068901
[3]	Yu H, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 020204 (in Chinese) [于会, 刘尊, 李勇军 2013 物理学报 62 020204]
[4]	Albert R, Jeong H, Barabási A L 1999 Nature 401 130
[5]	Freeman L C 1977 Sociometry 40 35
[6]	Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[7]	Comellas F, Gago S 2007 Linear Algebra Appl. 423 74
[8]	Mantrach A, Yen L, Callut J, Francoisse K, Shimbo M, Saerens M 2010 IEEE Trans. Pattern Anal. Mach. Intell. 32 1112
[9]	Estrada E, Rodríguez-Velázquez J A 2005 Phys. Rev. E 71 056103
[10]	Stevanovi D 2013 Phys. Rev. E 88 026801
[11]	Sabidussi G 1966 Psychometrika 31 581
[12]	An S H, Du Y B, Qu J L 2006 Chin. J. Manage. Sci. 14 106 (in Chinese) [安世虎, 都艺兵, 曲吉林 2006 中国管理科学 14 106]
[13]	Corley H W, Sha D Y 1982 Oper. Res. Lett. 1 157
[14]	Nardelli E, Proietti G, Widmayer P 2001 Inform. Proces. Lett. 79 81
[15]	Tan Y J, Wu J, Deng H Z 2006 Syst. Eng. Theory Pract. 26 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 26 79]
[16]	Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]
[17]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]
[18]	Yan G, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chin. Phys. Lett. 22 510
[19]	Borge-Holthoefer J, Rivero A, Moreno Y 2012 Phys. Rev. E 85 066123
[20]	Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
[21]	Klemm K, Serrano M A, Eguíluz V M, San Miguel M 2012 Sci. Rep. 2 292
[22]	Aral S, Walker D 2012 Science 337 337
[23]	Liu J G, Wu Z X, Wang F 2007 Int. J. Mod. Phys. C 18 1087
[24]	Sergey V B, Roni P, Gerald P, Eugene S H, Shlomo H 2010 Nature 464 1025
[25]	Chen S M, Pang S P, Zou X Q 2013 Chin. Phys. B 22 058901
[26]	Hu K, Hu T, Tang Y 2010 Chin. Phys. B 19 080206
[27]	Zheng J F, Gao Z Y, Fu B B, Li F 2009 Chin. Phys. B 18 4754
[28]	Wang J W, Rong L L 2009 Acta Phys. Sin. 58 3714 (in Chinese) [王建伟, 荣莉莉 2009 物理学报 58 3714]
[29]	Wu Z H, Fang H J 2008 Chin. Phys. Lett. 25 3822
[30]	Wang J W, Rong L L 2008 Chin. Phys. Lett. 25 3826
[31]	Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102
[32]	Xia Y X, Fan J, Hill D 2010 Physica A 389 1281
[33]	Crucitti P, Latora V, Marchiori M 2004 Phys. Rev. E 69 045104
[34]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[35]	Albert R, Albert I, Nakarado G L 2004 Phys. Rev. E 69 025103
[36]	Wu J J, Gao Z Y, Sun H J 2007 Physica A 378 505
[37]	Bao Z J, Cao Y J, Ding L J, Wang G Z 2009 Physica A 388 4491
[38]	Wang J W, Rong L L 2009 Safety Sci. 47 1332
[39]	Wang J W, Rong L L 2009 Physica A 388 1289
[40]	Duan D L, Wu J, Deng H Z, Sha F, Wu X Y, Tan Y J 2013 Syst. Eng. Theory Pract. 33 203 (in Chinese) [段东立, 吴俊, 邓宏钟, 沙飞, 武小悦, 谭跃进 2013 系统工程理论与实践 33 203]
[41]	Barabási A L, Albert R 1999 Science 286 509

计量

文章访问数: 5901
PDF下载量: 1020
被引次数: 0

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

搜索

留言板