Waste less time on Facebook — follow Brilliant.

Complex Networks 6

(It is assumed that the reader has already read the fifth article of this series.)

In the last article, we talked about an interesting property, called "Small world"property, which is exhibited by some networks . We also saw in particular that ER network does actually exhibit this property and also experiments show that even social network has the same property. The immediate question that comes to mind after this is that "does ER model a good model for social networks and other networks which exhibit small world property?". To investigate this question, let us think about our own friend circle. Let us say that on an average, you have \(100\) friends. But we already know that the number of people in the whole world is gigantic as compared to this number. Thus if our society is really like Erdos-Reyni network, the probability that two of my friends themselves are friends of each other should be negligibly small! This is because, in ER model, the probability that any pair of nodes is connected is equal and for such a large network like society, it is extremely small because everybody has only \(100\) friends on an average! Now everybody would agree that this is complete nonsense. In fact, many of my good friends of course know each other very well (That is why we can go for parties together!). Mark Granovetter, an American sociologist, has actually an interesting theory about it, called "The Strength of Weak Ties". Thus, despite of predicting small-world character of our society quite nicely, ER model has serious problem in it - there are no groups! In the last article, we gave an example of another network which exhibits small world property: neural network of C. elegans. Just like we already know that that network has small world property, we also know now that that network is no longer like ER network but rather looks like our society- if a particular neuron has two friends, then there is a very high probability that they are connected to each other as well!

To make this point quantitative, we can define something called "Clustering coefficient" for a given network. Let us say that the node \(i\) in the network has degree \(k_{i}\). Then, if all these \(k_{i}\) neighbours were connected with each other, the total number of links in this "neighbour group" would have been \(T_{i}=\frac{k_{i}(k_{i}-1)}{2}\). But of course, in reality, not all these links are present. Let \(E_{i}\) be the actual number of links present among these neighbours. Then more the value of ratio \(\frac{E_{i}}{T_{i}}\), better is the cluster around node \(i\). So let us define clustering coefficient of node \(i\), as this ratio:


The clustering coefficient of the whole network would then be an average of \(C_{i}\) over all the nodes of the network. As the name suggests, clustering coefficient of the network indicates how much the given network is "clustered". Clustering coefficient for ER graph comes out to be equal to \(p\) (Prove this!), the connection probability which is very small if the average degree is constant and network is very large (Prove this too!). Social network and other networks like neural network in C. elegans on the other hand show high degree of clustering.

How do we solve this problem? Certainly, the mathematically beautiful ER model needs to be replaced somehow by a better model to account for high value of clustering coefficient but at the same time we want to retain a small-world character of the network. In the next article, we will describe a beautiful way to get over this problem so be ready and share your thoughts! :-)

Note by Snehal Shekatkar
2 years, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

We can model the problem as an example of Scale-free network, whose formation can be explained by Preferential attachment models among others. Abhishek Sinha · 2 years, 8 months ago

Log in to reply

@Abhishek Sinha Thanks Abhishek for your interest in the topic. As you may have already noticed, this is a series about network theory and things like Scale-free networks and preferential attachment will be explained in future articles. I would like to keep some kind of continuity in the matter and so I am going slowly. Also this series is not supposed to teach people network theory who are already well versed in mathematics; they can study all these things quickly from any good book or article. Rather, I am writing this series mostly for people with level 1,2 and 3 who have problems reading complicated mathematics. :) Snehal Shekatkar · 2 years, 8 months ago

Log in to reply

I am really sorry that because of some health issues I took too long to publish "Complex Networks 6". Snehal Shekatkar · 2 years, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...