Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph Algorithms

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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. The ensuing problem of containing future cascading failures by placement of protection or monitoring nodes in the network is complicated by the uncertainty of the failure source and the missing observation of how the cascading might unravel, be it the past cascading failures or the future ones. This paper examines the problem of minimizing the outage when a cascading failure from a single source occurs. A stochastic optimization problem is formulated where a limited number of protection nodes, when placed strategically in the network to mitigate systemic risk, can minimize the expected spread of cascading failure. We propose the vaccine centrality, which is a network centrality based on the partially ordered sets (poset) characteristics of the stochastic program and distributed message-passing, to design efficient approximation algorithms with provable approximation ratio guarantees. In particular, we illustrate how the vaccine centrality and the poset-constrained graph algorithms can be designed to tradeoff between complexity and optimality, as illustrated through a series of numerical experiments. This paper points toward a general framework of network centrality as statistical inference to design rigorous graph analytics for statistical problems in networks.

Original languageEnglish
Article number8374945
Pages (from-to)733-748
Number of pages16
JournalIEEE Journal on Selected Topics in Signal Processing
Issue number4
StatePublished - 1 Aug 2018


  • approximation algorithm
  • Cascading failure
  • graph theory and algorithms
  • large-scale stochastic optimization
  • message-passing algorithms
  • network centrality
  • viral spreading

Fingerprint Dive into the research topics of 'Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph Algorithms'. Together they form a unique fingerprint.

Cite this