Shortest-path percolation on scale-free networks
- 21 January 2026
- journal article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 113 (1) , 014314
Abstract
The shortest-path-percolation (SPP) model aims at describing the consumption and eventual exhaustion of a network's resources. Starting from a network containing a macroscopic connected component, random pairs of nodes are sequentially selected, and if the length of the shortest path connecting the node pairs is smaller than a tunable budget parameter, then all edges along such a path are removed from the network. As edges are progressively removed, the network eventually breaks into multiple microscopic components, undergoing a percolation-like transition. It is known that the SPP transition on Erdős-Rényi networks (ERNs) belongs to the same universality class as the ordinary bond percolation if the budget parameter is finite; for an unbounded budget, instead, the SPP transition becomes more abrupt than the ordinary percolation transition. By means of large-scale numerical simulations and finite-size scaling analysis, here we study the SPP transition on random scale-free networks (SFNs) characterized by power-law degree distributions. We find, in contrast with ordinary percolation, that the transition is identical to the one observed on ERNs, denoting independence from the degree exponent. Still, we distinguish finite- and infinite-budget SPP universality classes. Our findings follow from the fact that the SPP process drastically homogenizes the heterogeneous structure of SFNs before the SPP transition takes place.Keywords
All Related Versions
Funding Information
- National Science Foundation (1927425)
- National Science Foundation (1927418)
- Air Force Office of Scientific Research (FA9550-24-1-0039)
- Air Force Office of Scientific Research (B53D23003880006)
- Ministero dell'Università e della Ricerca
- NextGenerationEU
- PRIN (20223W2JKJ)
This publication has 36 references indexed in Scilit:
- Modeling resource consumption in the US air transportation system via minimum-cost percolationNature Communications, 2025
- Finite-size scaling of percolation on scale-free networksChaos, Solitons & Fractals, 2025
- Robustness and resilience of complex networksNature Reviews Physics, 2024
- The dynamic nature of percolation on networks with triadic interactionsNature Communications, 2023
- Percolation on complex networks: Theory and applicationPhysics Reports, 2021
- Universal gap scaling in percolationNature Physics, 2020
- Breaking of the site-bond percolation universality in networksNature Communications, 2015
- Percolation transition in dynamical traffic network with evolving critical bottlenecksProceedings of the National Academy of Sciences, 2014
- Catastrophic cascade of failures in interdependent networksNature, 2010
- Error and attack tolerance of complex networksNature, 2000