Vulnerability Evaluation of Networks to Multiple Failures Based on Critical Nodes and Links

In this chapter, we consider the vulnerability evaluation of a given network, composed by a set of nodes and a set of links, based on the connectivity still provided by the network if its critical elements fail simultaneously. This evaluation requires to solve the optimization problem of identifying the set of network elements (either nodes or links) that are the most critical in the sense that if they are removed from the network, the resulting connectivity is minimized. The chapter describes both exact methods based on integer linear programming and centrality-based heuristics. Although exact methods are preferable since they can provide optimal solutions, they do not scale for very large problem instances since the optimization problem is of combinatorial nature. In such cases, heuristics are alternative methods able to provide solutions that might be non-optimal. The chapter addresses separately the cases aiming to identify the set of critical nodes and the set of critical links. Computational results are provided enabling the comparison between exact methods and centrality-based heuristics in terms of solution optimality.