The structure of the tree was surprising, as it challenged our small-world intuitions. Rather than fanning out widely, reaching many people with only a few degrees of separation, the chain letter spread in a deep and narrow pattern, with many paths consisting of several hundred steps. The short chains in the social network were still there, but the chain letter was getting to people by much more roundabout means. Moreover, we found a very similar structure for the one other large-scale chain letter on which we could find enough mailing-list data, this one claiming to be organizing support for National Public Radio.

Why this deep and narrow spreading pattern arises in multiple settings remains something of a mystery, but there are several hypotheses for reconciling it with the structure of a small world. In our work on chain letters, we analyzed a model based on the natural idea that people take widely varying amounts of time to act on messages as they arrive: when recipients forward the chain letter at different times to highly overlapping circles of friends, it can in effect “echo” through dense clusters in the social network, following a snaking path rather than a direct one. Simulations of this process on real social networks such as the one from LiveJournal produce tree structures very similar to the true one we observed. ²⁹

It is also plausible that the nature of social influence—properties such as the 0– 1–2 effect in particular—play an important role. Suppose that most people in the social network need to receive a copy of the letter at least twice before actually signing their name and sending it on. As Centola and Macy have recently argued, our long-range friendships may be much less useful for spreading information in situations such as these: you can learn of something the first time from a far-flung friend, but to get a second confirmatory hearing you may need to wait for the information also to arrive through your more local contacts. ⁶ Such a pattern could slow down the progress of a chain letter, forcing it to slog through the dense structure of our local connections rather than exploit the long-range shortcuts that make the world small.

the availability
of such rich and
plentiful data on
human interaction
has closed an
important feedback
loop, allowing us
to develop and
evaluate models of
social phenomena
at large scales and
to use these models
in the design of
new computing
applications.

Contagion as a design principle. As with the decentralized search problem at the heart of the small-world phenomenon, the idea of contagion in networks has served as a design principle for a range of information systems. Early work in distributed computing proposed the notion of “epidemic algorithms,” in which information updates would be spread between hosts according to a probabilistic contagion rule. ⁸ This has led to an active line of research, based on the fact that such algorithms can be highly robust and relatively simple to configure at each individual node.

More recently, contagion and cascading behavior have been employed in proposals for social computing applications such as word-of-mouth recommendation systems, ²⁵ incentive mechanisms for routing queries to individuals possessing relevant information, ²² and methods to track the spread of information among Weblogs. ^{2, 14} Large-scale social contagion data also provides the opportunity to identify highly influential sets of people in a social network—the set of people who would trigger the largest cascade if they were to adopt an innovation. ¹¹ The search for such influential sets is a computationally difficult problem, although recent work has shown that when social influence follows the kind of “diminishing returns” pattern discussed here, it is possible to find approximate methods with provable guarantees. ^{19, 32}

further Directions

Research on large-scale social-network data is proceeding in many further directions as well. While much of what we have been discussing involves the dynamic behavior of individuals in social networks, an important and complementary area of inquiry is how the structure of the network itself evolves over time.

Recent studies of large datasets have shed light on several important principles of network evolution. A central one, rooted in early work in the social sciences, is the principle of “preferential attachment”—the idea that nodes that already have many links will tend to acquire them at a greater rate. ³³ An active line of research has shown how preferential attachment can lead to the highly