Limited Path Percolation in Complex Networks

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ℓ_ij(a≥1) where ℓ_ij is the shortest path before removal. For a large class of networks, we find analytically and numerically a new percolation transition at p˜_c=(κ₀-1)^(1-a)/a, where κ₀≡⟨k²⟩/⟨k⟩ and k is the node degree. Above p˜_c, order N nodes can communicate within the limited path length aℓ_ij, while below p˜_c, N^δ (δ<1) nodes can communicate. We expect our results to influence network design, routing algorithms, and immunization strategies, where short paths are most relevant.