Watts–Strogatz model

For a ring lattice, the average path length[1] is ${\displaystyle \ell (0)\approx N/2K\gg 1}$ and scales linearly with the system size. In the limiting case of ${\displaystyle \beta \rightarrow 1}$, the graph approaches a random graph with ${\displaystyle \ell (1)\approx {\frac {\ln N}{\ln K}}}$, while not actually converging to it. In the intermediate region ${\displaystyle 0<\beta <1}$, the average path length falls very rapidly with increasing ${\displaystyle \beta }$, quickly approaching its limiting value.

For the ring lattice the clustering coefficient[5] ${\displaystyle C(0)={\frac {3(K-2)}{4(K-1)}}}$, and so tends to ${\displaystyle 3/4}$ as ${\displaystyle K}$ grows, independently of the system size.[6] In the limiting case of ${\displaystyle \beta \rightarrow 1}$ the clustering coefficient is of the same order as the clustering coefficient for classical random graphs, ${\displaystyle C=K/(N-1)}$ and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high ${\displaystyle \beta }$. This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.

If we use the Barrat and Weigt[6] measure for clustering ${\displaystyle C'(\beta )}$ defined as the fraction between the average number of edges between the neighbors of a node and the average number of possible edges between these neighbors, or, alternatively,

${\displaystyle C'(\beta )\equiv {\frac {3\times {\text{number of triangles}}}{\text{number of connected triples}}}}$

then we get ${\displaystyle C'(\beta )\sim C(0)(1-\beta )^{3}.}$

The degree distribution in the case of the ring lattice is just a Dirac delta function centered at ${\displaystyle K}$. The degree distribution for a large number of nodes and ${\displaystyle 0<\beta <1}$ can be written as,[6]

${\displaystyle P(k)\approx \sum _{n=0}^{f(k,K)}{{K/2} \choose {n}}(1-\beta )^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{(k-K/2-n)!}}e^{-\beta K/2},}$

where ${\displaystyle k_{i}}$ is the number of edges that the ${\displaystyle i^{\text{th}}}$ node has or its degree. Here ${\displaystyle k\geq K/2}$, and ${\displaystyle f(k,K)=\min(k-K/2,K/2)}$. The shape of the degree distribution is similar to that of a random graph and has a pronounced peak at ${\displaystyle k=K}$ and decays exponentially for large ${\displaystyle |k-K|}$. The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree.