It is a remarkable fact that in a social network there are usually only six people linking any two members - this is often called the "small world effect" because picking any two people in the world at random we would expect then to be connected by no more than six people - why? Why isn't the world composed of effectively isolated groups of people?

The small world effect first appeared in a short story, "Chains" (1929) by Frigyes Karinthy, as a game to find out how many people it takes to connect any two random people. It was he who coined the term "six degrees of separation". Later the idea was generalized to the "small world" effect where the distance between people scales logarithmically with the size of the population.

What is strange, if the idea that any two people tend to be connected by a small chain of friends isn't strange enough, is that this number six? Why six? It has been confirmed a few times that six is indeed the number, although other studies have placed the number at close to 4 which makes the small world even smaller.

It seems that now we have a solution to the problem and it is, as you might expect, the result of each person acting locally to produce this global effect. The key is to understand that there is a cost involved in making a new friend and a corresponding benefit. You can think of these as casual quantities that people are vaguely aware of or you can quantify them and put them into a model and see what happens:

This is exactly what a large team of researchers did and they found that thing settled down into a Nash equilbrum where there was no change that could result in an overall improvement.  You can see in the chart below that adding random links to a network brings the connection down to a higher value than 6, but for the network at equilbrium the number is 6,

There is a pressure to form links with people in more distant groups because the reward function weights how important the person is in the network. This is based on the idea of "betweenness centrality". A person with high betweenness centrality is in a position where more information will pass through them from the other people in the network.

The paper concludes:

Namely, we demonstrated that a simple evolutionary process through which the cost incurred in forming connections is counterbalanced by the benefit in terms of increased betweenness centrality is a possible mechanism underlying the emergence of ultra-small world networks with six degrees of separation. Our study points out, therefore, that evolutionary rules of the kind traditionally associated with human cooperation and altruism can in fact account also for the emergence of this attribute of social networks. Furthermore, we show that such a global network feature can emerge even from situations where individuals have access to only partial information on the overall structure of connections, which is indeed the case in almost all social networks.

This is all very reasonable, although why six is the number that falls out of the model is something I personally still cannot see. However the final comment in the paper raises another interesting question:

 Finally, our study also sheds light on the so-called strength of weak ties phenomenon. This concept was introduced by Mark Granovetter who showed that the most common way of finding a new job is through personal contacts with distant acquaintances, and not via close friends, as one would instead 7 have expected. Distant acquaintances represent links connecting different groups of people, and therefore provide each individual with a unique way to receive useful information about distant groups.....

The formation of links connecting nodes from 2- independent sets as the key to the emergence of the six degrees of separation describes exactly the case of a local bridge formation, i.e. a weak tie in Granovetter’s sense. Therefore, our model can also be viewed as the gametheoretical foundation for strength of weak ties.

So it's not so much who you know, but who you know who knows people you don't know that is important.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way. and The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, which examines the nature of programming and reveals why it is a very special skill.

<ASIN:1871962439> 

<ASIN:1871962722> 

More Information

Why are there six degrees of separation in a social network?

Related Articles

Six Degrees Of Separation Is New

Vertex Coverings And The Cool Kids Problem

Think Complexity       

Going Further Into Complexity With Santa Fe Institute       

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info