First-order transition in small-world networks

Abstract

The small-world transition is a first-order transition at zero density $p$ of shortcuts, whereby the normalized shortest-path distance undergoes a discontinuity in the thermodynamic limit. On finite systems the apparent transition is shifted by $\Delta p\sim L^{-d}$. Equivalently a ``persistence size'' $L^{\ast }\sim p^{-1/d}$ can be defined in connection with finite-size effects. Assuming $L^{\ast }\sim p^{-\tau }$, simple rescaling arguments imply that $\tau =1/d$. We confirm this result by extensive numerical simulation in one to four dimensions, and argue that $\tau =1/d$ implies that this transition is first-order.

4 pages, 3 figures, To appear in Europhysics Letters