Six Degrees of Separation

In July 2006, Eric Horvitz and Jure Leskovec as part of a research project at Microsoft Research captured a snapshot of anonymized patterns of communications across the globe within the MSN Messenger system.  The dataset contained 30 billion conversations among 240 million people, representing what was estimated to be approximately half of all instant messaging communications in the world during that period of time.  No text was captured—only statistics were gathered. From the dataset, they constructed a “communication graph” with 180 million nodes and 1.3 billion undirected edges, creating the largest social network constructed and analyzed at the time. As part of their studies they investigated on a planetary-scale the oft-cited report that people are separated by “six degrees of separation” and found that the average path length among Messenger users communicating with one another during the month of July 2006 is 6.6. They also found that people tend to communicate more with each other when they have similar age, language, and location, and that cross-gender conversations are both more frequent and of longer duration than conversations with the same gender.

Some of the coverage on the analysis and results:



§  Short paper (WWW 2008): J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging Network, Proceedings of WWW 2008, Beijing, China, April 2008.

§  Longer report: J. Leskovec and E. Horvitz. Worldwide Buzz: Planetary-Scale Views on an Instant-Messaging Network, Microsoft Research Technical Report MSR-TR-2006-186, Microsoft Research, June 2007.






Back to Eric Horvitz's home page.