Network Vulnerability Analysis in Wasserstein Spaces

The main contribution of this paper is the proposal of a new family of vulnerability measures based on a probabilistic representation framework in which the network and its components are modelled as discrete probability distributions. The resulting histograms are embedded in a space endowed with a metric given by the Wasserstein distance. This representation enables the synthesis of a set of discrete distributions through a barycenter and the clustering of distributions. We show that analyzing the networks as discrete probability distributions in the Wasserstein space enables the definition of a new family of vulnerability measures and the assessment of the criticality of each component. Computational results on real-life networks confirm the validity of our basic assumption that distributional representation can capture the topological information embedded in a network graph and yield more meaningful metrics than vulnerability measures based on average values. The computation of the Wasserstein distance is equivalent to the solution of a min-flow problem: its computational complexity has limited its diffusion outside the imaging science community. To avoid this computational bottleneck in this paper, we focus on a statistical approach that drastically reduces the computational hurdles. This approach has been implemented in a software tool HistDAWass. The linear complexity of this approach has also enabled the analysis of large-scale networks.