Infinite characteristic length on small-world systems

It was recently claimed that on d-dimensional small-world networks with a density p of shortcuts, the typical separation s (p) ~ p^-1/d between shortcut-ends is a characteristic length for shortest-pathscond-mat/9904419. This contradicts an earlier argument suggesting that no finite characteristic length can be defined for bilocal observables on these systems cont-mat/9903426. We show analytically, and confirm by numerical simulation, that shortest-path lengths (r) behave as (r) ~ r for r rc, where r is the Euclidean separation between two points and rc (p, L) = p^-1/d log (Lᵈp) is a characteristic length. This shows that the mean separation s between shortcut-ends is not a relevant length-scale for shortest-paths. The true characteristic length rc (p, L) diverges with system size L no matter the value of p. Therefore no finite characteristic length can be defined for small-world networks in the thermodynamic limit.