Temporal dynamics of connectivity and epidemic properties of growing networks

Traditional mathematical models of epidemic disease had for decades conventionally considered static structure for contacts. Recently, an upsurge of theoretical inquiry has strived towards rendering the models more realistic by incorporating the temporal aspects of networks of contacts, societal and online, that are of interest in the study of epidemics (and other similar diffusion processes). However, temporal dynamics have predominantly focused on link fluctuations and nodal activities, and less attention has been paid to the growth of the underlying network. Many real networks grow: Online networks are evidently in constant growth, and societal networks can grow due to migration flux and reproduction. The effect of network growth on the epidemic properties of networks is hitherto unknown, mainly due to the predominant focus of the network growth literature on the so-called steady state. This paper takes a step towards alleviating this gap. We analytically study the degree dynamics of a given arbitrary network that is subject to growth. We use the theoretical findings to predict the epidemic properties of the network as a function of time. We observe that the introduction of new individuals into the network can enhance or diminish its resilience against endemic outbreaks and investigate how this regime shift depends upon the connectivity of newcomers and on how they establish connections to existing nodes. Throughout, theoretical findings are corroborated with Monte Carlo simulations over synthetic and real networks. The results shed light on the effects of network growth on the future epidemic properties of networks and offers insights for devising a priori immunization strategies.

Figure 1

Simulation results for the assessment of the theoretical prediction of the time-dependent degree distribution (10). Markers represent simulation results, averaged over 50 Monte Carlo trials. Shaded areas pertain to the theoretical prediction. Shades are used instead of linear plots for better visibility. The initial substrate is a $\text{SW}(3,400,0.05)$ network, as described in the text. The degree distribution of the initial substrate corresponds to the curve depicted for $t=0$. The parameters of the growth mechanism are $\beta =4$ and $\theta =5.2$, which are example values chosen for expository purposes. As time progresses, the initial lump, which is concentrated around the mean degree of the initial substrate—that can be obtained from $2\times 3+0.05\times (400-2\times 3)$, which is close to 26—loses its mass, because new nodes are being introduced to the network. Newcomers have initial degree $\beta =4$; hence, probability mass shifts leftwards. Note that the time axis is not linear: Few time steps are chosen for illustrative purposes to maintain convenience of vision.

Figure 2

Simulation results for the assessment of the theoretical prediction of the time-dependent degree distribution (10) (the view angle is rotated to achieve better visibility; hence, the right-to-left ordering of time steps). The markers represent simulation results, and filled areas represent theoretical predictions. The simulation results are averaged over 50 Monte Carlo trials. The initial substrate is a BA network of 2000 nodes, grown with $\beta =5$. It is visible that at $t=0$ the peak of the degree distribution is at $k={\beta }_0=5$. The degree distribution of the initial substrate is approximately power law, starting from $k=5$. As new nodes are introduced, the population of nodes with degree $k=\beta =3$ increases. The lump concentrated around $k=5$ loses its mass as time progresses, and the probability mass moves towards $k=3$. In the limit as $t\to \infty$, we get a power-law degree distribution starting at $k=3$.

Figure 3

Simulation results for the assessment of the theoretical prediction of the time-dependent degree distribution (10). The substrate is an ER network with 150 nodes. The existence probability of each link is 0.05. The growth parameters are $\beta =3$ and $\theta =1.9$. The markers represent simulation results, and filled areas represent theoretical predictions. The simulation results are averaged over 100 Monte Carlo trials.

Figure 4

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is an ER network of 1000 nodes, where the probability of existence for each link is equal to 0.02. The growth parameters are $\beta =12$ and $\theta =3.2$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14).

Figure 5

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is a small-world network, namely a $\text{SW}(10,1000,0.05)$ network. The growth parameters are $\beta =10$ and $\theta =12.5$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14). The inset shows the theoretical prediction for the second moment of the degree distribution.

Figure 6

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is a an ER network with 1000 nodes. the existence probability of links is 0.1. The growth parameters are $\beta =1$ and $\theta =50$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14). The inset shows the theoretical prediction for the second moment of the degree distribution. As a result of the addition of new incoming nodes to the network, the epidemic threshold increases, making the network more resilient to endemic outbreaks.

Figure 7

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is the social network of dolphins [55]. The initial connectivity of incoming nodes is $\beta =1$. The markers represent simulation results, averaged over 100 Monte Carlo trials. The solid line represents the theoretical prediction (14).

