EECS Joint Colloquium Distinguished Lecture Series

Wednesday, February 6, 2002
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Dr. Jon Kleinberg

Department of Computer Science, Cornell University

Print Version

Small-World Phenomena & Decentralized Search Algorithms




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 discovering short chains of acquaintances leading to designated targets. 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 draw connections to a number of current issues in the design of agents that interact with large networked environments.

    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.