My draft on this topic.
Recently, I have been looking into graph generation models like G(n,p) which is a random, graph generation method. The Watts-Strogats is also random graph generator. Unlike G(n,p), Watts-Strogats uses a rewiring probability. A simple model would use a lattice structure. Typically, most introductions I have come across begins with a single dimension lattice structure.
Watts-Strogatz model creates a small-world network. The G(n,p) model does. Yet, this still has a high clustering coefficient and also shortens the characteristic path length of the graph.
History
The Watts-Strogatz model is a graph generation model. A 1998 paper by Duncan Watts and Steven Strogatz [1] published one of the most popular papers of its time in a physical science describing the small-world phenomena. Older origins of this study of this phenemona was conducted as an experiment to see how many passes it took to deliver a piece of mail from one person to reach a particular destination. Mail was sent only through your known connections. A different paper following the next year in 1998 by Barabási and Albert was also a top ten cited paper. I will return to discuss more on this in a separate post.
Rewiring with Probability, p
Begin a model with a lattice-network of same degree. This can be best visualized with a circular, 2-degree node. Rewire with probability, p, the links replacing the existing link formed by u,v to a different pair of nodes u,w. The effect of this is you start with the highest clustering coefficient which will then decrease as the rewiring starts. As links are rewired, this shortens the characteristic path length (CPL), while still maintaining a relative, high clustering coefficient.
I've shared here how to calculate the local clustering coefficient.
References
[1] Watts, D.J. and Strogatz, S.H.; Collective Dynamics of 'Small-World' Networks; Nature, 393: p.440, 1998.