= Solution
For the \b[<Watts-Strogatz model>], choose $n$ <vertices> on a ring, an even initial <vertex degree> $K<n$, and a rewiring <probability> $p$. Connect each <vertex> to its $K/2$ nearest neighbours on each side. Consider each original clockwise <edge> once: with <probability> $p$, retain its starting endpoint and replace its other endpoint uniformly, excluding <self-loops> and duplicate <edges>. The edge count remains $nK/2$, although individual <vertex degrees> change.
Increasing $n$ at fixed $K$ lengthens unrewired-ring <graph distances>. Increasing $K$ adds <edges> and shortens distances. Increasing $p$ introduces shortcuts, sharply reducing <average shortest path length> at first, then progressively reducing the <clustering coefficient> by destroying local triangles.
\b[The <small-world network> regime occurs at intermediate $p$] with sufficient shortcuts, substantial clustering, and $K\ll n$. At $p=0$ distances are long; near $p=1$ the clustering advantage disappears. The <degree distribution> remains concentrated around $K$, so this is \b[not a <scale-free network>].<Collective dynamics of small-world networks by Duncan J. Watts and Steven H. Strogatz>[pp. 440–441, construction and dependence on rewiring probability]{ref}
Back to article page
