Reducing power grid cascading failure propagation by minimizing algebraic connectivity in edge addition

Supaporn LONAPALAWONG; Jiangzhe YAN; Jiayu LI; Deshi YE; Wei CHEN; Yong TANG; Yanhao HUANG; Can WANG

doi:10.1631/FITEE.2000596

Your Location：

Home >

Browse articles >

Reducing power grid cascading failure propagation by minimizing algebraic connectivity in edge addition

Regular Papers | Updated：2022-03-28

- Reducing power grid cascading failure propagation by minimizing algebraic connectivity in edge addition
  Enhanced Publication
- 通过最小化边缘添加中的代数连接度来减少电网级联故障传播
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 3, Pages: 382-397(2022)
- Affiliations：
  
  1.State Key Lab of CAD & CG, Zhejiang University, Hangzhou310058, China
  2.College of Computer Science and Technology, Zhejiang University, Hangzhou310058, China
  3.School of Mathematical Science, Zhejiang University, Hangzhou310058, China
  4.State Key Laboratory of Power Grid Safety and Energy Conservation, China Electric Power Research Institute, Beijing100192, China
- Author bio：
  
  [ "Supaporn LONAPALAWONG, first author of this invited paper, is currently a PhD candidate in the College of Computer Science and Technology at Zhejiang University, China. Her research interests include data mining and visual analytics." ]
  [ "Can WANG, corresponding author of this invited paper, is currently an associate professor in the College of Computer Science and Technology at Zhejiang University, China. He received his BS degree in Economics in 1995, and his MS and PhD degrees in Computer Science in 2003 and 2009, respectively, from Zhejiang University. His research interests include information retrieval, data mining, machine learning, and information accessibility. He has published over 30 research papers in SCI indexed journals and top international conferences. He is the recipient of AAAI Outstanding Paper Award (2012). He is also the coach of ACM/ICPC team at Zhejiang University, which won the 35th ACM/ICPC World Final Champion in Orlando, USA, in 2011." ]
- Funds：
- DOI：10.1631/FITEE.2000596
  CLC： TP393
- Received：02 November 2020，
  
  Accepted：07 March 2021，
  
  Published Online：24 January 2022，
  
  Published：0 March 2022
