stanford.seal64.gif (1,768 bytes)

Broad Area Colloquium for Artificial Intelligence,
Geometry, Graphics, Robotics and Vision

Small-World Phenomena and Decentralized Search Algorithms

Jon Kleinberg
Cornell University

Monday, January 14, 2002, 4:15PM
Gates B01


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