Vulnerability and robustness of networked infrastructures: beyond typical graph-based measures

The issue of vulnerability and robustness in networked systems can be addressed by several methods. The most widely used are based on a set of centrality and connectivity measures from network theory which basically relate vulnerability to the loss of efficiency caused by the removal of some nodes and edges. Another related view is given by the analysis of the spectra of the adjacency and Laplacian matrices of the graph associated to the networked system.

The main contribution of this paper is the introduction of a new set of vulnerability metrics given by the distance between the probability distribution of node-node distances between the original network and that resulting from the removal of nodes/edges. Two such probabilistic measures have been analysed: Jensen-Shannon (JS) divergence and Wasserstein (WST) distance, aka the Earth-Mover distance: this name comes from its informal interpretation as the minimum energy cost of moving and transforming a pile of dirt in the shape of one probability distribution to the shape of the other distribution. The cost is quantified by the amount of dirt moved times the moving distance. The Wasserstein distance can be traced back to the works of Gaspard Monge in 1761 and Lev Kantorovich in 1942. Wasserstein distances are generally well defined and provide an interpretable distance metric between distributions. Computing Wasserstein distances requires in general the solution of a constrained linear optimization problem which is, when the support of the probability distributions is multidimensional, very large.

An advantage of the Wasserstein distance is that, under quite general conditions, it is a differentiable function of the parameters of the distributions which makes possible its use to assess the sensitivity of the network robustness to distributional perturbations. The computational results related to two real-life water distribution networks confirm that the value of the distances JS and WST is strongly related to the criticality of the removed edges. Both are more discriminating, at least for water distribution networks, than efficiency-based and spectral measures. A general methodological scheme has been developed connecting different modelling and computational elements, concepts and analysis tools, to create an analysis framework suitable for analysing robustness. This modelling and algorithmic framework can also support the analysis of other networked infrastructures among which power grids, gas distribution and transit networks.