document: Milgram-routing in social networks We demonstrate how a recent model of social networks ( `` Affiliation Networks '' , ( 21 ) ) 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 ( log2 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 .
doc_bio_tags: O O B I O O O O O O O B I O O B I O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O