Graph algorithms for preventing cascading failures in networks

Pei Duo Yu*, Chee Wei Tan, Hung-Lin Fu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Cascading failures in critical networked infrastructures that result even from a single source of failure often lead to rapidly widespread outages as witnessed in the 2013 Northeast blackout in northern America. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. An optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the spread of cascading failure. Computationally fast distributed message-passing algorithms are developed to solve this problem. Global convergence and the optimality of the algorithm are proved using graph theoretic analysis. In particular, we illustrate how the poset-constrained graph algorithms can be designed to address the trade-off between complexity and optimality.

Original languageEnglish
Title of host publication2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-6
Number of pages6
ISBN (Electronic)9781538605790
DOIs
StatePublished - 21 May 2018
Event52nd Annual Conference on Information Sciences and Systems, CISS 2018 - Princeton, United States
Duration: 21 Mar 201823 Mar 2018

Publication series

Name2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018

Conference

Conference52nd Annual Conference on Information Sciences and Systems, CISS 2018
CountryUnited States
CityPrinceton
Period21/03/1823/03/18

Keywords

  • Cascading failure
  • graph theory
  • large-scale optimization
  • message-passing algorithms
  • viral spreading

Fingerprint Dive into the research topics of 'Graph algorithms for preventing cascading failures in networks'. Together they form a unique fingerprint.

Cite this