標題: Averting Cascading Failures in Networked Infrastructures: Poset-Constrained Graph Algorithms
作者: Yu, Pei-Duo
Tan, Chee Wei
Fu, Hung-Lin
交大名義發表
應用數學系
National Chiao Tung University
Department of Applied Mathematics
關鍵字: Cascading failure;viral spreading;graph theory and algorithms;large-scale stochastic optimization;message-passing algorithms;approximation algorithm;network centrality
公開日期: 1-Aug-2018
摘要: 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.
URI: http://dx.doi.org/10.1109/JSTSP.2018.2844813
http://hdl.handle.net/11536/147958
ISSN: 1932-4553
DOI: 10.1109/JSTSP.2018.2844813
期刊: IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING
Volume: 12
起始頁: 733
結束頁: 748
Appears in Collections:Articles