Critical nodes in interdependent networks with deterministic and probabilistic cascading failures

We consider optimization problems of identifying critical nodes in coupled interdependent networks, that is, choosing a subset of nodes whose deletion causes the maximum network fragmentation (quantified by an appropriate metric) in the presence of deterministic or probabilistic cascading failure propagations. We use two commonly considered network fragmentation metrics: total number of disabled nodes and total number of disabled pair-wise connectivities. First, we discuss computational complexity issues and develop linear mixed integer programming (MIP) formulations for the corresponding optimization problems in the deterministic case. We then extend these problems to the case with probabilistic failure propagations using Conditional Value-at-Risk measure. We develop a scenario-based linear MIP model and propose an exact Markov chain-based algorithm to solve these problems. Finally, we perform a series of computational experiments on synthetic and semi-synthetic networks and discuss some interesting insights that illustrate the properties of the proposed models.