PNAS Geek-Out, Part III: Geographic Routing in Social Networks

Finally in our geek-out in the current issue of the Proceedings of the National Academy of Sciences, this paper about overlaying geography onto online social networks:

Geographic routing in social networks

We live in a ‘‘small world,’’ where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively forward a message along such a chain. Experimental studies have verified this property in real social networks, and theoretical models have been advanced to explain it. However, existing theoretical models have not been shown to capture behavior in real-world social networks. Here, we introduce a richer model relating geography and social-network friendship, in which the probability of befriending a particular person is inversely proportional to the number of closer people. In a large social network, we show that one-third of the friendships are independent of geography and the remainder exhibit the proposed relationship. Further, we prove analytically that short chains can be discovered in every network exhibiting the relationship.

The authors used the 1.3mm LiveJournal bloggers as their dataset, most of whom have geographic information included in their profile data. The upshot: Friendship is only indifferently a function of geographic distance; it is more closely related to what the authors call rank friendship, which rethinks distance as a function of the number of people between two points in a network, as opposed to the the actual physical distance. Fascinating stuff.