Recently, large datasets stored on the Internet have enabled the analysis of processes, such as large-scale diffusions of information, at new levels of detail. In a recent study, Liben-Nowell and Kleinberg [(2008) Proc Natl Acad Sci USA 105:4633-4638] observed that the flow of information on the Internet exhibits surprising patterns whereby a chain letter reaches its typical recipient through long paths of hundreds of intermediaries. We show that a basic Galton-Watson epidemic model combined with the selection bias of observing only large diffusions suffices to explain these patterns. Thus, selection biases of which data we observe can radically change the estimation of classical diffusion processes. diameter | chain letters | Galton-Watson process | maximum likelihood estimation | social networks A s social network data become increasingly available in electronic form, researchers are developing more detailed and accurate pictures of the patterns of social interactions. These empirical investigations are of primary importance given the multitude of ways in which social networks affect our lives (1). However, such data come with their own idiosyncrasies. Most notably, in the past most data on social networks were obtained via questionnaires (2), interviews (3), experiments (4), or observations directly made by researchers (5), and so it was the researcher who chose the data. More recently, the availability of electronic data has made it more common for the data to choose the researcher. That is, often large and interesting datasets become available because of the electronic storage of various forms of interaction occurring via the Internet, and these then become useful test beds for theories of social networks. In this paper, we focus on the explanatory power of one inherent selection bias that comes along with many such datasets. Specifically, we examine a selection bias that arises from looking at unusually large instances of diffusion processes-with a particular application to Internet chain letters. In a recent paper (6), Liben-Nowell and Kleinberg provided an important and interesting examination of two chain letters that had wide circulation on the Internet: a petition in support of public radio and television that began circulating in 1995 and a petition against the eventual war in Iraq that circulated in 2002 and 2003. By obtaining many copies of the e-mails and tracing through the ordered lists of names added to each petition, Liben-Nowell and Kleinberg were able to reconstruct large portions of the trees of dissemination of these chain letters. The remarkable aspect of Liben-Nowell and Kleinberg's findings is that these trees do not exhibit the short distances between nodes that are characteristic of many social networks (7, 8) . Instead, these trees have very small widths (i.e., many nodes have a single offspring), and the median node receives the letter after it has been through hundreds of intermediaries. To understand why the paths of chain letter dissemination that Liben-Nowell and Kleinberg reconstruct are puzzling, let us discuss what seems to be the most natural and simple model of how such a process would operate. That model is the classical one of Galton and Watson (9), which was developed in the 1870s to study the longevity of family names in a patrilineal system. Galton and Watson proposed a branching process where each node has a random number of children, drawn independently according to the same distribution. The process can also serve as a model of an epidemic, where the number of children is the number of others a given node infects. In this application, the number of children of a given sender is the number of other people who sign the petition immediately below that sender's signature in various versions of the letter that branch off as various recipients sign. It is well known (10) that the key quantity in characterizing the asymptotic properties of this process is the expected number of children per node. If this quantity is below the threshold of unity, then the process is called subcritical and with probability one it will end in extinction after a finite number of steps. If the expected number of children is more than one, then the process is called supercritical and will continue forever with positive probability. (We ignore the nongeneric borderline case in which each node has exactly one child in expectation.) The puzzle is that neither regime seems to explain the observed data. The two datasets that Liben-Nowell and Kleinberg study have more than 10,000 nodes each, whereas it is quite rare for a subcritical branching process with reasonable parameters to have more than a dozen nodes. Thus, the typical subcritical tree is a poor match to the data on many dimensions. On the other hand, if one tries to fit the data with a supercritical process, then the trees that emerge have huge breadths, branch very frequently, and do not have the long chains that are observed in the data. In view of this, Liben-Nowell and Kleinberg developed a richer network-based model of chain letter distribution with two important features: asynchronous response times and group replies. The realizations of their process that are as large as the observed diffusions have the correct shapes. We show that, despite their surprising appearances, the observed trees have a global structure that corresponds to a basic and classical process. In particular, the simple Galton-Watson epidemic model suffices to generate trees reaching many nodes yet having long chains as in the data. To show this, we first fit the parameters of a Galton-Watson process by using maximumlikelihood estimation on the basis of one of the trees inferred by Liben-Nowell and Kleinberg. Then we simulate the process and examine only the rare outcomes in which a chain letter with these parameters spreads as widely as those that were observed. Most realizations are very small and have virtually no chance of being observed; we are interested in the properties of those rare ones that are big enough to match the public radio and war petitions described above. Simulated outcomes from this conditional distribution match the real observations closely on global dimensions such as tree depth, width, and the distribution of children per node. The seeming obstacle discussed above-that neither of
In this sense, our data avoids selection bias which strongly influences the estimation of these processes REF .
Using selection bias to explain the observed structure of Internet diffusions
Proceedings of the National Academy of Sciences of the United States of America
Proceedings of the National Academy of Sciences of the United States of America
Medicine Computer Science