Description
Pros & Cons
It is a well known model, whose properties are by now quite well understood. It can be used to generate networks of any size. The degree distribution is Poissonian for any value of the rewiring probability (except in the extreme case of rewiring probability zero, for which all nodes have equal degree), the clustering coefficient is tunable.
Applications
It is usually studied to explore networks with tunable values for the average shortest path between pairs of nodes and the clustering coefficient. Networks with small values for the average shortest path and large values for the clustering coefficient are supposed to simulate social networks.
Implementation Details
The algorithm requires three inputs: the number of nodes of the network, the number k of initial neighbors of each node on the two sides of the network (the initial configuration is a ring of nodes) and the probability of rewiring the edges (which is a real number between 0 and 1). The network is built following the original prescription of Watts and Strogatz, i.e. by starting from a ring of nodes each connected to the k nodes to their right/left and by rewiring each edge with the specified probability.
The algorithm runs in a time O(kn), where n is the number of nodes of the network.
Usage Hints
As an exercise, one could try to build a small world network with 1000 nodes, 10 initial neighbors per side and a rewiring probability of 0.01. After the network file has been produced, one could select it and apply on it the two algorithms on the average shortest path and the clustering coefficient, to verify that the former is small and the latter is still relatively large.
Acknowledgements
The algorithm was implemented and documented by S. Fortunato, integrated by S. Fortunato and W. Huang. For the description we acknowledge Wikipedia.
References
Watts, D.J., Strogatz, S.H.(1998) Collective dynamics of 'small-world' networks. Nature 393:440-442.