Descendant distributions for the impact of mutant contagion on networks

Contagion, broadly construed, refers to anything that can spread infectiously from peer to peer. Examples include communicable diseases, rumors, misinformation, ideas, innovations, bank failures, and electrical blackouts. Sometimes, as in the 1918 Spanish flu epidemic, a contagion mutates at some point as it spreads through a network. Here, using a simple susceptible-infected model of contagion, we explore the downstream impact of a single mutation event. Assuming that this mutation occurs at a random node in the contact network, we calculate the distribution of the number of “descendants,” $d$, downstream from the initial “patient zero” mutant. We find that the tail of the distribution decays as $d^{-2}$ for complete graphs, random graphs, small-world networks, networks with block-like structure, and other infinite-dimensional networks. This prediction agrees with the observed statistics of memes propagating and mutating on Facebook and is expected to hold for other effectively infinite-dimensional networks, such as the global human contact network. In a wider context, our approach suggests a possible starting point for a mesoscopic theory of contagion. Such a theory would focus on the paths traced by a spreading contagion, thereby furnishing an intermediate level of description between that of individual nodes and the total infected population. We anticipate that contagion pathways will hold valuable lessons, given their role as the conduits through which single mutations, innovations, or failures can sweep through a network as a whole.

Figure 1

Simple SI model of contagion spreading on a network and its corresponding epidemic tree. Black filled circles denote susceptible nodes; red filled circles, infected nodes; red open circles, nodes infected by a mutant strain of the infection. (a) Starting with a single infected seed $O$ at time $t=0$, another node gets infected at random at the next time step. Any edge between an infected node and a susceptible node has an equal chance of being the next edge over which the contagion spreads. We keep track of which nodes transmitted and received the infection at every time step, until ultimately every node is infected. (b) The epidemic tree shows who infected whom in the contagion process depicted in panel (a). We draw this tree with the seed on top. The nodes that the seed infected are drawn in the second layer, and so on. A descendant of node $i$ is defined as any node that directly or indirectly received the infection from node $i$. Such a descendant node $j$ can be reached by starting at node $i$ and following a sequence of directed edges downward through the epidemic tree until the path ends at $j$. (c) If a mutant infection occurs at some node ($B$, in the example shown here), that node passes the mutated strain on to all its descendants (two descendants, in this example).

Figure 2

Descendant distribution for the SI contagion process on a complete graph. We simulated the SI model on complete graphs of $N={10}^4$ nodes and averaged the resulting descendant distributions over ${10}^3$ realizations of the random contagion process, each of which started with a single seed node. Filled circles show the numerically computed distribution of the number, $d$, of descendants of each node in the network. This distribution quantifies the impact that a mutant infection would have on the rest of the population, had it started at a random patient-zero node. The dashed line shows the analytical result (2). For large values of $d$, the descendant distribution declines proportional to $d^{-2}$.

Figure 3

Descendant distributions for the SI contagion process on random networks. We simulated the SI process on $z$-regular configuration models, Erdős–Rényi (ER) networks, and networks with block structure of $N={10}^4$ nodes. The block network has four equally sized Erdős–Rényi blocks and parameters $z=8.25$ and $p=0.002$. The descendant distributions have been rescaled to collapse onto a single curve. This rescaling involved adding $\tilde{x}\left(z\right)=(z-1+2p)/(z-2+2p)$ to $d$, and multiplying $P_d$ by $\tilde{x}{\left(z\right)}^{-1}$, the inverse of the scaling factor of $P_d$.

Figure 4

Descendant distributions of a SI process simulated on a Facebook subgraph. We ran simulations of the SI contagion process on a network of merged Facebook ego networks [35, 36]. Taken together, this subnetwork contains 4039 nodes and 88 234 edges. We started a contagion at a random seed node and ran the simulation until exactly a predefined number of nodes were infected. Then we stopped the spreading, obtained the descendant distribution for the realization, and started a new simulation with a seed chosen uniformly at random. The descendant distributions shown here have predefined cascade sizes 100, 400, and 2000 and are averaged over ${10}^3$ simulations for each cascade size. The smallness of the subnetwork gives rise to conspicuous finite-size effects in the tail of the distribution. Apart from these effects, the descendant distribution falls on the curve expected for highly connected infinite-dimensional networks, here illustrated with the analytical solution for the descendant distribution for contagion on the complete graph.