Shortest paths on systems with power-law distributed long-range connections

Abstract

We discuss shortest-path lengths $\ell (r)$ on periodic rings of size L supplemented with an average of pL randomly located long-range links whose lengths are distributed according to $P_l \sim l^{-\xpn}$. Using rescaling arguments and numerical simulation on systems of up to $10^7$ sites, we show that a characteristic length $\xi$ exists such that $\ell (r)\sim r$ for $r<\xi$ but $\ell(r) \sim r^{θ_s(\xpn)}$ for $r>>\xi$. For small p we find that the shortest-path length satisfies the scaling relation $\ell(r,\xpn,p)/ξ= f(\xpn,r/ξ)$. Three regions with different asymptotic behaviors are found, respectively: a) $\xpn>2$ where ${\theta }_s=1$, b) $1<\xpn<2$ where $0<θ_s(\xpn)<1/2$ and, c) $\xpn<1$ where $\ell (r)$ behaves logarithmically, i.e. ${\theta }_s=0$. The characteristic length $\xi$ is of the form $\xi \sim p^{-\nu }$ with $ν=1/(2-\xpn)$ in region b), but depends on L as well in region c). A directed model of shortest-paths is solved and compared with numerical results.

10 pages, 10 figures, revtex4. Submitted to PRE