Limited path percolation in complex networks

Abstract

We study the stability of network communication after removal of $q=1-p$ links under the assumption that communication is effective only if the shortest path between nodes $i$ and $j$ after removal is shorter than $a{\ell }_{ij}(a\ge 1)$ where ${\ell }_{ij}$ is the shortest path before removal. For a large class of networks, we find a new percolation transition at ${\tilde{p}}_c=({\kappa }_o-1{)}^{(1-a)/a}$, where ${\kappa }_o\equiv <k^2>/<k>$ and $k$ is the node degree. Below ${\tilde{p}}_c$, only a fraction $N^{\delta }$ of the network nodes can communicate, where $\delta \equiv a(1-|\log p|/\log ({\kappa }_o-1))<1$, while above ${\tilde{p}}_c$, order $N$ nodes can communicate within the limited path length $a{\ell }_{ij}$. Our analytical results are supported by simulations on Erdős-Rényi and scale-free network models. We expect our results to influence the design of networks, routing algorithms, and immunization strategies, where short paths are most relevant.

11 pages, 3 figures, 1 table

References in corpus (16)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• The architecture of complex weighted networks
• The spread of epidemic disease on networks
• Classes of behavior of small-world networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Connectivity of Growing Random Networks
• Scale-Free Networks are Ultrasmall
• Optimal Paths in Disordered Complex Networks
• Optimization of Network Robustness to Waves of Targeted and Random Attack
• Communication Bottlenecks in Scale-Free Networks
• Anomalous Transport in Complex Networks

Cited by in corpus (19)

• Critical phenomena in complex networks
• Percolation on complex networks: Theory and application
• Dynamical Systems on Networks: A Tutorial
• Density-based and transport-based core-periphery structures in networks
• The Effect of Disease-induced Mortality on Structural Network Properties
• Simple and efficient self-healing strategy for damaged complex networks
• Limited path entanglement percolation in quantum complex networks
• Effect of edge removal on topological and functional robustness of complex networks
• Enhancing the robustness of scale-free networks
• Effects of epidemic threshold definition on disease spread statistics
• Optimization of transport protocols with path-length constraints in complex networks
• Characterization of Subgraphs Relationships and Distribution in Complex Networks
• Models of Continuous-Time Networks with Tie Decay, Diffusion, and Convection
• Emergent lifetime distribution from complex network systems aging
• Pseudo-Darwinian evolution of physical flows in complex networks
• Disorder Induced Limited Path Percolation
• Color-avoiding percolation in edge-colored Erdős-Rényi graphs
• Coupled effects of local movement and global interaction on contagion
• Household Bubbling Strategies for Epidemic Control and Social Connectivity