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\geq1)$ 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=(κ_o-1)^{(1-a)/a}$, where $κ_o\equiv < k^2>/< k>$ and $k$ is the node degree. Below $\tilde{p}_c$, only a fraction $N^δ$ of the network nodes can communicate, where $δ\equiv a(1-|\log p|/\log{(κ_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