Six Degrees of Separation

Byron SpiceMonday, September 1, 2008

As more and more people migrate to the web for social interaction, researchers like Jure Leskovec (CS '07, '08) are finding new opportunities to study their collective behavior. While interning at Microsoft Research Redmond, Leskovec began wondering whether or not the "six degrees of separation" theory still rings true in today's wired world.

The theory suggests that everyone on Earth can be connected to any random person through less than seven people. Leskovec wondered how a smaller population of online chatters using Microsoft Instant Messenger might hold up to the theory.

Working with fellow Microsoft researcher Eric Horvitz, Leskovec analyzed 30 billion conversations over Microsoft Instant Messenger and found that any two random people were separated by 6.6 degrees. Read about their research in the Washington Post and ABC News.

"It is very easy to log detailed actions of millions of people through massive online communications systems such as Microsoft Instant Messager and Facebook," Leskovec explained. "By doing that, we can build predictive models of their collective behavior, which will help us to design better online systems and applications."

Leskovec's interests lie in the analysis and modeling of large, real-world networks as the study of phenomena across the social, technological and natural worlds. In the past, he has worked with civil engineers on the problem of how to place sensors in a water distribution network to quickly detect disease outbreaks.

"It turned out that we can use the same approach to identify influential people in social networks, identify flow of information on the web and find the most influential bloggers," Leskovec said.

A sense of community is very important to him. He sees it as one of Carnegie Mellon University's greatest strengths.

"In general, people at Carnegie Mellon are very friendly and willing to help and discuss research problems," he said. "My experience is that it is also very easy to collaborate with people inside computer science as well as across departments."

Leskovec hopes this sense of community carries on to the alumni, encouraging his peers to return to the school, give talks and share career insights.

He explained, "This way everyone benefits - students learn and alumni get to maintain the relationship with the university and its students."

For More Information

Byron Spice | 412-268-9068 | bspice@cs.cmu.edu