Limited path percolation in complex networks

López, Eduardo, Parshani, Roni, Cohen, Reuven, Carmi, Shai and Havlin, Shlomo (2007) Limited path percolation in complex networks. Physical Review Letters, 99 (18). p. 188701.


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=(κ0-1)(1-a)/a, where κ0≡⟨k2⟩/⟨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.

Item Type: Article
Keywords: Statistical Mechanics; Disordered Systems and Neural Networks; Complex Networks
Subject(s): Complexity
Centre: CABDyN Complexity Centre
Date Deposited: 06 Mar 2012 21:19
Last Modified: 23 Oct 2015 14:06

Actions (login required)

Edit View Edit View