From SIAM News, Volume 37, Number 3, April 2004

The Small-World Phenomenon and Decentralized Search

By Jon Kleinberg

The small-world phenomenon -- the principle that we are all linked by short chains of acquaintances, or "six degrees of separation" -- is a fundamental issue in social networks; it is a basic statement about the abundance of short paths in a graph whose nodes are people, with links joining pairs who know one another. It is also a topic on which the feedback between social, mathematical, and computational issues has been particularly fluid.

The problem has its roots in experiments performed by the social psychologist Stanley Milgram in the 1960s; to trace out short paths through the social network of the United States, he asked participants to forward a letter to a "target person" living near Boston, with the restriction that each participant could advance the letter only by forwarding it to a single acquaintance. Milgram found that the median completed chain length was six. Why should a social network contain such short paths?

Working much more recently, applied mathematicians Duncan Watts and Steve Strogatz proposed thinking about networks with this small-world property as a superposition: a highly clustered sub-network consisting of the "local acquaintances" of nodes, together with a collection of random long-range shortcuts that help produce short paths. In addition to empirical studies of social, technological, and biological networks, Watts and Strogatz considered the following simple model system: Start with a d-dimensional lattice network, and add a small number of long-range links out of each node, to destinations chosen uniformly at random. A network created by this superposition will have local clustering and short paths, just like many of the networks found in the real world. (See Figures 1 and 2.)

Figure 1. Two-dimensional grid with a single random shortcut superimposed.

Figure 2. Two-dimensional grid with many random shortcuts superimposed (as in the Watts-Strogatz model).

But Milgram's experiment really led to two striking discoveries, of which the existence of short paths was only the first. The second was that people in society, with knowledge of only their own personal acquaintances, were collectively able to forward the letter to a distant target so quickly. Viewed in computational terms, this is a statement about the power of a routing algorithm, equipped with purely local information, to find efficient paths to a destination; that such a decentralized routing scheme is effective says something striking about the underlying social network.

Modeling this aspect of the small-world phenomenon poses further challenges: Can we find model systems for which it can be proved that Milgram-style decentralized routing will produce short paths? Here, mathematical analysis of the Watts-Strogatz model and its variants yields some surprises. For one, it is possible to prove that in the model of a d-dimensional lattice with uniformly random shortcuts, no decentralized algorithm can find short paths; this, then, is a concrete example of a network in which short paths exist, but local knowledge does not suffice to construct them.

Exploring further, though, we find that a subtle variant of the Watts-Strogatz network will in fact support efficient search: Rather than adding the long-range shortcuts uniformly at random, we add links between nodes of this network with a probability that decays like the dth power of their distance (in d dimensions). Moreover, this is the only link distribution of this form for which efficient search is possible. The intuition here is that a probability decaying like the dth power of the distance is in fact uniform over all "distance scales" -- a node is roughly as likely to form links at distances 1 to 10 as it is at distances 10 to 100, 100 to 1000, and so on. (See Figure 3.)

Figure 3. A node with several random shortcuts spanning different distance scales.

The ability to construct a searchable network in this way, with long-range links whose probabilities decay with distance, has proved useful in the design of peer-to-peer file-sharing systems on the Internet, where content must be found by nodes consulting one another in a decentralized fashion. In other words, nodes executing these look-up protocols are behaving very much like participants in the Milgram experiments -- a striking illustration of the way in which the computational and social sciences can inform one another, and the way in which mathematical models in the computational world turn into design principles with remarkable ease.

Jon Kleinberg is an associate professor of computer science at Cornell University.

Download this article as a PDF (612k).