复杂网络中的级联失效研究进展

doi:10.3976/j.issn.1002-4026.20230179

摘要/Abstract

摘要：

随着网络科学的发展和复杂系统理论的兴起,学者们开始对复杂网络的结构和动力学特性展开深入研究。在复杂网络动力学特征中,级联失效作为复杂网络动力学特征中重要的研究领域之一,描述了一个系统或过程中的一个故障或错误导致其他相关组件或环节的连锁反应性故障。学者们针对复杂网络中的级联失效提出了多种级联失效模型和恢复策略。本文对级联失效的发生机理进行了分析,总结了国内外针对复杂网络中级联失效的研究成果,并概括了应对级联失效的恢复策略,同时指出了现有研究存在的问题与不足之处,为未来的研究提供了一定的思路。

关键词: 级联失效, 复杂网络, 多层网络, 传播特性, 恢复策略, 渗流, 网络鲁棒性

Abstract:

With the development of network science and the emergence of complex systems theory, scholars have embarked on in-depth research on the structural and dynamic properties of complex networks. Among the dynamic properties of complex networks, cascading failures, as one of the most important research areas, describe a situation where a fault or error in a system or process leads to the failures of other related components or links. Various models and recovery strategies have been proposed for cascading failures in complex networks. This study analyzes the mechanisms of cascading failures, provides a comprehensive summary on the development of domestic and international cascading failure in complex networks, outlines the recovery strategies for addressing cascading failures, and highlights the existing issues and shortcomings in current research, providing valuable insights for future studies.

Key words: cascading failure, complex networks, multilayer networks, propagation properties, recovery strategies, percolation, network robustness

中图分类号:

N945.17

张渡淯, 吴建军, 杨欣, 马智傲, 朱天雷. 复杂网络中的级联失效研究进展[J]. 山东科学, 2024, 37(2): 85-96.

ZHANG Duyu, WU Jianjun, YANG Xin, MA Zhi’ao, ZHU Tianlei. Research progress on cascading failures in complex networks[J]. Shandong Science, 2024, 37(2): 85-96.

图/表 4

图1

表1

图2

图3

参考文献 79

