A Model for Optimal Reinforcement of Error- and Attack-Resilient Clusters in Networks Under Uncertainty

Hossein Dashti () and Pavlo A. Krokhmal ()
Additional contact information
Hossein Dashti: University of Arizona
Pavlo A. Krokhmal: University of Arizona

A chapter in Optimization Methods and Applications, 2017, pp 97-117 from Springer

Abstract: Abstract Network robustness issues are crucial in a variety of application areas, such as energy, defense, communications, and so on. Unpredictable failures of network components (nodes and/or edges) can be caused by a variety of factors, including man-made and natural disruptions, which may significantly affect or inhibit network’s functionality. In many situations, one of the key robustness requirements is that every pair of nodes is connected, with the number of intermediate links between them being as small as possible. Additionally, if nodes in a cluster are connected by several different paths, such a cluster will be more robust with respect to potential network component disruptions. In this work, we study the problem of identifying error- and attack-resilient clusters in graphs, particularly power grids. It is assumed that the cluster represents a R-robust 2-club, which is defined as a subgraph with at least R node/edge disjoint paths connecting each pair of nodes, where each path consists of at most two edges. Uncertain information manifests itself in the form of stochastic number of errors/attacks that could happen in different nodes. If one can reinforce the network components against future threats, the goal is to determine optimal reinforcements that would yield a cluster with minimum risk of disruptions. A combinatorial branch-and-bound algorithm is developed and compared with an equivalent mathematical programming approach on simulated and real-world networks.

Keywords: Stochastic Number; Conditional Value At Risk (CVaR); Mixed-integer Nonlinear Problem (MINLP); Distinct Shortest Paths; CVaR Risk Measure (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-68640-0_6

Ordering information: This item can be ordered from
http://www.springer.com/9783319686400

DOI: 10.1007/978-3-319-68640-0_6

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().