Shortest-path percolation on random networks

Abstract

We propose a bond-percolation model intended to describe the consumption, and eventual exhaustion, of resources in transport networks. Edges forming minimum-length paths connecting demanded origin-destination nodes are removed if below a certain budget. As pairs of nodes are demanded and edges are removed, the macroscopic connected component of the graph disappears, i.e., the graph undergoes a percolation transition. Here, we study such a shortest-path-percolation transition in homogeneous random graphs where pairs of demanded origin-destination nodes are randomly generated, and fully characterize it by means of finite-size scaling analysis. If budget is finite, the transition is identical to the one of ordinary percolation, where a single giant cluster shrinks as edges are removed from the graph; for infinite budget, the transition becomes more abrupt than the one of ordinary percolation, being characterized by the sudden fragmentation of the giant connected component into a multitude of clusters of similar size.

5 pages, 5 figures, 1 table + Supplemental Material

References in corpus (20)

• Error and attack tolerance of complex networks
• Catastrophic cascade of failures in interdependent networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• k-core organization of complex networks
• Robustness and resilience of complex networks
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Percolation on complex networks: Theory and application
• Modelling the Air Transport with Complex Networks: a short review
• Percolation in real interdependent networks
• Self-organized adaptation of a simple neural circuit enables complex robot behaviour
• Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
• Emergence of core-peripheries in networks
• The dynamic nature of percolation on networks with triadic interactions
• Crackling Noise in Fractional Percolation -- Randomly distributed discontinuous jumps in explosive percolation
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Explosive Percolation Obeys Standard Finite-Size Scaling in an Event-based Ensemble
• On the stability of traffic breakup patterns in urban networks
• Hysteretic percolation from locally optimal individual decisions
• Extended-range percolation in complex networks

Cited by in corpus (8)

• Path Percolation in Quantum Communication Networks
• General theory for extended-range percolation on simple and multiplex networks
• Triadic percolation on multilayer networks
• Modeling resource consumption in the US air transportation system via minimum-cost percolation
• Janus Percolation in Anisotropic Limited-Degree Networks
• Discontinuous transition in explosive percolation via local suppression
• Entanglement percolation in random quantum networks
• Shortest-path percolation on scale-free networks