Figure 8

Temporal evolution of the epidemic threshold for the SIR model. The initial substrate is an ER network with 500 nodes, with link creation probability of 0.2. The growth parameters are $\beta =5$ and $\theta =20$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (16). The inset shows the theoretical prediction for the second moment of the degree distribution, which is invoked in the calculation of the epidemic threshold (16).

Figure 9

Temporal evolution of the basic reproduction number in the SIR model. The initial substrate is a BA tree with 100 nodes. The initial attractiveness is $\theta =5.2$. The transmission rate is $\eta =0.05$ and the recovery rate is $\mu =0.2$. The solid markers are averaged over 100 Monte Carlo trials. The solid line represents the theoretical prediction (18). The initial network is secure, as ${\mathcal{R}}_0$ is below unity. As the network grows, the incoming node can drive ${\mathcal{R}}_0$ above unity, making the system susceptible to endemic disease outbreaks.

Figure 10

Temporal evolution of the basic reproduction number in the SIR model. The initial substrate is an ER network with 200 nodes. The probability of existence of links is 0.1. The initial attractiveness in the growth process is $\theta =10$. The transmission rate is $\eta =0.01$ and the recovery rate is $\mu =0.2$. The solid markers are averaged over 100 Monte Carlo trials. The solid line represents the theoretical prediction (18). The initial network is secure, as ${\mathcal{R}}_0$ is below unity. As the network grows, if $\beta$ is sufficiently large, incoming node can drive ${\mathcal{R}}_0$ above unity, making the system susceptible to endemic disease outbreaks.

Figure 11

Temporal evolution of the basic reproduction number in the SIR model for the social network of dolphins. The initial attractiveness in the growth process is $\theta =5$. The transmission rate is $\eta =0.04$ and the recovery rate is $\mu =0.22$. The solid markers are averaged over 100 Monte Carlo trials. The solid line represents the theoretical prediction (18). It is readily discernible that higher values of $\beta$ result in faster rates of increase in ${\mathcal{R}}_0$. This means that the more gregarious the newcomers are, the more the network will be driven towards a potential endemic.

Figure 12

Temporal evolution of ${\mathcal{R}}_0$ in the SIR model for the social network of dolphins. The initial connectivity of incoming nodes is $\beta =2$. The transmission rate is $\eta =0.04$ and the recovery rate is $\mu =0.22$. The solid markers are averaged over 100 Monte Carlo trials. The solid line represents the theoretical prediction (18). The figure indicates that the higher the value of $\theta$ (initial attractiveness), the greater will be the future resilience of the network against endemic outbreaks. This means that less values of $\theta$, which is tantamount with more weight to be given by incoming nodes to the degrees of existing nodes, the more susceptible the network will be against endemic outbreaks.

Figure 13

Theoretical prediction and the simulation results for the growth process, using the social network of dolphins as the substrate. The growth parameters are $\beta =2$ and $\theta =10$.

Figure 14

Theoretical prediction and the simulation results for the growth process, using the network of collaborations between scholars of network science as the substrate for the growth process. The growth parameters are $\beta =8$ and $\theta =9.5$.

Figure 15

Theoretical prediction and the simulation results for the growth process, using the network of collaborations between condensed matter physicists as the substrate for the growth process. The growth parameters are $\beta =8$ and $\theta =9.5$.

Figure 16

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is a ring with 1000 nodes. The growth parameters are $\beta =1$ and $\theta =1.1$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14). The inset shows the theoretical prediction for the second moment of the degree distribution. As a result of the addition of new incoming nodes to the network, the epidemic threshold diminishes, making the network more susceptible to endemic outbreaks.

Figure 17

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is a complete graph with 200 nodes. The growth parameters are $\beta =1$ and $\theta =1.1$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14). The inset shows the theoretical prediction for the second moment of the degree distribution. As a result of the addition of new incoming nodes to the network, the epidemic threshold diminishes, making the network more susceptible to endemic outbreaks.

Figure 18

Temporal evolution of the epidemic threshold for the SIS model. The initial substrate is a random recursive tree with 1000 nodes. The growth parameters are $\beta =4$ and $\theta =0$. The error bars pertain to 1000 Monte Carlo simulations. The solid line represents the theoretical prediction (14). The inset shows the theoretical prediction for the second moment of the degree distribution.