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)
Abstract:
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.
|