Small-World Phenomena and the Dynamics of Information
Jon Kleinberg
Cornell University

Abstract: 

The information we deal with is taking on an increasingly networked
character.  In part, this is because we now have the resources to
represent and analyze enormous link-structured datasets.
But networked content is also being created at a phenomenal rate;
although the World Wide Web as we know it is barely a decade old,
it has already established itself as a new medium.

These developments have led to an emerging study of complex networks,
and a range of interesting research challenges.
One recurring theme in this area is the dynamic processes that
unfold within such networks -- the flow of information through them,
and the behavior of decentralized search algorithms that find
information without knowledge of the global structure.
Such processes are at work, for example, in the behavior of users 
browsing the Web; in the design of focused Web crawlers; and in 
the search protocols underlying peer-to-peer systems.

We develop a series of models that delineate some of the 
properties of networks in which these types of processes 
operate efficiently, and draw connections to a number of 
current issues in the design of decentralized network algorithms.  
We also relate the underlying phenomena to Stanley Milgram's 
striking set of `small-world' experiments, and other findings 
about the structure of large-scale social networks.