Computer Science

A Big World After All?

See allHide authors and affiliations

Science  11 Apr 2008:
Vol. 320, Issue 5873, pp. 156
DOI: 10.1126/science.320.5873.156d

From the spread of viral epidemics to the flow of information in a social network, a key question is the nature of the pathway taken. Epidemic-style models assume that propagation should occur from one individual to many others, following small-world principles. If the viral chain does not die out, it can be mapped as a tree-like structure with many branches that have short paths from the root (or original source). Liben-Nowell and Kleinberg looked at the spread of data on the Internet by examining the lists of names in two email petitions and found that, rather than expanding to many individuals in a few steps, the tree structures were very narrow and several hundreds of layers deep, with large variations in the time needed to reach the edges of the network. By running simulations on other networks, the authors confirmed that the distribution could not be modeled by a random epidemic process. However, they successfully reproduced the long, narrow trees by altering the model to allow for variations in the response time of the recipients (asynchronous response) and to allow recipients the option of either forwarding the message or group replying (back-transmission) to those already in the list. The results highlight how the transmission of data can vary from the small-world network in which the dissemination occurs. — MSL

Proc. Natl. Acad. Sci. U.S.A. 105, 4633 (2008).

Navigate This Article