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 al(ij)(a> or =1) where l(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)=(kappa(0)-1)((1-a)/a), where kappa(0) [triple bond]<k(2)> / <k>and k is the node degree. Above p(c), order N nodes can communicate within the limited path length al(ij), while below 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.
López
Eduardo
E
CNLS & T-7, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA. edlopez@lanl.gov
Parshani
Roni
R
Cohen
Reuven
R
Carmi
Shai
S
Havlin
Shlomo
S
D000465:Algorithms; D003142:Communication; D007255:Information Services; D008954:Models, Biological; D008962:Models, Theoretical