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:

$C_{i}=\frac{E_{i}}{T_{i}}=\frac{2E_{i}}{k_{i}(k_{i}-1)}$

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! :-)