Quantifying edge relevance for epidemic spreading via the semi-metric topology of complex networks

Soriano-Paños, David; Costa, Felipe Xavier; Rocha, Luis M.

http://hdl.handle.net/10400.14/54622

Use this identifier to reference this record.

Send Feedback

Authors

Soriano-Paños, David

Costa, Felipe Xavier

Rocha, Luis M.

Abstract(s)

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 \textit{semi-metric} when at least one edge breaks the triangle inequality (transitivity). We first confirm with new experiments that the \textit{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 \textit{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

Distance backbone Epidemic dynamics Network sparsification Semi-metric distortion

URI

http://hdl.handle.net/10400.14/54622

Citation

Soriano-Paños, D., Costa, F. X., & Rocha, L. M. (2025). Quantifying edge relevance for epidemic spreading via the semi-metric topology of complex networks. Journal of Physics: Complexity, 6(3), Article 035005. https://doi.org/10.1088/2632-072X/adf2ed