Swarthmore College Department of Computer Science

Talk by David Liben-Nowell

Geographic Routing In Social Networks
Tuesday, October 18
SCI 240, 4:15 pm

Abstract

If you have an urgent personal message that you have to send to Dick Cheney by passing it from one friend to another, how would you send it to him? Beginning with the "six degrees of separation" experiments of Stanley Milgram in the 1960's, interest in the structure and analysis of social networks (think Friendster/Orkut/Facebook) has blossomed into a full-fledged area of research. More specifically, many interesting studies of our "small world" -- so called because two arbitrary people are likely to be connected by a short chain of intermediate friends -- have been carried out over recent years.

In this talk, I will highlight the last forty years of research into small-world phenomena, and then describe a new model for friendship formation in social networks that is based upon the geographic locations of the people within it. I'll show that the model accurately predicts about two-thirds of self-reported friendships in the LiveJournal online blogging community. Furthermore, I'll describe theoretical results that say that every social network that adheres to this model will be a small world. Time permitting, I will also mention applications to neoconservativism and the Boston Red Sox, Lake of the Woods County (Minnesota) and Allen Iverson, and the Swarthmore College Department of Educational Studies.

Joint work with Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins (Yahoo! Research Labs) and Jasmine Novak (IBM Almaden).