Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time

For a reliable prediction of an epidemic or information spreading pattern in complex systems, well-defined measures are essential. In the susceptible-infected model on heterogeneous networks, the cluster of infected nodes in the intermediate-time regime exhibits too large fluctuation in size to use its mean size as a representative value. The cluster size follows quite a broad distribution, which is shown to be derived from the variation of the cluster size with the time when a hub node was first infected. On the contrary, the distribution of the time taken to infect a given number of nodes is well concentrated at its mean, suggesting the mean infection time is a better measure. We show that the mean infection time can be evaluated by using the scaling behaviors of the boundary area of the infected cluster and use it to find a nonexponential but algebraic spreading phase in the intermediate stage on strongly heterogeneous networks. Such slow spreading originates in only small-degree nodes left susceptible, while most hub nodes are already infected in the early exponential-spreading stage. Our results offer a way to detour around large statistical fluctuations and quantify reliably the temporal pattern of spread under structural heterogeneity.

Figure 1

Fluctuation in the spreading of infection on SF networks. The fraction of simulation runs of the SI model yielding $I$ infected nodes at time $t$ is color-coded. The SI model with infection rate $\lambda ={10}^{-4}$ is simulated 100 times in each of 200 SF networks of $N={10}^6$ nodes, $L=2\times {10}^6$ links (the mean degree $\langle k\rangle =4$), and degree exponent $\gamma =2.75$. Shown are ${\langle I\rangle }_t, {\langle t\rangle }_I$, and the fastest and slowest spreading, taking the shortest and longest time to infect $I_0=100$ nodes, respectively.

Figure 2

Statistics of the infection spreading in the SI model on SF networks with $\gamma =2.75$. (a) The probability distribution $P_t\left(I\right)$ of $I$ at time $t$ for the network of $N={10}^6$. ${\sigma }_{I;t}$ is its standard deviation. The dashed line $y=0.003x^{-1}$ is shown as a guide. Inset: ${\sigma }_{I;t}$ versus the mean ${\langle I\rangle }_t$ for different $N$. The lines $y=x$ (solid) and $y=30x^{4/5}$ (dashed) are shown. (b) The distribution $P_I\left(t\right)$ of the time $t$ taken to infect $I$ nodes. ${\langle t\rangle }_I$ and ${\sigma }_{t;I}$ are its mean and standard deviation. Inset: ${\sigma }_{t;I}$ versus ${\langle t\rangle }_I$. The line $y=x$ (solid) is shown as a guide.

Figure 3

Role of infecting hubs in infection spreading on a SF network with $\gamma =2.75$. The cluster of the first 80 infected nodes appears (a) at the observation time $t=550$ (fastest spreading) or (b) at $t=110870$ (slowest spreading). Node size and color represent the degree and the infection order of each node. (c) Plot of $I$ versus the difference between $t$ and the hub-infection time $t_{\mathrm{hub}}$. The mean and the standard deviation are shown, along with a solid line fitting Eq. (2) to the data.

Figure 4

The volume of the infected cluster and the mean infection time ${\langle t\rangle }_I$ for $N={10}^6$. (a) The internal volume ${\langle \mathbb{C}\rangle }_I$ versus $I$. The approximation in Eq. (6) is shown as a guide. (b) The degree ${\langle k_{\mathrm{new}}\rangle }_I$ of the newly infected node given $I$ infected nodes. Its cumulative sum gives the whole volume ${\langle \mathbb{V}\rangle }_I$ as in Eq. (10). The lines represent $\langle k_{\mathrm{nn}}\rangle \left(I\right)/\langle k_{\mathrm{nn}}\rangle$ computed using Eq. (8) with $P_{\mathrm{degree}}\left(k\right)$ from the simulations used. (c) Plots of $I$ versus ${\langle t\rangle }_I$ from simulations (points) and from the solutions (lines) to Eq. (4) with Eqs. (6) and (10) and the initial condition $I_0=100$ and $t_0={\langle t\rangle }_{I_0}$.

Figure 5