- Accepted：
Scan QR Code
Supaporn LONAPALAWONG, Jiangzhe YAN, Jiayu LI, et al. Reducing power grid cascading failure propagation by minimizing algebraic connectivity in edge addition[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(3): 382-397.
DOI：

Supaporn LONAPALAWONG, Jiangzhe YAN, Jiayu LI, et al. Reducing power grid cascading failure propagation by minimizing algebraic connectivity in edge addition[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(3): 382-397. DOI： 10.1631/FITEE.2000596.

摘要

在各种情况下分析网络鲁棒性通常被认为是一个具有挑战性的问题。应对故障的鲁棒性是大型动态网络系统（如电力网、运输系统、通信系统和计算机网络）的基本特性之一。由于网络的多样性和复杂性，人们已提出许多拓扑特征以捕获系统特定属性。对于电网，通过拓扑设计提高网络结构鲁棒性是常见做法。然而，大多数现有方法集中于局部网络度量，例如节点连接度和边连接度，而非从全局视角看待电网中的级联传播。本文使用信息量大的全局度量代数连接度，因为它对谱图的全局连接度敏感。我们通过最小化代数连接度的增量以减少电网中的平均传播。提出一种基于拓扑的贪婪策略，以优化电网鲁棒性。为评估网络鲁棒性，使用MATCASC计算电网中级联故障中断的平均传播。实验结果表明，所提方法优于现有技术。

Abstract

Analyzing network robustness under various circumstances is generally regarded as a challenging problem. Robustness against failure is one of the essential properties of large-scale dynamic network systems such as power grids

transportation systems

communication systems

and computer networks. Due to the network diversity and complexity

many topological features have been proposed to capture specific system properties. For power grids

a popular process for improving a network’s structural robustness is via the topology design. However

most of existing methods focus on localized network metrics

such as node connectivity and edge connectivity

which do not encompass a global perspective of cascading propagation in a power grid. In this paper

we use an informative global metric algebraic connectivity because it is sensitive to the connectedness in a broader spectrum of graphs. Our process involves decreasing the average propagation in a power grid by minimizing the increase in its algebraic connectivity. We propose a topology-based greedy strategy to optimize the robustness of the power grid. To evaluate the network robustness

we calculate the average propagation using MATCASC to simulate cascading line outages in power grids. Experimental results illustrate that our proposed method outperforms existing techniques.

关键词

Keywords

references

Anghel M , Werley KA , Motter AE , 2007 . Stochastic model for power grid dynamics . 40 th Annual Hawaii Int Conf on System Sciences , p. 1 - 10 . doi: 10.1109/HICSS.2007.500 http://doi.org/10.1109/HICSS.2007.500

Azzolin A , Dueñas-Osorio L , Cadini F , et al. , 2018 . Electrical and topological drivers of the cascading failure dynamics in power transmission networks . Reliab Eng Syst Saf , 175 : 196 - 206 . doi: 10.1016/j.ress.2018.03.011 http://doi.org/10.1016/j.ress.2018.03.011

Bigdeli A , Tizghadam A , Leon-Garcia A , 2009 . Comparison of network criticality, algebraic connectivity, and other graph metrics . Proc 1 st Annual Workshop on Simplifying Complex Network for Practitioners , p. 1 - 6 . doi: 10.1145/1610304.1610308 http://doi.org/10.1145/1610304.1610308

Bompard E , Estebsari A , Huang T , et al. , 2016 . A framework for analyzing cascading failure in large interconnected power systems: a post-contingency evolution simulator . Int J Electr Power Energy Syst , 81 : 12 - 21 . doi: 10.1016/j.ijepes.2016.02.010 http://doi.org/10.1016/j.ijepes.2016.02.010

Carreras BA , Lynch VE , Dobson I , et al. , 2002 . Critical points and transitions in an electric power transmission model for cascading failure blackouts . Chaos , 12 : 985 - 994 . doi: 10.1063/1.1505810 http://doi.org/10.1063/1.1505810

Carreras BA , Newman DE , Dobson I , et al. , 2004 . Evidence for self-organized criticality in a time series of electric power system blackouts . IEEE Trans Circ Syst I , 51 ( 9 ): 1733 - 1740 . doi: 10.1109/TCSI.2004.834513 http://doi.org/10.1109/TCSI.2004.834513

Chen J , Thorp JS , Dobson I , 2005 . Cascading dynamics and mitigation assessment in power system disturbances via a hidden failure model . Int J Electr Power Energy Syst , 27 ( 4 ): 318 - 326 . doi: 10.1016/j.ijepes.2004.12.003 http://doi.org/10.1016/j.ijepes.2004.12.003

Chen Q , Mili L , 2013 . Composite power system vulnerability evaluation to cascading failures using importance sampling and antithetic variates . IEEE Trans Power Syst , 28 ( 3 ): 2321 - 2330 . doi: 10.1109/TPWRS.2013.2238258 http://doi.org/10.1109/TPWRS.2013.2238258

Correa-Henao GJ , Yusta-Loyo JM , 2015 . Representation of electric power systems by complex networks with applications to risk vulnerability assessment . DYNA , 82 ( 192 ): 68 - 77 . doi: 10.15446/dyna.v82n192.48574 http://doi.org/10.15446/dyna.v82n192.48574

Correa-Henao GJ , Yusta JM , Lacal-Arántegui R , 2013 . Using interconnected risk maps to assess the threats faced by electricity infrastructures . Int J Crit Infrastr Prot , 6 ( 3-4 ): 197 - 216 . doi: 10.1016/j.ijcip.2013.10.002 http://doi.org/10.1016/j.ijcip.2013.10.002

Cuadra L , Salcedo-Sanz S , Del Ser J , et al. , 2015 . A critical review of robustness in power grids using complex networks concepts . Energies , 8 ( 9 ): 9211 - 9265 . doi: 10.3390/en8099211 http://doi.org/10.3390/en8099211

Dey P , Mehra R , Kazi F , et al. , 2016 . Impact of topology on the propagation of cascading failure in power grid . IEEE Trans Smart Grid , 7 ( 4 ): 1970 - 1978 . doi: 10.1109/TSG.2016.2558465 http://doi.org/10.1109/TSG.2016.2558465

Dobson I , Carreras BA , Newman DE , 2005 . Branching process models for the exponentially increasing portions of cascading failure blackouts . Proc 38 th Annual Hawaii Int Conf on System Sciences , p. 1 - 10 . doi: 10.1109/HICSS.2005.125 http://doi.org/10.1109/HICSS.2005.125

Dobson I , Wierzbicki KR , Carreras BA , et al. , 2006 . An estimator of propagation of cascading failure . Proc 39 th Annual Hawaii Int Conf on System Sciences , p. 1 - 10 . doi: 10.1109/HICSS.2006.54 http://doi.org/10.1109/HICSS.2006.54

Dobson I , Kim J , Wierzbicki KR , 2010 . Testing branching process estimators of cascading failure with data from a simulation of transmission line outages . Risk Anal , 30 ( 4 ): 650 - 662 . doi: 10.1111/j.1539-6924.2010.01369.x http://doi.org/10.1111/j.1539-6924.2010.01369.x

Ellens W , Spieksma F , van Mieghem P , et al. , 2011 . Effective graph resistance . Linear Algebra Appl , 435 ( 10 ): 2491 - 2506 . doi: 10.1016/j.laa.2011.02.024 http://doi.org/10.1016/j.laa.2011.02.024

Eppstein MJ , Hines PDH , 2012 . A “random chemistry” algorithm for identifying collections of multiple contingencies that initiate cascading failure . IEEE Trans Power Syst , 27 ( 3 ): 1698 - 1705 . doi: 10.1109/TPWRS.2012.2183624 http://doi.org/10.1109/TPWRS.2012.2183624

Fiedler M , 1973 . Algebraic connectivity of graphs . Czech Math J , 23 ( 2 ): 298 - 305 . doi: 10.21136/CMJ.1973.101168 http://doi.org/10.21136/CMJ.1973.101168

Ghosh A , Boyd S , 2006 . Growing well-connected graphs . Proc 45 th IEEE Conf on Decision and Control , p. 6605 - 6611 . doi: 10.1109/CDC.2006.377282 http://doi.org/10.1109/CDC.2006.377282

Gu YJ , Yang HY , Sun W , et al. , 2020 . Hierarchical control of DC microgrids robustness and smartness . CSEE J Power Energy Syst , 6 ( 2 ): 384 - 393 . doi: 10.17775/CSEEJPES.2017.00920 http://doi.org/10.17775/CSEEJPES.2017.00920

Guan ZH , Chen L , Qian TH , 2011 . Routing in scale-free networks based on expanding betweenness centrality . Phys A , 390 ( 6 ): 1131 - 1138 . doi: 10.1016/j.physa.2010.10.002 http://doi.org/10.1016/j.physa.2010.10.002

Holme P , Kim BJ , Yoon CN , et al. , 2002 . Attack vulnerability of complex networks . Phys Rev E , 65 : 056109 . doi: 10.1103/PhysRevE.65.056109 http://doi.org/10.1103/PhysRevE.65.056109

Jamakovic A , Uhlig S , 2007 . Influence of the network structure on robustness . 15 th IEEE Int Conf on Networks , p. 278 - 283 . doi: 10.1109/ICON.2007.4444099 http://doi.org/10.1109/ICON.2007.4444099

Ji XP , Wang B , Liu DC , et al. , 2016 . Improving interdependent networks robustness by adding connectivity links . Phys A , 444 : 9 - 19 . doi: 10.1016/j.physa.2015.10.010 http://doi.org/10.1016/j.physa.2015.10.010

Jiang ZY , Liang MG , Guo DC , 2011 . Enhancing network performance by edge addition . Int J Mod Phys C , 22 ( 11 ): 1211 - 1226 . doi: 10.1142/S0129183111016841 http://doi.org/10.1142/S0129183111016841

Koç Y , Verma T , Araujo NAM , et al. , 2013 . MATCASC: a tool to analyse cascading line outages in power grids . IEEE Int Workshop on Intelligent Energy Systems , p. 143 - 148 . doi: 10.1109/IWIES.2013.6698576 http://doi.org/10.1109/IWIES.2013.6698576

Koç Y , Warnier M , van Mieghem P , et al. , 2014 . The impact of the topology on cascading failures in a power grid model . Phys A , 402 : 169 - 179 . doi: 10.1016/j.physa.2014.01.056 http://doi.org/10.1016/j.physa.2014.01.056

Laszka A , Buttyán L , Szeszlér D , 2013 . Designing robust network topologies for wireless sensor networks in adversarial environments . Pervas Mob Comput , 9 ( 4 ): 546 - 563 . doi: 10.1016/j.pmcj.2012.05.001 http://doi.org/10.1016/j.pmcj.2012.05.001

Li CH , Xue YS , 2019 . Effects of cascading failure intervals on synchronous stability . Int J Elect Power Energy Syst , 106 : 502 - 510 . doi: 10.1016/j.ijepes.2018.10.036 http://doi.org/10.1016/j.ijepes.2018.10.036

Liu J , Zhang HX , Qiao W , et al. , 2019 . DC (optimal) power flow-based models for simulation and mitigation of overload cascading failures . North American Power Symp , p. 1 - 5 . doi: 10.1109/NAPS46351.2019.9000269 http://doi.org/10.1109/NAPS46351.2019.9000269

Liu W , Sirisena H , Pawlikowski K , et al. , 2009 . Utility of algebraic connectivity metric in topology design of survivable networks . 7 th Int Workshop on Design of Reliable Communication Networks , p. 131 - 138 . doi: 10.1109/DRCN.2009.5340016 http://doi.org/10.1109/DRCN.2009.5340016

Liu ZY , Zhang HP , Smith P , et al. , 2012 . Optimizing weighted graph topology for robust network information dissemination . Proc 51 st IEEE Conf on Decision and Control , p. 3329 - 3334 . doi: 10.1109/CDC.2012.6426594 http://doi.org/10.1109/CDC.2012.6426594

Marsden PV , 2015 . Network Centrality, Measures of . In: International Encyclopedia of the Social & Behavioral Sciences ( 2 nd Ed.). Elsevier , Oxford , p. 532 - 539 . doi: 10.1016/B978-0-08-097086-8.43115-6 http://doi.org/10.1016/B978-0-08-097086-8.43115-6

Mohar B , Alavi Y , Chartrand G , et al. , 1991 . The Laplacian spectrum of graphs . Graph Theory Combin Appl , 2 : 5364 .

Moussawi A , Derzsy N , Lin X , et al. , 2017 . Limits of predictability of cascading overload failures in spatially-embedded networks with distributed flows . Sci Rep , 7 : 11729 . doi: 10.1038/s41598-017-11765-1 http://doi.org/10.1038/s41598-017-11765-1

Pahwa S , Hodges A , Scoglio C , et al. , 2012 . Topological analysis and mitigation strategies for cascading failures in power grid networks . https://arxiv.org/abs/1212.5620 https://arxiv.org/abs/1212.5620

Peng GS , Wu J , 2016 . Optimal network topology for structural robustness based on natural connectivity . Phys A , 443 : 212 - 220 . doi: 10.1016/j.physa.2015.09.023 http://doi.org/10.1016/j.physa.2015.09.023

Pizzuti C , Socievole A , van Mieghem P , 2020 . Comparative network robustness evaluation of link attacks . Complex Networks and Their Applications VIII . Studies in Computational Intelligence , p. 735 - 746 . doi: 10.1007/978-3-030-36687-2_61 http://doi.org/10.1007/978-3-030-36687-2_61

Qi JJ , Dobson I , Mei SW , 2013 . Towards estimating the statistics of simulated cascades of outages with branching processes . IEEE Trans Power Syst , 28 ( 3 ): 3410 - 3419 . doi: 10.1109/TPWRS.2013.2243479 http://doi.org/10.1109/TPWRS.2013.2243479

Rei AM , Leite da Silva AM , Jardim JL , et al. , 2000 . Static and dynamic aspects in bulk power system reliability evaluations . IEEE Trans Power Syst , 15 ( 1 ): 189 - 195 . doi: 10.1109/59.852120 http://doi.org/10.1109/59.852120

Rezaei P , Hines P , Eppstein M , 2015 . Estimating cascading failure risk with random chemistry . IEEE Power and Energy Society General Meeting , p. 1 . doi: 10.1109/PESGM.2015.7285613 http://doi.org/10.1109/PESGM.2015.7285613

Saleh M , Esa Y , Mohamed A , 2018 . Applications of complex network analysis in electric power systems . Energies , 11 ( 6 ): 1381 . doi: 10.3390/en11061381 http://doi.org/10.3390/en11061381

Song JJ , Cotilla-Sanchez E , Ghanavati G , et al. , 2016 . Dynamic modeling of cascading failure in power systems . IEEE Trans Power Syst , 31 ( 3 ): 2085 - 2095 . doi: 10.1109/TPWRS.2015.2439237 http://doi.org/10.1109/TPWRS.2015.2439237

Spiewak R , Soltan S , Forman Y , et al. , 2018 . A study of cascading failures in real and synthetic power grid topologies . Netw Sci , 6 ( 4 ): 448 - 468 . doi: 10.1017/nws.2018.14 http://doi.org/10.1017/nws.2018.14

Sydney A , Scoglio C , Gruenbacher D , 2013 . Optimizing algebraic connectivity by edge rewiring . Appl Math Comput , 219 ( 10 ): 5465 - 5479 . doi: 10.1016/j.amc.2012.11.002 http://doi.org/10.1016/j.amc.2012.11.002

Tang Y , Huang YH , Wang HZ , et al. , 2018 . Framework for artificial intelligence analysis in large-scale power grids based on digital simulation . CSEE J Power Energy Syst , 4 ( 4 ): 459 - 468 . doi: 10.17775/CSEEJPES.2018.01010 http://doi.org/10.17775/CSEEJPES.2018.01010

van Mieghem P , 2010 . Graph Spectra for Complex Networks . Cambridge University Press , Cambridge, UK . doi: 10.1017/CBO9780511921681 http://doi.org/10.1017/CBO9780511921681

Wang JW , Rong LL , 2009 . Cascade-based attack vulnerability on the US power grid . Saf Sci , 47 ( 10 ): 1332 - 1336 . doi: 10.1016/j.ssci.2009.02.002 http://doi.org/10.1016/j.ssci.2009.02.002

Wang JX , Wei JD , Zhu YC , et al. , 2020 . The reliability and operational test system of a power grid with large-scale renewable integration . CSEE J Power Energy Syst , 6 ( 3 ): 704 - 711 . doi: 10.17775/CSEEJPES.2017.01300 http://doi.org/10.17775/CSEEJPES.2017.01300

Wang YZ , Baldick R , 2014 . Interdiction analysis of electric grids combining cascading outage and medium-term impacts . IEEE Trans Power Syst , 29 ( 5 ): 2160 - 2168 . doi: 10.1109/TPWRS.2014.2300695 http://doi.org/10.1109/TPWRS.2014.2300695

Wang ZF , Scaglione A , Thomas RJ , 2012 . A Markov-transition model for cascading failures in power grids . 45 th Hawaii Int Conf on System Sciences , p. 2115 - 2124 . doi: 10.1109/HICSS.2012.63 http://doi.org/10.1109/HICSS.2012.63

Wei P , Chen L , Sun D , 2014 . Algebraic connectivity maximization of an air transportation network: the flight routes’ addition/deletion problem . Trans Res E , 61 : 13 - 27 . doi: 10.1016/j.tre.2013.10.008 http://doi.org/10.1016/j.tre.2013.10.008

Wei XG , Gao SB , Huang T , et al. , 2019 . Identification of two vulnerability features: a new framework for electrical networks based on the load redistribution mechanism of complex networks . Complexity , 2019 : 3531209 . doi: 10.1155/2019/3531209 http://doi.org/10.1155/2019/3531209

Zhang X , Tse CK , 2015 . Assessment of robustness of power systems from a network perspective . IEEE J Emerg Sel Top Circ Syst , 5 ( 3 ): 456 - 464 . doi: 10.1109/JETCAS.2015.2462152 http://doi.org/10.1109/JETCAS.2015.2462152

Zheng YX , Zhao SH , Liu Y , et al. , 2017 . Weighted algebraic connectivity maximization for optical satellite networks . IEEE Access , 5 : 6885 - 6893 . doi: 10.1109/ACCESS.2017.2697818 http://doi.org/10.1109/ACCESS.2017.2697818

Views

113

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

An artificial intelligence based method for evaluating power grid node importance using network embedding and support vector regression

Related Author

Hui-fang WANG

Chen-yu ZHANG

Dong-yang LIN

Ben-teng HE

Related Institution

Department of Electrical Engineering, Zhejiang University

State Grid Jiangsu Electric Power Engineering Consulting Co., Ltd.

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