Workshop on Online Social Networks
    Participation by invitation only


Microsoft Research Cambridge, UK.

December 7, 2007.



Wayfinding in Social Networks



David Liben-Nowell         (Carleton College)





Good urban planners and architects pay considerable attention in their design to the way in which users will use and traverse the space.  In the physical world, this manifests itself in helpful signage, careful placement of paths and roads, and the like.  But what does helpful signage mean in a social network?  For that matter, what does use and traversal of a social network mean?  One answer, following a line of research beginning with the "six degrees of separation" experiments of Stanley Milgram in the 1960's, is a person S searching for a chain of friends to connect S to a particular information source (a new job, a date, a tutor who can give lessons on how to punt, ...) or a particular destination person T.  Of course, S does not have global information about the network, and instead must try to find T using only a limited "local" view of the network.  Despite their organic, non-engineered nature, real-world social networks support remarkably efficient search of this type.  In this talk, I will highlight the last forty years of research into this "small-world phenomenon", emphasizing the design and analysis of algorithms for the efficient navigation of social networks. Time permitting, I will try to draw some connections to the design of networks that support efficient "local" search.

Presentation slides