Waste less time on Facebook — follow Brilliant.

Complex Networks 7

(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. :)

Note by Snehal Shekatkar
2 years, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

Wow, this is really interesting... The Social Network analogy is a great way to explain this, as it's intuitive to understand. In what other fields can these models be applied? In what other ways are complex networks used to help us? Raj Magesh · 1 year, 8 months ago

Log in to reply

@Raj Magesh They are used to describe any system where there are many interacting units. Some examples apart from social network are world wide web, internet, chemical reactions in biological cells, airports, power grids, languages, movie actors, human brain, proteins and genes, scientific papers, researchers and so on. Snehal Shekatkar · 1 year, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...