[1]	BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. DOI: 10.1126/science.286.5439.509. pmid: 10521342
[2]	WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393: 440-442. DOI: 10.1038/30918.
[3]	GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826. DOI: 10.1073/pnas.122653799. pmid: 12060727
[4]	曹一家, 陈晓刚, 孙可. 基于复杂网络理论的大型电力系统脆弱线路辨识[J]. 电力自动化设备, 2006, 26(12): 1-5. DOI: 10.3969/j.issn.1006-6047.2006.12.001.
[5]	吴建军, 李树彬. 基于复杂网络的城市交通系统复杂性概述[J]. 山东科学, 2009, 22(4): 68-73.
[6]	吴晋峰, 任瑞萍, 韩立宁, 等. 中国航空国际网络结构特征及其对入境旅游的影响[J]. 经济地理, 2012, 32(5): 147-152. DOI: 10.15957/j.cnki.jjdl.2012.05.025.
[7]	HINTON G E, SALAKHUTDINOV R R. Reducing the dimensionality of data with neural networks[J]. Science, 2006, 313(5786): 504-507. DOI: 10.1126/science.1127647. pmid: 16873662
[8]	韩利文, 陈善军, 董榕, 等. 网络药理学在中药复杂作用模式研究中的应用进展[J]. 山东科学, 2021, 34(6): 22-31. DOI: 10.3976/j.issn.1002-4026.2021.06.004.
[9]	SUN H J, ZHAO H, WU JJ. A robust matching model of capacity to defense cascading failure on complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2008, 387(25): 6431-6435. DOI: 10.1016/j.physa.2008.07.028.
[10]	MASSEY G W. The impact of installing power factor improvement capacitors: an overview and case study[C]// Proceedings of Rural Electric Power Conference. Fort Worth, TX, USA. IEEE, 2002: C4. DOI: 10.1109/REPCON.1996.495245.
[11]	WU J J, GAO Z Y, SUN H J, et al. Congestion in different topologies of traffic networks[J]. Europhysics Letters, 2006, 74(3): 560-566. DOI: 10.1209/epl/i2005-10551-x.
[12]	LI D H, WANG Q, ZHANG X, et al. Predicting the cascading failure propagation path in complex networks based on attention-LSTM neural networks[C]// 2023 IEEE International Symposium on Circuits and Systems (ISCAS). Monterey: IEEE, 2023: 1-4. DOI: 10.1109/ISCAS46773.2023.10181599.
[13]	JONES D T, KNOPMAN D S, GUNTER J L, et al. Cascading network failure across the Alzheimer’s disease spectrum[J]. Brain, 2016, 139(2): 547-562. DOI: 10.1093/brain/awv338.
[14]	高自友, 吴建军. 出行者博弈、网络结构与城市交通系统复杂性[J]. 复杂系统与复杂性科学, 2010, 7(4): 55-64. DOI: 10.13306/j.1672-3813.2010.04.006.
[15]	REIS S D S, HU Y Q, BABINO A, et al. Avoiding catastrophic failure in correlated networks of networks[J]. Nature Physics, 2014, 10: 762-767. DOI: 10.1038/nphys3081.
[16]	REN W D, WU J J, ZHANG X, et al. A stochastic model of cascading failure dynamics in communication networks[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018, 65(5): 632-636. DOI: 10.1109/TCSII.2018.2822049.
[17]	CUMELLES J, LORDAN O, SALLAN J M. Cascading failures in airport networks[J]. Journal of Air Transport Management, 2021, 92: 102026. DOI: 10.1016/j.jairtraman.2021.102026.
[18]	陈志龙, 郭平, 蒋银华, 等. 计算机网络级联失效建模与分析[J]. 后勤工程学院学报, 2012, 28(4): 85-90. DOI: 10.3969/j.issn.1672-7843.2012.04.015.
[19]	吴杏, 曾康铭. 基于熵方法的计算机网络脆弱性检测和优化[J]. 微电子学与计算机, 2016, 33(7): 98-101. DOI: 10.19304/j.cnki.issn1000-7180.2016.07.021.
[20]	黄英艺, 金淳. 物流基础设施网络级联失效下的抗毁性分析[J]. 控制与决策, 2014, 29(9):1711-1714.
[21]	LIU H R, DONG M R, YIN R R, et al. Cascading failure in the wireless sensor scale-free networks[J]. Chinese Physics B, 2015, 24(5): 050506. DOI: 10.1088/1674-1056/24/5/050506.
[22]	DAVID A E, GJORGIEV B, SANSAVINI G. Quantitative comparison of cascading failure models for risk-based decision making in power systems[J]. Reliability Engineering & System Safety, 2020, 198: 106877. DOI: 10.1016/j.ress.2020.106877.
[23]	YI C Q, BAO Y Y, JIANG J C, et al. Mitigation strategy against cascading failures on social networks[J]. China Communications, 2014, 11(8): 37-46. DOI: 10.1109/CC.2014.6911086.
[24]	XU J, WANG X F. Cascading failures in scale-free coupled map lattices[C]// 2005 IEEE International Symposium on Circuits and Systems (ISCAS). Kobe: IEEE, 2005: 3395-3398. DOI: 10.1109/ISCAS.2005.1465357.
[25]	ZHANG L, XU M, WANG S A. Quantifying bus route service disruptions under interdependent cascading failures of a multimodal public transit system based on an improved coupled map lattice model[J]. Reliability Engineering & System Safety, 2023, 235: 109250. DOI: 10.1016/j.ress.2023.109250.
[26]	MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102. DOI: 10.1103/physreve.66.065102.
[27]	HOLME P, KIM B J. Vertex overload breakdown in evolving networks[J]. Physical Review E, 2002, 65(6): 066109. DOI: 10.1103/physreve.65.066109.
[28]	MORENO Y, PASTOR-SATORRAS R, VÁZQUEZ A, et al. Critical load and congestion instabilities in scale-free networks[J]. Europhysics Letters, 2003, 62(2): 292-298. DOI: 10.1209/epl/i2003-00140-7.
[29]	CRUCITTI P, LATORA V, MARCHIORI M. Model for cascading failures in complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69(4Pt 2): 045104. DOI: 10.1103/PhysRevE.69.045104.
[30]	BAK P, TANG C, WIESENFELD K. Self-organized criticality: an explanation of the 1/f noise[J]. Physical Review Letters, 1987, 59(4): 381-384. DOI: 10.1103/PhysRevLett.59.381. pmid: 10035754
[31]	张晓莉, 严广乐. 基于沙堆模型的股市脆性[J]. 哈尔滨工业大学学报, 2009, 41(10): 269-271. DOI: 10.3321/j.issn:0367-6234.2009.10.060.
[32]	姚令侃, 黄艺丹, 杨庆华. 地震触发崩塌滑坡自组织临界性研究[J]. 四川大学学报(工程科学版), 2010, 42(5): 33-43. DOI: 10.15961/j.jsuese.2010.05.012.
[33]	DOBSON I, CARRERAS B A, NEWMAN D E. A probabilistic loading-dependent model of cascading failure and possible implications for blackouts[C]// 36th Annual Hawaii International Conference on System Sciences, 2003. Proceedings of the. Big Island: IEEE, 2003: 10. DOI: 10.1109/HICSS.2003.1173909.
[34]	KANEKO K. Period-doubling of kink-antikink patterns,quasiperiodicity in antiferro-like structures and spatial intermittency in coupled logistic lattice:towards a prelude of a field-theory of chaos[J]. Progress of Theoretical Physics, 1984, 72(3): 480-486. DOI: 10.1143/PTP.72.480.
[35]	WANG X F, XU J. Cascading failures in coupled map lattices[J]. Physical Review E, 2004, 70(5):056113. doi: 10.1103/PhysRevE.70.056113
[36]	WATTS D J. A simple model of global cascades on random networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(9): 5766-5771. DOI: 10.1073/pnas.082090499. pmid: 16578874
[37]	MORENO Y, GÓMEZ J B, PACHECO A F. Instability of scale-free networks under node-breaking avalanches[J]. Europhysics Letters, 2002, 58(4): 630-636. DOI: 10.1209/epl/i2002-00442-2.
[38]	XIA Y X, FAN J, HILL D. Cascading failure in Watts-Strogatz small-world networks[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(6): 1281-1285. DOI: 10.1016/j.physa.2009.11.037.
[39]	MIRZASOLEIMAN B, BABAEI M, JALILI M, et al. Cascaded failures in weighted networks[J]. Physical Review E, 2011, 84(4): 046114. DOI: 10.1103/physreve.84.046114.
[40]	ZHAO J C, LI D Q, SANHEDRAI H, et al. Spatio-temporal propagation of cascading overload failures in spatially embedded networks[J]. Nature Communications, 2016, 7: 10094. DOI: 10.1038/ncomms10094. pmid: 26754065
[41]	谢丰, 程苏琦, 陈冬青, 等. 基于级联失效的复杂网络抗毁性[J]. 清华大学学报(自然科学版), 2011, 51(10): 1252-1257. DOI: 10.16511/j.cnki.qhdxxb.2011.10.001.
[42]	CARRERAS B A, LYNCH V E, DOBSON I, et al. Critical points and transitions in an electric power transmission model for cascading failure blackouts[J]. Chaos, 2002, 12(4): 985-994. DOI: 10.1063/1.1505810. pmid: 12779622
[43]	WU J J, GAO Z Y, SUN H J. Effects of the cascading failures on scale-free traffic networks[J]. Physica A: Statistical Mechanics and Its Applications, 2007, 378(2): 505-511. DOI: 10.1016/j.physa.2006.12.003.
[44]	WU J J, SUN H J, GAO Z Y. Cascading failures on weighted urban traffic equilibrium networks[J]. Physica A: Statistical Mechanics and Its Applications, 2007, 386(1): 407-413. DOI: 10.1016/j.physa.2007.08.034.
[45]	SUN L S, HUANG Y C, CHEN Y Y, et al. Vulnerability assessment of urban rail transit based on multi-static weighted method in Beijing, China[J]. Transportation Research Part A: Policy and Practice, 2018, 108: 12-24. DOI: 10.1016/j.tra.2017.12.008.
[46]	LU Q C, ZHANG L, XU P C, et al. Modeling network vulnerability of urban rail transit under cascading failures: a coupled map lattices approach[J]. Reliability Engineering & System Safety, 2022, 221: 108320. DOI: 10.1016/j.ress.2022.108320.
[47]	YI C Q, BAO Y Y, JIANG J C, et al. Modeling cascading failures with the crisis of trust in social networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 436: 256-271. DOI: 10.1016/j.physa.2015.05.030.
[48]	马亚男, 李莹. 商业银行集团客户成员企业信用风险传导仿真研究[J]. 商业研究, 2016(12): 96-101. DOI: 10.13902/j.cnki.syyj.2016.12.013.
[49]	DE ARRUDA G F, RODRIGUES F A, MORENO Y. Fundamentals of spreading processes in single and multilayer complex networks[J]. Physics Reports, 2018, 756:1-59. DOI: 10.1016/i.physrep.2018.06.007.
	DE ARRUDA G F, RODRIGUES F A, MORENO Y. Fundamentals of spreading processes in single and multilayer complex networks[J]. Physics Reports, 2018, 756: 1-59. DOI: 10.1016/j.physrep.2018.06.007.
[50]	ALETA A, MELONI S, MORENO Y. A Multilayer perspective for the analysis of urban transportation systems[J]. Scientific Reports, 2017, 7: 44359. DOI: 10.1038/srep44359. pmid: 28295015
[51]	ALETA A, MORENO Y. Multilayer networks in a nutshell[J]. Annual Review of Condensed Matter Physics, 2019, 10: 45-62. DOI: 10.1146/annurev-conmatphys-031218-013259.
[52]	DE DOMENICO M. More is different in real-world multilayer networks[J]. Nature Physics, 2023, 19: 1247-1262. DOI: 10.1038/s41567-023-02132-1.
[53]	WANG Z Y, CHEN G, LIU L, et al. Cascading risk assessment in power-communication interdependent networks[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 540: 120496. DOI: 10.1016/j.physa.2019.01.065.
[54]	VESPIGNANI A. Complex networks: the fragility of interdependency[J]. Nature, 2010, 464(7291): 984-985. DOI: 10.1038/464984a.
[55]	BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464: 1025-1028. DOI: 10.1038/nature08932.
[56]	GAO J X, BULDYREV S V, STANLEY H E, et al. Networks formed from interdependent networks[J]. Nature Physics, 2012, 8: 40-48. DOI: 10.1038/nphys2180.
[57]	SHAO J, BULDYREV S V, HAVLIN S, et al. Cascade of failures in coupled network systems with multiple support-dependence relations[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2011, 83(3 Pt 2): 036116. DOI: 10.1103/PhysRevE.83.036116.
[58]	LI W, BASHAN A, BULDYREV S V, et al. Cascading failures in interdependent lattice networks: the critical role of the length of dependency links[J]. Physical Review Letters, 2012, 108(22): 228702. DOI: 10.1103/PhysRevLett.108.228702.
[59]	BAXTER G J, DOROGOVTSEV S N, GOLTSEV A V, et al. Avalanche collapse of interdependent networks[J]. Physical Review Letters, 2012, 109(24): 248701. DOI: 10.1103/PhysRevLett.109.248701.
[60]	LIU R R, JIA C X, LAI Y C. Asymmetry in interdependence makes a multilayer system more robust against cascading failures[J]. Physical Review E, 2019, 100: 052306. DOI: 10.1103/PhysRevE.100.052306.
[61]	HAN H Y, YANG R N. Improvement on load-induced cascading failure in asymmetrical interdependent networks: modeling and analysis[J]. Mathematical Problems in Engineering, 2015, 2015: 194568. DOI: 10.1155/2015/194568.
[62]	ROSATO V, ISSACHAROFF L, TIRITICCO F, et al. Modelling interdependent infrastructures using interacting dynamical models[J]. International Journal of Critical Infrastructures, 2008, 4(1/2): 63. DOI: 10.1504/ijcis.2008.016092.
[63]	ZHANG L, WEN H Y, LU J, et al. Exploring cascading reliability of multi-modal public transit network based on complex networks[J]. Reliability Engineering & System Safety, 2022, 221: 108367. DOI: 10.1016/j.ress.2022.108367.
[64]	RAHNAMAY-NAEINI M, HAYAT M M. Cascading failures in interdependent infrastructures: an interdependent markov-chain approach[J]. IEEE Transactions on Smart Grid, 2016, 7(4): 1997-2006. DOI: 10.1109/TSG.2016.2539823.
[65]	吴建军. 城市交通网络拓扑结构复杂性研究[D]. 北京: 北京交通大学, 2008.
[66]	SCHNEIDER C M, MOREIRA A A, ANDRADE J S Jr, et al. Mitigation of malicious attacks on networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2011, 108(10): 3838-3841. DOI: 10.1073/pnas.1009440108. pmid: 21368159
[67]	KOÇ Y, WARNIER M, KOOIJ R E, et al. An entropy-based metric to quantify the robustness of power grids against cascading failures[J]. Safety Science, 2013, 59: 126-134. DOI: 10.1016/j.ssci.2013.05.006.
[68]	ZHANG Y F, NG S T. Robustness of urban railway networks against the cascading failures induced by the fluctuation of passenger flow[J]. Reliability Engineering & System Safety, 2022, 219: 108227. DOI: 10.1016/j.ress.2021.108227.
[69]	周琴, 徐桂琼. 基于动态级联失效的开发者协作网络鲁棒性研究[J/OL]. 复杂系统与复杂性科学.[2023-12-07]. http://kns.cnki.net/kcms/detail/37.1402.N.20231207.1017.006.html.
[70]	MAJDANDZIC A, PODOBNIK B, BULDYREV S V, et al. Spontaneous recovery in dynamical networks[J]. Nature Physics, 2014, 10: 34-38. DOI: 10.1038/nphys2819.
[71]	MOTTER A E. Cascade control and defense in complex networks[J]. Physical Review Letters, 2004, 93(9): 098701. DOI: 10.1103/PhysRevLett.93.098701.
[72]	LIU C R, LI D Q, FU B W, et al. Modeling of self-healing against cascading overload failures in complex networks[J]. Europhysics Letters, 2014, 107(6): 68003. DOI: 10.1209/0295-5075/107/68003.
[73]	ZHANG Y R, ARENAS A, YAĞAN O. Cascading failures in interdependent systems under a flow redistribution model[J]. Physical Review E, 2018, 97: 022307. DOI: 10.1103/PhysRevE.97.022307.
[74]	OUYANG M, DUEÑAS-OSORIO L, MIN X. A three-stage resilience analysis framework for urban infrastructure systems[J]. Structural Safety, 2012, 36/37: 23-31. DOI: 10.1016/j.strusafe.2011.12.004.
[75]	WANG J W. Mitigation strategies on scale-free networks against cascading failures[J]. Physica A: Statistical Mechanics and Its Applications, 2013, 392(9): 2257-2264. DOI: 10.1016/j.physa.2013.01.013.
[76]	WANG J W, RONG L L. Robustness of the western United States power grid under edge attack strategies due to cascading failures[J]. Safety Science, 2011, 49(6): 807-812. DOI: 10.1016/j.ssci.2010.10.003.
[77]	STIPPINGER M, KERTÉSZ J. Enhancing resilience of interdependent networks by healing[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 416: 481-487. DOI: 10.1016/j.physa.2014.08.069.
[78]	LA ROCCA C E, STANLEY H E, BRAUNSTEIN L A. Strategy for stopping failure cascades in interdependent networks[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 508: 577-583. DOI: 10.1016/j.physa.2018.05.154.
[79]	唐亮, 焦鹏, 李纪康, 等. 带恢复策略的复杂网络级联失效机理及鲁棒性研究[J]. 控制与决策, 2018, 33(10): 1841-1850. DOI: 10.13195/j.kzyjc.2017.0728.

发生机理	机理定义	机理特点
网络拓扑结构	复杂网络通常具有复杂的拓扑结构,包括小世界网络、无标度网络等。这些网络结构具有高度的连通性和鲁棒性,但也存在脆弱性。当一个节点或边故障时,其相邻节点或连边可能受到影响,从而引发级联失效	网络拓扑结构复杂,具有高度的连通性和鲁棒性,但也存在脆弱性,容易引发级联失效^[20-21]
动态耦合和反馈效应	复杂网络中的节点和连边通常相互耦合,并且存在着反馈效应。当一个节点或边故障时,其故障信息可能通过网络传播并影响其他节点。同时,其他节点的响应和调整可能会反过来影响故障节点,形成正反馈循环,导致级联失效的扩散	节点和连边相互耦合,存在反馈效应,容易形成正反馈循环,导致级联失效的扩散^[22-23]
网络动力学和系统失衡	复杂网络中的节点和连边通常具有自适应和动态调整的特性。当一个节点或连边故障时,它可能会破坏网络的平衡状态,引发系统的失衡。失衡状态可能导致其他节点或连边的过载或不稳定,从而引发级联失效	节点和连边具有自适应和动态调整的特性,故障可能会破坏网络平衡状态,引发系统失衡,导致级联失效^[24-25]