Small-world networks: Evidence for a crossover picture

Watts and Strogatz [Nature 393, 440 (1998)] have recently introduced a model for disordered networks and reported that, even for very small values of the disorder $p$ in the links, the network behaves as a small-world. Here, we test the hypothesis that the appearance of small-world behavior is not a phase-transition but a crossover phenomenon which depends both on the network size $n$ and on the degree of disorder $p$. We propose that the average distance $\mathrm{\ell }$ between any two vertices of the network is a scaling function of $n\mathrm{/}{n}^{\ast }$. The crossover size $n^{\ast }$ above which the network behaves as a small-world is shown to scale as $n^{\ast }(p\ll 1)\sim p^{-\tau }$ with $\tau \approx 2/3$.