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

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.