then in fact be closely approximated by the natural generalization of the inverse-square law.

It was difficult not to be a bit surprised by the alignment of theory and measurement. The abstract models were making very specific predictions about how friendships should depend on physical distance, and these predictions were being approximately borne out on data arising from real-world social networks. And there remains a mystery at the heart of these findings. While the fact that the distributions are so close does not necessarily imply the existence of an organizing mechanism (for example, see Bookstein⁵ for a discussion of this general issue in the context of social-science data), it is still natural to ask why real social networks have arranged themselves in a pattern of friendships across distance that is close to optimal for forwarding messages to faraway targets. Further, whatever the users of LiveJournal are doing, they are not explicitly trying to run versions of the Milgram experiment—if there are selective pressures driving the network toward this shape, they must be more implicit, and it remains a fascinating open question whether such forces exist and how they might operate.

Other research using online data has considered how friendship and communication depend on nongeographic notions of “distance.” For example, the probability that you know someone is affected by whether you and they have similar occupations, cultural backgrounds, or roles within a large organization. Adamic and Adar studied how communication depends on one such kind of distance: they measured how the rate of email messaging between employees of a corporate research lab fell off as they looked at people who were farther and farther apart in the organizational hierarchy. ¹ Here too, this rate approximated an analogue of the inverse-square law— in a form adapted to hierarchies^{21, 39}—although the messages in the researchers’ data were skewed a bit more toward long-range contacts in the organization than short-range ones.

Finally, these models can rapidly turn into design principles for distributed computing systems as well. Modern peer-to-peer file-sharing systems

are built on the principle that there should not be a central index of the content being shared (in contrast, for example, to the way in which search engines like Google provide a central index for Web pages). As a result, looking up content in a peer-to-peer system follows a Milgram-style approach in which the hosts participating in the system must forward requests with only a local view. ³¹ Mathematical models of small worlds—originally built with human networks in mind—can provide insights into the design of efficient solutions for this distributed search problem as well.

We’ve thus seen how viewing such models in the online domain can help us understand the global layout of social-networking sites, the flow of communications within organizations, and the design of peer-to-peer systems. We now look at how the insights we’ve gained here can provide perspective on an important related problem—the spread of information through large populations.

social contagion and
the spread of ideas

Milgram’s experiment was about focusing a message on a particular target, but much of the information that flows through a social network radiates outward in many directions at once. 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. This is an important process to understand because it is part of a broader pattern by which people influence one another over longer periods of time, whether in online or offline settings, to form new political and social beliefs, adopt new technologies, and change personal behavior—a process that sociologists refer to as the “diffusion of innovations.” ³⁵ But while the outcomes of many of these processes are easily visible, their inner workings have remained elusive.

Some of the basic mathematical models for the diffusion of innovations posit that people’s adoption of new behaviors depends in a probabilistic way on the behaviors of their neighbors in the social network: as more and more of your friends buy a new product or join a new activity, you

are more likely to do so as well. ¹³ Recent studies of online data have provided some of the first pictures of what this dependence looks like over large populations. In particular, Leskovec, Adamic, and Huberman studied how the probability of purchasing books, DVDs, and music from a large online retailer increased with the number of email recommendations a potential customer received. ²⁵ Backstrom et al. determined the probability of joining groups in a large online community as a function of the number of friends who already belonged to the group. ⁴ And Hill, Provost, and Volinsky¹⁶ analyzed how an individual’s adoption of a consumer telecommunications service plan depended on his or her connections to prior adopters of the service.

While the probability of adopting a behavior increases with the number of friends who have already adopted it, there is a “diminishing returns” pattern in which the marginal effect of each successive friend decreases. ^{4, 25} In many cases, however, an interesting deviation from this pattern is observed—a “0– 1–2 effect,” in which the probability of joining an activity when two friends have done so is significantly more than twice the probability of joining when only one has done so. ⁴

The structure of cascading behavior. Beyond these local mechanisms of social influence, it is instructive to trace out the overall patterns by which influence propagates through a large social network. In recent work, David Liben-Nowell and I investigated such global-scale processes by gathering data on chain-letter petitions that had spread widely over the Internet. ²⁹ A particularly pervasive chain letter, which spread in 2002 and 2003, purported to organize opposition to the impending invasion of Iraq. Each copy of the petition contained the list of people who had received that particular copy, in the order in which they added their names and then passed it on to others in their email address books. In the process, several hundred of these copies had been sent to Internet mailing lists; by retrieving them from the mailing lists’ archives, we could reconstruct a large fragment of the branching tree-like trajectory by which the chain letter had spread.