This Article Free via Open Access: OA Figures Only OA Full Text Full Text (PDF) Supporting Appendix Alert me when this article is cited Alert me if a correction is posted Services Email this article to a colleague Related articles in PNAS Similar articles in this journal Similar articles in ISI Web of Science Similar articles in PubMed Alert me to new issues of the journal Add to My File Cabinet Download to citation manager Request Copyright Permission Citing Articles Citing Articles via CrossRef Google Scholar Articles by Liben-Nowell, D. Articles by Kleinberg, J. PubMed PubMed Citation Articles by Liben-Nowell, D. Articles by Kleinberg, J. Social Bookmarking                What's this?

 Previous Article  | Table of Contents |  Next Article 

PHYSICAL SCIENCES / SOCIAL SCIENCES / COMPUTER SCIENCES / SOCIAL SCIENCES
Tracing information flow on a global scale using Internet chain-letter data

David Liben-Nowell^*, and Jon Kleinberg^,

*Department of Computer Science, Carleton College, Northfield, MN 55057; and Department of Computer Science, Cornell University, Ithaca, NY 14853

Edited by Ronald L. Graham, University of California at San Diego, La Jolla, CA, and approved January 25, 2008 (received for review September 6, 2007)

Although information, news, and opinions continuously circulate in the worldwide social network, the actual mechanics of how any single piece of information spreads on a global scale have been a mystery. Here, we trace such information-spreading processes at a person-by-person level using methods to reconstruct the propagation of massively circulated Internet chain letters. We find that rather than fanning out widely, reaching many people in very few steps according to "small-world" principles, the progress of these chain letters proceeds in a narrow but very deep tree-like pattern, continuing for several hundred steps. This suggests a new and more complex picture for the spread of information through a social network. We describe a probabilistic model based on network clustering and asynchronous response times that produces trees with this characteristic structure on social-network data.

social networks | algorithms | epidemics | diffusion in networks

Author contributions: D.L.-N. and J.K. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/cgi/content/full/0708471105/DC1.

To whom correspondence may be addressed. E-mail: dlibenno{at}carleton.edu or kleinber{at}cs.cornell.edu

© 2008 by The National Academy of Sciences of the USA

CiteULike    Complore    Connotea    Del.icio.us    Digg    What's this?

Related articles in PNAS:

In This Issue

PNAS 2008 105: 4531-4532. [Full Text]