Limited Path Percolation in Complex Networks

Abstract

We study the stability of network communication after removal of a fraction $q=1-p$ of 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 analytically and numerically a new percolation transition at ${\tilde{p}}_c=({\kappa }_0-1{)}^{(1-a)/a}$, where ${\kappa }_0\equiv ⟨k^2⟩/⟨k⟩$ and $k$ is the node degree. Above ${\tilde{p}}_c$, order $N$ nodes can communicate within the limited path length $a{\ell }_{ij}$, while below ${\tilde{p}}_c$, $N^{\delta }$ ($\delta <1$) nodes can communicate. We expect our results to influence network design, routing algorithms, and immunization strategies, where short paths are most relevant.