Complex Networks 6

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

Note by Snehal Shekatkar
7 years, 4 months ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example 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 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I am really sorry that because of some health issues I took too long to publish "Complex Networks 6".

- 7 years, 4 months ago

We can model the problem as an example of Scale-free network, whose formation can be explained by Preferential attachment models among others.

- 7 years, 4 months ago

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

- 7 years, 4 months ago