(It is assumed that reader has already read the sixth article of this series)
In the last article we discussed an important property of networks called 'Clustering coefficient' and we also saw that many real networks have much larger value for clustering coefficient (\(C\)) than predicted by ER model. On the other hand ER model predicts to a great accuracy small world-property of these networks. This implies that we should now look for an alternative model which will predict higher value of clustering coefficient and at the same time, will retain small worlds property. In 1998 , American mathematician Steven Strogatz from Cornell University with his Ph.D. student Duncan Watts proposed a model (which they published in Nature which for the first time reconciled clustering with the small world property.
To understand Watts-Strogatz model (henceforth called WS model for brevity), let us imagine that all the nodes of the network are sitting on the circumference of the circle with each node being connected to four nearest neighbouring nodes on the circle. The resulting network is shown in Figure 1.Figure 1
You can amuse yourself by calculating the clustering coefficient for this network. For sure, \(C\) for this model has much larger value than that for ER model. But for sure, this network is too regular to be of any use as model of social network for example which is much random. Moreover, if there are say 10 billion nodes in this network, it would by no means have small world property: to go from one side of network to the other side, we would have to literally cross billion nodes! But now comes the surprise! Now imagine that we simply rewire few of the existing links randomly so that they connect distant nodes on the network. The resulting network after this rewiring may look something like the one in Figure 2.Figure 2
The most surprising thing that Watts and Strogatz found was that even a small number of such re-wirings are sufficient to drastically decrease the average separation between the nodes of this network retaining the clustering coefficient to almost the same value! The few long range links produced by rewiring amazingly collapse the astronomical distances which were present in the network before and network becomes small-world! At the same time, since the number of rewired links is quite small, it doesn't affect the clustering coefficient much and it remains at appreciably high value than for ER model. In terms of social networks, this WS model says that almost all the people have local friends but there are few people thanks to whom, we can easily navigate to distant parts of the social network.
This beautiful construction has solved the major problem of reconciling the clustering with small worlds but the world is of course not that simple yet! In future articles we would see whether even this model survives the test of complexity or we need even better view of the world around us. So please keep giving feedback and share your thoughts below. :)