ftp://ftp.research.microsoft.com/pub/tr/TR-2006-186.pdf

 This article describes yet another experiment to prove that any two nodes in a network can be connected by at most 6 steps.  More specifically this experiment was referenced on page 34 of the text.  Jure Leskovec and Eric Horvitz looked at of 200 million Instant Messenger users and created a social network linking users if they had spoken to one another in the last 30 days.  This expeiment resulted in the average degree of separation of 6.6.  Earlier work by Travers and Milgram result in an average degree of separation of 6.2.  The obsession with the number 6 seems unwarranted.  I think the whole obsession with 6 degrees of separation is from the fact that people are suprised by such a low number.  By it is this number really that small?

The idea of locating a given node of a network by starting at a certain node can be computed by using depth-first search.  This average degree of separation is really only effected by the branching factor the graph (which could differ from node to node).  But lets look at Facebook.  Even though I don’t have Facebook myself I know alot of people who use it have 100’s of friends.  But lets be conservative and say that on average a person has 100 Facebook friends.  Then at a height of 6, or 6 degrees of separation, away from the root node, 100^6 nodes would have been traversed.  100^6 is 1 trillion nodes, which is also around 100 times the number of people in the world!  So is it that hard to believe that most networks observe around 6 degrees of separation.  I think not.  But then again it would be interesting to see if growing networks experience some kind of limiting average for the degree of separation, but this is outside of the scope of this post.