A model for optimal reinforcement of error- and attack-resilient clusters in networks under uncertainty

Hossein Dashti, Pavlo A. Krokhmal

Research output: Chapter in Book/Report/Conference proceedingChapter


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.

Original languageEnglish (US)
Title of host publicationSpringer Optimization and Its Applications
PublisherSpringer International Publishing
Number of pages21
StatePublished - 2017
Externally publishedYes

Publication series

NameSpringer Optimization and Its Applications
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'A model for optimal reinforcement of error- and attack-resilient clusters in networks under uncertainty'. Together they form a unique fingerprint.

Cite this