• Featured in Physics

Limited Path Percolation in Complex Networks

Eduardo López, Roni Parshani, Reuven Cohen, Shai Carmi, and Shlomo Havlin
Phys. Rev. Lett. 99, 188701 – Published 29 October 2007
Physics logo

Abstract

We study the stability of network communication after removal of a fraction q=1p of links under the assumption that communication is effective only if the shortest path between nodes i and j after removal is shorter than aij(a1) 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=(κ01)(1a)/a, where κ0k2/k and k is the node degree. Above p˜c, order N nodes can communicate within the limited path length aij, 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 14 February 2007

DOI:https://doi.org/10.1103/PhysRevLett.99.188701

©2007 American Physical Society

Authors & Affiliations

Eduardo López1,*, Roni Parshani2,†, Reuven Cohen3, Shai Carmi2, and Shlomo Havlin2

  • 1CNLS & T-7, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA
  • 2Minerva Center & Department of Physics, Bar-Ilan University, Ramat Gan, Israel
  • 3Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

  • *Corresponding author. edlopez@lanl.gov
  • Corresponding author. parshani.roni@gmail.com

See Also

Connections Get You Everywhere, but Slowly

Mark Buchanan
Phys. Rev. Focus 20, 15 (2007)

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 99, Iss. 18 — 2 November 2007

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×