This Article Free via Open Access: OA 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 Similar articles in this journal 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?

COMPUTER SCIENCES / SOCIAL 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)

Abstract

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.

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?

Current Issue | Archives | Online Submission | Info for Authors | Editorial Board | About Subscribe | Advertise | Contact | Site Map Copyright © 2008 by the National Academy of Sciences