Google Research

Milgram-routing in social networks.

Proceedings of the 20th International Conference on World Wide Web, WWW 2011, pp. 725-734


We demonstrate how a recent model of social networks (“Affiliation Networks”) offers powerful cues in local routing within social networks, a theme made famous by sociologist Milgram’s “six degrees of separation” experiments. This model posits the existence of an “interest space” that underlies a social network; we prove that in networks produced by this model, not only do short paths exist among all pairs of nodes but natural local routing algorithms can discover them effectively. Specifically, we show that local routing can discover paths of length O(log^2 n) to targets chosen uniformly at random, and paths of length O(1) to targets chosen with probability proportional to their degrees. Experiments on the co-authorship graph derived from DBLP data confirm our theoretical results, and shed light into the power of one step of lookahead in routing algorithms for social networks.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work