Workshop on Online Social
December 7, 2007.
Wayfinding in Social
David Liben-Nowell (Carleton College)
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.