title: 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 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.
authors.affiliation: CNLS & T-7, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA. edlopez@lanl.gov
authors.forename: Eduardo
authors.initials: E
authors.lastname: López
authors.forename: Roni
authors.initials: R
authors.lastname: Parshani
authors.forename: Reuven
authors.initials: R
authors.lastname: Cohen
authors.forename: Shai
authors.initials: S
authors.lastname: Carmi
authors.forename: Shlomo
authors.initials: S
authors.lastname: Havlin
mesh_terms: D000465:Algorithms; D003142:Communication; D007255:Information Services; D008954:Models, Biological; D008962:Models, Theoretical