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.

Ponti, A., Irpino, A., Candelieri, A., Bosio, A., Giordani, I., Archetti, F. (2022). Network Vulnerability Analysis in Wasserstein Spaces. In Learning and Intelligent Optimization 16th International Conference, LION 16, Milos Island, Greece, June 5–10, 2022, Revised Selected Papers (pp.263-277). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-031-24866-5_20].

Network Vulnerability Analysis in Wasserstein Spaces

Ponti, A
;
Candelieri, A;Bosio, A;Giordani, I;Archetti, F
2022

Abstract

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.
paper
Network analysis; Vulnerability; Wasserstein distance;
English
16th International Conference on Learning and Intelligent Optimization, LION 16 2022 - 5 June 2022 through 10 June 2022
2022
Simos, D; Rasskazova, V; Archetti, F; Kotsireas, I; Pardalos, P
Learning and Intelligent Optimization 16th International Conference, LION 16, Milos Island, Greece, June 5–10, 2022, Revised Selected Papers
978-3-031-24865-8
5-feb-2023
2022
13621 LNCS
263
277
none
Ponti, A., Irpino, A., Candelieri, A., Bosio, A., Giordani, I., Archetti, F. (2022). Network Vulnerability Analysis in Wasserstein Spaces. In Learning and Intelligent Optimization 16th International Conference, LION 16, Milos Island, Greece, June 5–10, 2022, Revised Selected Papers (pp.263-277). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-031-24866-5_20].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/408464
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
Social impact