Relative fluctuations of the number of infected nodes and the infection time in the SI model on SF networks with $\gamma =2.75$ and different numbers of nodes $N$. (a) The ratio of the standard deviation ${\sigma }_{I;t}$ to the mean ${\langle I\rangle }_t$ of the number of infected nodes at time $t$. (b) The ratio of the standard deviation ${\sigma }_{t;I}$ to the mean ${\langle t\rangle }_I$ of the time to infect $I$ nodes in the same networks as in (a). (c) The region where ${\sigma }_{t;I}<{\langle t\rangle }_I$ and ${\sigma }_{I;t}>{\langle I\rangle }_t$ is shaded in the $(t,I)$ plane.

Figure 6

Ratio of the mean number of infected nodes ${\langle I\rangle }_t$ at time $t$ to the value of $I$ at which ${\langle t\rangle }_I=t$, denoted by $I_{{\langle t\rangle }_I=t}$. Time $t$ in the horizontal axis is scaled by $t_c\equiv {\langle t\rangle }_{I_c}$ with $I_c$ in Eq. (9). (a) The ratio ${\langle I\rangle }_t/I_{{\langle t\rangle }_I=t}$ in the SF networks with $\gamma =2.75$ and different numbers of nodes $N$. (b) The ratio in the SF networks with $\gamma =3.6$. (c) The ratio in the ER networks. (d) The maximum of the ratio ${max}_t({\langle I\rangle }_t/I_{{\langle t\rangle }_I=t})$ versus system size $N$.

Figure 7

Statistics of the hub-infection time and the number of infected nodes for a given hub-infection time. (a) The distributions $P\left(t_{\mathrm{hub}}\right)$ of the hub-infection time in the SF and ER networks of $N={10}^6$. They are fitted to log-normal distributions with mean $\langle ln{t}_{\mathrm{hub}}\rangle =9.01,9.74$, and 8.12 and standard deviation ${\sigma }_{ln{t}_{\mathrm{hub}}}=0.78,0.41$, and 1.22 of $ln{t}_{\mathrm{hub}}$ for SF networks with $\gamma =2.75,3.6$ and the ER networks, respectively. (b) The conditional probability distribution $P_{t,t_{\mathrm{hub}}}\left(I\right)$ of the number of infected nodes at $t$ for selected hub-infection times $t_{\mathrm{hub}}$ in SF networks with $\gamma =2.75$ and $N={10}^6$. They are also fitted to log-normal distributions with the mean and standard deviation of $lnI$ at time $t={10}^4$ for given $t_{\mathrm{hub}}$ shown in the inset.

Figure 8

Simulation results of the SI model on (a)–(d) SF networks with $\gamma =3.6$ and (e)–(h) ER networks. (a) and (e) The fraction of simulation runs yielding $I$ infected nodes at time $t$ is color-coded in the $(t,I)$ plane. (b) and (f) The probability distribution $P_t\left(I\right)$ for $N={10}^6$. Inset: the standard deviation ${\sigma }_{I;t}$ versus the mean ${\langle I\rangle }_t$. (c) and (g) The probability distribution $P_I\left(t\right)$ for $N={10}^6$. Inset: the standard deviation ${\sigma }_{t;I}$ versus the mean ${\langle t\rangle }_I$. (d) and (h) Plot of $I$ versus $t-t_{\mathrm{hub}}$. A solid line fitting Eq. (2) is shown.

Figure 9

The dependence of the hub-infection time on the initially infected node (seed). (a) The hub-infection time $t_{\mathrm{hub}}$ increases with the distance $d_{\mathrm{seed},\mathrm{hub}}$ of the seed node to the nearest hub node, having a degree larger than $0.3k_{\max }$, in SF networks with $\gamma =2.75$ and different numbers of nodes $N$. (b) Plot of $t_{\mathrm{hub}}$ versus the degree $k_{\mathrm{seed}}$ of the seed node.

Figure 10

The ratio of the standard deviation ${\sigma }_{\mathbb{B};I}$ to the mean ${\langle \mathbb{B}\rangle }_I$ of the number of boundary links for a given number of infected nodes $I$ in SF networks with $\gamma =2.75$.