带恢复策略的复杂网络级联失效机理及鲁棒性研究
|
摘要
为研究复杂网络在遭遇随机故障或蓄意攻击时的鲁棒性,考虑节点具有恢复和重复失效等特征,构建故障节点概率传播模式下的级联失效模型.构建节点故障概率随故障次数增加而逐渐降低的故障概率函数,设计概率恢复(R)和阶段恢复(T)两种故障节点恢复策略,并针对ER、WS、NC和BA四类网络研究其恢复鲁棒性.仿真实验考虑模型中相关参数变化,揭示其对复杂网络级联失效过程中的鲁棒性影响,综合分析边鲁棒性和节点鲁棒性的性能权衡.仿真结果表明,在概率恢复策略下,随着恢复率的增大,4类网络级联失效的规模均能够实现有效降低;而在阶段恢复策略下,随着参数T值增加到不同阈值,4类网络鲁棒性指标在级联失效过程中均能够呈现出突变现象.
To study the robustness of complex networks while encountering random failure or deliberate attack, the cascading failure model based on probability propagation is constructed by considering the characteristics of repeated failures and recovery of nodes. In particular, we consider that the failure probability of node decreases with the increase of number of failures and the failure probability function is constructed accordingly. Then, two kinds of node recovery strategies(i.e., probability R and stage T) are proposed and implemented on ER random network, WS small-world network, nearest-neighbor coupled network and BA scale-free network, respectively, to test the network robustness of cascading failure model. Finally, simulation experiments are carried out and the parameters changes are considered to reveal their effects on robustness during cascading failure process. Additionally, performance tradeoff between edge robustness and node robustness is analyzed as well. The simulation results show that cascading failure scale of four types of network decreases with the increase of recovery rate. Under the stage recovery strategy, the network robustness index of four types of network shows a mutation phenomenon when the parameter T increases to a threshold.
To study the robustness of complex networks while encountering random failure or deliberate attack, the cascading failure model based on probability propagation is constructed by considering the characteristics of repeated failures and recovery of nodes. In particular, we consider that the failure probability of node decreases with the increase of number of failures and the failure probability function is constructed accordingly. Then, two kinds of node recovery strategies(i.e., probability R and stage T) are proposed and implemented on ER random network, WS small-world network, nearest-neighbor coupled network and BA scale-free network, respectively, to test the network robustness of cascading failure model. Finally, simulation experiments are carried out and the parameters changes are considered to reveal their effects on robustness during cascading failure process. Additionally, performance tradeoff between edge robustness and node robustness is analyzed as well. The simulation results show that cascading failure scale of four types of network decreases with the increase of recovery rate. Under the stage recovery strategy, the network robustness index of four types of network shows a mutation phenomenon when the parameter T increases to a threshold.
引文
[1]段东立,吴俊,邓宏钟,等.基于可调负载重分配的复杂网络级联失效模型[J].系统工程理论与实践,2013,33(1):203-208.(Duan D L,Wu J,Deng H Z,et al.Cascading failure model of complex networks based on tunable load redistribution[J].Systems Engineering—Theory&Practice,2013,33(1):203-208.)
[2]李钊,郭燕慧,徐国爱,等.复杂网络中带有应急恢复机理的级联动力学分析[J].物理学报,2014,63(15):158901.(Li Z,Guo Y H,Xu G A,et al.Analysis of cascading dynamic in complex networks with an emergency recovery mechanism[J].Acta Physica Sinical,2014,63(15):158901.)
[3]Wang J W,Rong L L.A model for cascading failure in scale-free networks with a breakdown probability[J].Physica A,2009,388(7):1289-1298.
[4]阮逸润,老松杨,王竣德,等.基于邻域相似度的复杂网络节点重要度评估算法[J].物理学报,2017,66(3):038902.(Ruan Y R,Lao S Y,Wang J D,et al.Node importance measurement based on neighborhood similarity in complex network[J].Acta Physica Sinical,2017,66(3):038902.)
[5]周漩,张凤鸣,周卫平,等.利用节点效率评估复杂网络功能鲁棒性[J].物理学报,2012,61(19):190201.(Zhou X,Zhang F M,Zhou W P,et al.Evaluating complex network functional robustness by node efficiency[J].ActaPhysica Sinical,2012,61(19):190201.)
[6]Barabasi A L,Bonabeau E.Scale-free networks[J].Science Americal,2003,288(5):60-69.
[7]Watts D J.The“new”science of networks[J].Annual Review of Sociology,2004,30(5):243-270.
[8]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:72-101.(Wang X F,Li X,Chen G R.Complex network theory and its application[M].Beijing:Tsinghua University Press,2006:72-101.
[9]Chen S M,Pang S P,Zou X Q.An LCOR model for suppressing cascading failure in weighted complex networks[J].Chinese Physics B,2013,22(5):626-631.
[10]王建伟,荣莉莉.基于负荷局域择优重新分配原则的复杂网络上的相继故障[J].物理学报,2009,58(6):3714-3721.(Wang J W,Rong L L.Cascading failures on complex networks based on the local preferential redistribution rule of the load[J].Acta Physica Sinical,2009,58(6):3714-3721.)
[11]王建伟,荣莉莉,王铎.基于节点局域特征的复杂网络上相继故障模型[J].管理科学学报,2010,13(8):42-50.(Wang J W,Rong L L,Wang D.Model for cascading failures on complex networks based on local characteristics of nodes[J].J of Management Sciences in China,2010,13(8):42-50.)
[12]Bao Z J,Cao Y J,Ding L J,et al.Synergetic behavior in the cascading failure propagation of scale-free coupled map lattices[J].Physica A,2008,387(23):5922-5929.
[13]Chen S M,Xu Y F,Nie S.Robustness of network controllability in cascading failure[J].Physica A,2017,471(1):536-539.
[14]Wu J J,Gao Z Y,Sun H J.Effects of the cascading failure on scale-free traffic networks[J].Physica A,2007,378(2):505-511.
[15]Sun H J,Gao Z Y.Dynamical behaviors of epidemics on scale-free networks with community structure[J].Physica A,2007,381(15):491-496.
[16]Liu J,Xiong Q Y,Shi X,et al.Robustness of complex networks with an improved breakdown probability against cascading failure[J].Physica A,2016,456(15):302-309.
[17]Grilo M,Fadigas I S,Miranda J G V,et al.Robustness in semantic networks based on cliques[J].Physica A,2017,472(15):94-102.
[18]Jiang Z Y,Ma J F,Shen Y L,et al.Effects of link-orientation methods on robustness against cascading failures in complex networks[J].Physica A,2016,457(1):1-7.
[19]Wang J W,Jiang C,Qian J F.Robustness of interdependent networks with different link patterns against cascading failure[J].Physica A,2014,393(1):535-541.
[20]Tang L,Jing K,He J,et al.Robustness of assemble supply chain networks by considering risk propagation and cascading failure[J].Physica A,2016,459(1):129-139.
[21]唐亮,何杰,靖可.关联供应链网络级联失效机理及鲁棒性研究[J].管理科学学报,2016,19(11):33-43.(Tang L,He J,Jing K.Cascading failure mechanism and robustness of interdependent supply chain networks[J].J of Management Sciences in China,2016,19(11):33-43.)
[22]肖延东,老松杨,侯绿林,等.基于节点负荷失效的网络可控性研究[J].物理学报,2013,62(18):180201.(Xiao Y D,Lao S Y,Hou L L,et al.Network controllability based on node overloaded failure[J].Acta Physica Sinical,2013,62(18):180201.
[23]丁超,姚宏,杜军,等.基于社团划分的复杂网络级联抗毁攻击策略[J].计算机应用,2014,(34)(6):1666-1667.(Ding C,Yao H,Du J,et al.Cascading invulnerability attack strategy of complex network via community detection[J].J of Computer Applications,2014,34(6):1666-1667.)
[24]王建伟,荣莉莉.面向相继故障的复杂网络上边袭击策略研究[J].系统工程学报,2011,26(1):1-8.(Wang J W,Rong L L.Study of cascading failure-oriented attack on the edges of complex networks[J].J of System Engineering,2011,26(1):1-8.)
[25]段东立,武小悦.基于可调负载重分配的无标度网络连锁效应分析[J].物理学报,2014,63(3):030501.(Duan D L,Wu X Y.Cascading failure of scale-free networks based on a tunable load redistribution model[J].Acta Physica Sinical,2014,63(3):030501.)
[26]王健,刘衍衍,张程,等.Internet级联动力学分析与建模[J].软件学报,2010,21(8):2050-2058.(Wang J,Liu Y Y,Zhang C,et al.Analyzing and modeling cascading dynamics if internet[J].J of Software,2010,21(8):2050-2058.)
[27]Gao J X,Buldyrev S V,Havlin S,et al.Robustness of a network formed by n interdependent networks with a one-to-one correspondence dependent nodes[J].Physical Review E,2012,85(6):036116.
[28]邓宏钟,吴俊,李勇.双层小世界网络中的级联失效模型与分析[J].计算机仿真,2008,25(10):150-153.(Deng H Z,Wu J,Li Y.Analysis of cascading failure model for two-layer small-world networks[J].Computer Simulation,2008,25(10):150-153.)
[2]李钊,郭燕慧,徐国爱,等.复杂网络中带有应急恢复机理的级联动力学分析[J].物理学报,2014,63(15):158901.(Li Z,Guo Y H,Xu G A,et al.Analysis of cascading dynamic in complex networks with an emergency recovery mechanism[J].Acta Physica Sinical,2014,63(15):158901.)
[3]Wang J W,Rong L L.A model for cascading failure in scale-free networks with a breakdown probability[J].Physica A,2009,388(7):1289-1298.
[4]阮逸润,老松杨,王竣德,等.基于邻域相似度的复杂网络节点重要度评估算法[J].物理学报,2017,66(3):038902.(Ruan Y R,Lao S Y,Wang J D,et al.Node importance measurement based on neighborhood similarity in complex network[J].Acta Physica Sinical,2017,66(3):038902.)
[5]周漩,张凤鸣,周卫平,等.利用节点效率评估复杂网络功能鲁棒性[J].物理学报,2012,61(19):190201.(Zhou X,Zhang F M,Zhou W P,et al.Evaluating complex network functional robustness by node efficiency[J].ActaPhysica Sinical,2012,61(19):190201.)
[6]Barabasi A L,Bonabeau E.Scale-free networks[J].Science Americal,2003,288(5):60-69.
[7]Watts D J.The“new”science of networks[J].Annual Review of Sociology,2004,30(5):243-270.
[8]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:72-101.(Wang X F,Li X,Chen G R.Complex network theory and its application[M].Beijing:Tsinghua University Press,2006:72-101.
[9]Chen S M,Pang S P,Zou X Q.An LCOR model for suppressing cascading failure in weighted complex networks[J].Chinese Physics B,2013,22(5):626-631.
[10]王建伟,荣莉莉.基于负荷局域择优重新分配原则的复杂网络上的相继故障[J].物理学报,2009,58(6):3714-3721.(Wang J W,Rong L L.Cascading failures on complex networks based on the local preferential redistribution rule of the load[J].Acta Physica Sinical,2009,58(6):3714-3721.)
[11]王建伟,荣莉莉,王铎.基于节点局域特征的复杂网络上相继故障模型[J].管理科学学报,2010,13(8):42-50.(Wang J W,Rong L L,Wang D.Model for cascading failures on complex networks based on local characteristics of nodes[J].J of Management Sciences in China,2010,13(8):42-50.)
[12]Bao Z J,Cao Y J,Ding L J,et al.Synergetic behavior in the cascading failure propagation of scale-free coupled map lattices[J].Physica A,2008,387(23):5922-5929.
[13]Chen S M,Xu Y F,Nie S.Robustness of network controllability in cascading failure[J].Physica A,2017,471(1):536-539.
[14]Wu J J,Gao Z Y,Sun H J.Effects of the cascading failure on scale-free traffic networks[J].Physica A,2007,378(2):505-511.
[15]Sun H J,Gao Z Y.Dynamical behaviors of epidemics on scale-free networks with community structure[J].Physica A,2007,381(15):491-496.
[16]Liu J,Xiong Q Y,Shi X,et al.Robustness of complex networks with an improved breakdown probability against cascading failure[J].Physica A,2016,456(15):302-309.
[17]Grilo M,Fadigas I S,Miranda J G V,et al.Robustness in semantic networks based on cliques[J].Physica A,2017,472(15):94-102.
[18]Jiang Z Y,Ma J F,Shen Y L,et al.Effects of link-orientation methods on robustness against cascading failures in complex networks[J].Physica A,2016,457(1):1-7.
[19]Wang J W,Jiang C,Qian J F.Robustness of interdependent networks with different link patterns against cascading failure[J].Physica A,2014,393(1):535-541.
[20]Tang L,Jing K,He J,et al.Robustness of assemble supply chain networks by considering risk propagation and cascading failure[J].Physica A,2016,459(1):129-139.
[21]唐亮,何杰,靖可.关联供应链网络级联失效机理及鲁棒性研究[J].管理科学学报,2016,19(11):33-43.(Tang L,He J,Jing K.Cascading failure mechanism and robustness of interdependent supply chain networks[J].J of Management Sciences in China,2016,19(11):33-43.)
[22]肖延东,老松杨,侯绿林,等.基于节点负荷失效的网络可控性研究[J].物理学报,2013,62(18):180201.(Xiao Y D,Lao S Y,Hou L L,et al.Network controllability based on node overloaded failure[J].Acta Physica Sinical,2013,62(18):180201.
[23]丁超,姚宏,杜军,等.基于社团划分的复杂网络级联抗毁攻击策略[J].计算机应用,2014,(34)(6):1666-1667.(Ding C,Yao H,Du J,et al.Cascading invulnerability attack strategy of complex network via community detection[J].J of Computer Applications,2014,34(6):1666-1667.)
[24]王建伟,荣莉莉.面向相继故障的复杂网络上边袭击策略研究[J].系统工程学报,2011,26(1):1-8.(Wang J W,Rong L L.Study of cascading failure-oriented attack on the edges of complex networks[J].J of System Engineering,2011,26(1):1-8.)
[25]段东立,武小悦.基于可调负载重分配的无标度网络连锁效应分析[J].物理学报,2014,63(3):030501.(Duan D L,Wu X Y.Cascading failure of scale-free networks based on a tunable load redistribution model[J].Acta Physica Sinical,2014,63(3):030501.)
[26]王健,刘衍衍,张程,等.Internet级联动力学分析与建模[J].软件学报,2010,21(8):2050-2058.(Wang J,Liu Y Y,Zhang C,et al.Analyzing and modeling cascading dynamics if internet[J].J of Software,2010,21(8):2050-2058.)
[27]Gao J X,Buldyrev S V,Havlin S,et al.Robustness of a network formed by n interdependent networks with a one-to-one correspondence dependent nodes[J].Physical Review E,2012,85(6):036116.
[28]邓宏钟,吴俊,李勇.双层小世界网络中的级联失效模型与分析[J].计算机仿真,2008,25(10):150-153.(Deng H Z,Wu J,Li Y.Analysis of cascading failure model for two-layer small-world networks[J].Computer Simulation,2008,25(10):150-153.)