Quantifying edge relevance for epidemic spreading via the semi-metric topology of complex networks
Open Access
- 1 August 2025
- journal article
- Published by IOP Publishing in Journal of Physics: Complexity
- Vol. 6 (3) , 035005
Abstract
Sparsification aims at extracting a reduced core of associations that best preserves both the dynamics and topology of networks while reducing the computational cost of simulations. We show that the semi-metric topology of complex networks yields a natural and algebraically-principled sparsification that outperforms existing methods on those goals. Weighted graphs whose edges represent distances between nodes are semi-metric when at least one edge breaks the triangle inequality (transitivity). We first confirm with new experiments that the metric backbone—a unique subgraph of all edges that obey the triangle inequality and thus preserve all shortest paths—recovers susceptible-infected dynamics over the original non-sparsified graph. This recovery is improved when we remove only those edges that break the triangle inequality significantly, i.e. edges with large semi-metric distortion. Based on these results, we propose the new semi-metric distortion sparsification method to progressively sparsify networks in decreasing order of semi-metric distortion. Our method recovers the macro- and micro-level dynamics of epidemic outbreaks better than other methods while also yielding sparser yet connected subgraphs that preserve all shortest paths. Overall, we show that semi-metric distortion overcomes the limitations of edge betweenness in ranking the dynamical relevance of edges not participating in any shortest path, as it quantifies the existence and strength of alternative transmission pathways.Keywords
All Related Versions
Funding Information
- Fundação para a Ciência e a Tecnologia (2022.09122.PTDC)
- U.S. National Library of Medicine (01LM011945-01)
- Ministerio de Ciencia, Innovación y Universidades (JDC2022-048339-I)
This publication has 62 references indexed in Scilit:
- The Distance Backbone of Directed Networks2023
- The interconnection between independent reactive control policies drives the stringency of local containmentChaos, Solitons & Fractals, 2022
- Allocating resources for epidemic spreading on metapopulation networksApplied Mathematics and Computation, 2021
- Spectrum-preserving sparsification for visualization of big graphsComputers & Graphics, 2020
- Preparedness and vulnerability of African countries against importations of COVID-19: a modelling studyThe Lancet, 2020
- Using epidemic betweenness to measure the influence of users in complex networksJournal of Network and Computer Applications, 2017
- Distance closures on complex networksNetwork Science, 2015
- Reaction–diffusion processes and metapopulation models in heterogeneous networksNature Physics, 2007
- Collective dynamics of ‘small-world’ networksNature, 1998
- The renormalization group and the ε expansionPhysics Reports, 1974