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
Country/TerritoryUnited 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