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

Abstract

We discuss shortest-path lengths l(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) approximately l(-mu). Using rescaling arguments and numerical simulation on systems of up to 10(7) sites, we show that a characteristic length xi exists such that l(r) approximately r for r<xi but l(r) approximately r(theta(s)(mu)) for r>>xi. For small p we find that the shortest-path length satisfies the scaling relation l(r,mu,p)/xi=f(mu,r/xi). Three regions with different asymptotic behaviors are found, respectively: (a) mu>2 where theta(s)=1, (b) 1<mu<2 where 0<theta(s)(mu)<1/2, and (c) mu<1 where l(r) behaves logarithmically, i.e., theta(s)=0. The characteristic length xi is of the form xi approximately p(-nu) with nu=1/(2-mu) 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.