Spreading and shortest paths in systems with sparse long-range connections

Abstract

Spreading according to simple rules (e.g., of fire or diseases) and shortest-path distances are studied on d-dimensional systems with a small density p per site of long-range connections (“small-world” lattices). The volume $V\left(t\right)\mathrm{}$ covered by the spreading quantity on an infinite system is exactly calculated in all dimensions as a function of time t. From this, the average shortest-path distance $\mathcal{l}\mathrm{}\left(r\right)\mathrm{}$ can be calculated as a function of Euclidean distance r. It is found that $\mathcal{l}\mathrm{}\left(r\right)\mathrm{}\sim r$ for $r<\mathrm{}{r}_c=\left[2p{\Gamma }_d\right(d-1)!{]}^{-1/d}\log (2p{\Gamma }_d{L}^d)$ and $\mathcal{l}\mathrm{}\left(r\right)\mathrm{}\sim r_c$ for $r>\mathrm{}{r}_c.$ The characteristic length $r_c,$ which governs the behavior of shortest-path lengths, diverges logarithmically with L for all $p>\mathrm{}0.\mathrm{}$