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

Regular Regular Figure 1

You can amuse yourself by calculating the clustering coefficient for this network. For sure, CC 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.

WS WS 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
7 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


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 - 6 years, 5 months ago

Log in to reply

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 - 6 years, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...