Milgram-routing in social networks.
Venue
Proceedings of the 20th International Conference on World Wide Web, WWW 2011, pp. 725-734
Publication Year
2011
Authors
Silvio Lattanzi, Alessandro Panconesi, D. Sivakumar
BibTeX
Abstract
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.
