Broad Area Colloquium for Artificial Intelligence,
Geometry, Graphics, Robotics and Vision
Small-World Phenomena and Decentralized Search Algorithms
Monday, January 14, 2002, 4:15PM
Increasingly, one encounters settings in which agents
must search or navigate in a large decentralized network
without knowledge of the global structure.
Such a phenomenon arises in the behavior of users browsing
the Web by following hyperlinks; in the design of focused crawlers
and other mechanisms that explore the Web's links to gather information;
and in the search protocols underlying decentralized
peer-to-peer systems such as Gnutella, Freenet, and recent
research prototypes through which users can share resources
without a central server.
Our recent work on decentralized search has led back to
Stanley Milgram's famous `small-world' experiments,
which established the `six degrees of separation' principle
and showed that individuals are very effective at finding
short chains of acquaintances leading to designated targets.
These experiments dealt precisely with a form of search in a social network,
with people as nodes and links joining pairs of people who know each other.
We wish to understand the structure of networks in which such
a phenomenon emerges -- in which navigation with purely local
information can be efficient. We develop a series of models
that delineate some of the underlying properties of networks
supporting efficient decentralized search, and we draw
connections to a number of current issues in the design of agents
that interact with large networked environments.
About the Speaker
Jon Kleinberg received his Ph.D. in computer science from MIT in 1996.
He subsequently spent a year as a Visiting Scientist at
the IBM Almaden Research Center, and is now an Associate Professor
in the Department of Computer Science at Cornell University.
His research interests are centered around algorithms that exploit
the combinatorial structure of networks and information.
He is a recipient of an NSF Career Award, an ONR Young Investigator Award,
research fellowships from the Sloan and Packard Foundations, and the
National Academy of Sciences Award for Initiatives in Research.
Back to the Colloquium Page