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) the Watts-Strogats model uses a rewiring probability beginning with a lattice structure. Typically, most introductions I have come across begin with a single dimension lattice structure and I my plan here is to build such program that others can use after a bit more study. I am writing this at the moment as though you might already be familiar with the topic and a separate tutorial-like introduction will be written later.
The key takeaway using the Watts-Strogats model is that it creates a small-world network which will never be found in the G(n,p) model. 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 which can generate a network with the small-world phenomena. A 1998 paper [1] by Duncan Watts and Steven Strogatz published one of the most popular papers of its time in a physical science describing the small-world phenomena. You may better know its variants like the 6-degress of freedom or older origins of this study of this phenemona which was conducted as an experiment to see how many passes it took to delivery a piece of mail from one person to reach a destination by sending mail only through your known networks. A different paper following the next year in 1998 by Barabási and Albert was also a top ten cited paper, but we will discuss this in a different article for generating random graph using their G(n,p) model.
Rewiring Probability
As I mentioned, unlike the g(n,p) model which establishes links based on a probability of p, the Watts-Strogatz model first begins with a lattice-network of same degree. This can be best visualized with a circular, 2-degree node. Then with a probability of p links are rewired by 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.
In my earlier article I've shown how to calculate the local clustering coefficient if you like to revisit this topic.
Illustration
I will come around to update with some pictures here after I generate some visualizations. Mostly a reminder to myself to do this.
Tools
I will come around to update with a tool I created so you can explore with different parameters. Again, a reminder to myself and having it documented.
References
[1] Watts, D.J. and Strogatz, S.H.; Collective Dynamics of 'Small-World' Networks; Nature, 393: p.440, 1998.