[an error occurred while processing this directive]

From ## The Small-World Phenomenon and Decentralized SearchBy 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
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
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
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). |