I have recently read


* Watts, D., Strogatz, S., *Collective dynamics of ‘small-world’ networks*, Nature **393** (1998) pp. 440–442, doi:[10.1038/30918](https://doi.org/10.1038/30918),


on small-world networks, and is still not very clear to me how is the "small-world network regime" defined. Meaning that for a fixed value of vertices $N$ and a node degree $k$, what is the intermediate region of $0 < p < 1$ for which the Watts-Strogatz model is a small-world network?



Small world network regime
An increase of the "rewiring probability" $p$ (the probability that an edge is disconnected from one of its nodes and then randomly connected to another node) reduces both the mean path length $L$ and the [clustering coeffcient](https://en.wikipedia.org/wiki/Clustering_coefficient) $C$. There is a range of $p$ where the path length has been reduced substantially while the clustering coefficient is still close to the $p=0$ value. In that range of $p$ the network is called a small-world network.


There is no unique way to quantify that $p$-range. Wikipedia lists [three different criteria.](https://en.wikipedia.org/wiki/Small-world_network#Properties_of_small-world_networks)


The figure below shows how $L$ and $C$ decrease with increasing $p$. The shaded region would be the "small-world network" region, but obviously this is not a sharply bound region. [click on the figure to enter the applet and see how the network changes as you slide $p$]


[![](https://i.stack.imgur.com/2X4Fq.png)](https://mathinsight.org/applet/small_world_network)


*Note: "path length" counts each edge as being of length 1, irrespective of the length of the bond.*


