Detecting resilient structures in stochastic networks: A two‐stage stochastic optimization approach. Issue 2 (30th January 2017)

• Record Type: Journal Article
• Authors: Rysz, Maciej; Krokhmal, Pavlo A.; Pasiliao, Eduardo L.
• Is Part Of: Networks. Volume 69:Issue 2(2017)
• Page Start: 189
• Page End: 204
• Publication Date: 2017-01-30
• Subjects: maximum subgraph problem -- stochastic graphs -- resilience of subgraphs -- two‐stage stochastic optimization -- combinatorial branch‐and‐bound algorithm -- stochastic maximum clique problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21727
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : We propose a two‐stage stochastic programming framework for designing or identifying "resilient, " or "reparable" structures in graphs whose topology may undergo a stochastic transformation. The reparability of a subgraph satisfying a given property is defined in terms of a budget constraint, which allows for a prescribed number of vertices to be added to or removed from the subgraph so as to restore its structural properties after the observation of random changes to the graph's set of edges. A two‐stage stochastic programming model is formulated and is shown to be N P ‐complete for a broad range of graph‐theoretical properties that the resilient subgraph is required to satisfy. A general combinatorial branch‐and‐bound algorithm is developed, and its computational performance is illustrated on the example of a two‐stage stochastic maximum clique problem. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 189–204 2017