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


Abstract in English

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^{theta_s(xpn)}$ for $r>>xi$. For small p we find that the shortest-path length satisfies the scaling relation $ell(r,xpn,p)/xi = f(xpn,r/xi)$. Three regions with different asymptotic behaviors are found, respectively: a) $xpn>2$ where $theta_s=1$, b) $1<xpn<2$ where $0<theta_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^{- u}$ with $ u=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.

Download