Geometric phase-transition on systems with sparse long-range connections

Small-world networks are regular structures with a fraction p of regular connections per site replaced by totally random ones (“shortcuts”). This kind of structure seems to be present on networks arising in nature and technology. In this work we show that the small-world transition is a first-order transition at zero density p of shortcuts, whereby the normalized shortest-path distance L=ℓ̄/L undergoes a discontinuity in the thermodynamic limit. On finite systems the apparent transition is shifted by Δp∼L−d. Equivalently a “persistence size” L∗∼p−1/d can be defined in connection with finite-size effects. Assuming L∗∼p−τ, simple rescaling arguments imply that τ=1/d. We confirm this result by extensive numerical simulation in one to four dimensions, and argue that τ=1/d implies that this transition is first-order.