and that we each knew our next-door neighbors for some distance in each direction. Now, following Watts and Strogatz, we add a small number of random connections—say, each of us has a single additional friend chosen uniformly at random from the full population. Short paths appear, as expected, but one can prove that there is no procedure the people living in this world can perform—using only local information and without a global “bird’s-eye view” of the social network—to forward letters to faraway targets quickly. ²⁰ In other words, in a structured world supplemented with purely random connections, the Milgram experiment would have failed: the short paths would have been there, but they would have been unfindable for people living in the network.

By extending things a little bit, however, we can get the model to capture the effect Milgram saw in real life. To do this, we keep everyone living on a two-dimensional plane but revisit the random connections, which are supposed to account for the unexpected far-flung friendships that make the world small. In reality, of course, these links are not completely random; they too are biased toward closer and more similar people. Suppose, then, that each person still has a random far-away friend, but that this friend is chosen with a probability that decays with the individual’s distance in the plane—say, by a “gravitational law” in which the probability of being friends with a person at a distance d decays as d^−r for some power r. Thus, as the exponent r increases, the world gets less purely random—the long-range friendships are still potentially far away, but overall they are more geographically clustered. What effect does this have on searching for targets in the network?

Analyzing this model, one finds that the effectiveness of Milgram-style search with local information initially gets better as r increases—because the world is becoming more orderly and easy to navigate—and then gets worse again as r continues increasing— because short paths actually start becoming too rare in the network. The best choice for the exponent r, when search is in fact very rapid, is to set it equal to 2. In other words, when the

a rumor, a political
message, or a
link to an online
video—these are
all examples of
information that
can spread from
person to person,
contagiously, in the
style of an epidemic.

probability of friendship falls off like the square of the distance, we have a small world in which the paths are not only there but also can be found quickly by people operating without a global view. ²⁰ The exponent of 2 is thus balanced at a point where short paths are abundant, but not so abundant as to be too disorganized to use.

Further analysis indicates that this best exponent in fact has a simple qualitative property that helps us understand its special role: when friendships fall off according to an inverse-square law in two dimensions, then on average people have about the same proportion of friends at each “scale of resolution”—at distances 1–10, 10– 100, 100–1000, and so on. This property lets messages descend gradually through these distance scales, finding ways to get significantly closer to the target at each step and in this way completing short chains, just as Milgram observed.

Validating and Applying the Model. When such models were first proposed, it was unclear not only how accurate they were in real life but also how to go about collecting data to measure the accuracy. To do so, you would have to convince thousands of people to report where they lived and who their friends were—a daunting task.

But of course, the public profiles on social-networking sites readily do just that, and as these sites began to grow explosively in 2003 and 2004, Liben-Nowell et al. developed a framework for using this type of data to test the predictions of the small-world models. ³⁰ In particular, they collected data from the friendship network of the public blogging site LiveJournal, focusing on half a million people who reported U.S. hometown locations and lists of friends on the site. They then had to extend the mathematical models to deal with the fact that real human population densities are highly nonuniform. To do so, they defined the distance between two people in an ordinal rather than absolute sense: they based the probability that a person v forms a link to a person w on the number of people who are closer to v than w is, rather than on the physical distance between v and w. Using this more flexible definition, the distribution of friendships in the data could