Complex Networks 5

(It is assumed that the reader has read the fourth article of this series)

Have you ever tried to count the number of your friends and acquaintances? For most of us, the number would be of the order of $100$. For some of you, may be the number is greater than $1000$. But just see the size of the population of the whole world (or even your city!) and you will realize that all of us are in acquaintance with a very very small fraction of the society. In the jargon of network theory, every person is a node in a big social network and you have, say, $100$ links. Let us say that all of your acquaintances are $1$ link away from you. Now think of a particular friend of yours. Of course he also knows many people which you may not be knowing. All those people, whom one of your friends or acquaintances knows but you don't know, is then $2$ links away from you. We can also say that the distance between any of these people and you is $2$ in social network. If you consider the whole population of the world, then one interesting question to ask would be "what is the average distance between any two people in the whole social network?" After looking at the size of the whole social network, (more than $7$ billion nodes!), we would easily guess that this average distance must be very large!

Interestingly, social scientists have already performed few experiments to try to find out this average distance. The most prominent among these is the set of experiments performed by Stanley Milgram. The main theme of the experiment was choosing a random person as a target and then asking several other people (who don't have any connection with target person) to send letters to their acquaintances. Then those people who got these letters were asked to send new letters to their acquaintances and so on until the target person gets at least one of the letters. It was expected that it would take long time before any of these letters reach the target person (if at all). You can read about this experiment here. But when the results of this experiment came out, they were simply astonishing and in complete contrast to the expectations. Out of $160$ letters sent initially, not one or two, but $42$ letters could find the target! Also, the experiment revealed that the average distance between any two people in the population of U.S.A. is less than six! The better versions of these experiments have revealed that average social distance between any two people on earth is only six in spite of such a big number of nodes in the network! This is an extraordinary result indeed. You can consider any random person on earth (a factory worker in small village of Kenya or a President of United states) and if you try to find a sequence of people starting from you and ending on the target person, then that chain will not be of gigantic length as the intuition suggests at first sight. In fact the distance between you and that person would be around six only! (Try to amuse yourself by finding such a sequence of links starting from you and ending at the President of your country or some other famous person). This fact, since then, has been given a special name: Six degrees of separation!

Does ER model, that we are discussing, tell us something about this amazing property of the social networks? Let us try to look at the average distance between any two nodes in the ER network (methods of actually calculating things like this, which I am aware of, are somewhat complicated and will be dealt in some detail in future articles of this series). We will consider only the shortest distance (that is, the path in the network with least number of links between chosen pair of nodes). It turns out that if the size of the network (i.e. the number of nodes in the network) is $N$ then the average distance goes as $log N$ and as we already know, the logarithm is a very slowly increasing function of $N$. This helps in explaining the 'six degrees of separation' present in social network. This amazing gift that nodes have got, makes these gigantic networks literally "small". Somehow our world is not that large.. In fact.. its a quite small world! But there is nothing special about social networks. Most of the networks in nature show this property that the average distance between the nodes is very much smaller than the number of nodes in the network and hence all such networks are called "Small world networks" and this property is called "small world property".

Just to cite few more examples, Albert Barabasi's group, using the data provided by NEC group found that every web-page is around only $19$ clicks away from every other web-page and it is also well known now that the average distance between any two neurons in the brain of worm C. elegans is $14$. We will look into small worlds more in future, but for today, it must have shaken the intuitions of most of you if you did not know about this already.

Just now we are becoming aware of the extremely amazing properties of complex world around us and we are yet to see much more! So keep track of next articles of the series.. :)