key: cord-0010878-udro8rnr
authors: Chauhan, Sanjeev Kumar
title: Discrete-time dynamic network model for the spread of susceptible-infective-recovered diseases
date: 2017-07-05
journal: Phys Rev E
DOI: 10.1103/physreve.96.012305
sha: b61df137225252db4f3617f0d2b284a191e19831
doc_id: 10878
cord_uid: udro8rnr

We propose a discrete-time dynamic network model describing the spread of susceptible-infective-recovered diseases in a population. We consider the case in which the nodes in the network change their links due to social mixing dynamics as well as in response to the disease. The model shows the behavior that, as we increase social mixing, disease spread is inhibited in certain cases, while in other cases it is enhanced. We also extend this dynamic network model to take into account the case of hidden infection. Here we find that, as expected, the disease spreads more readily if there is a time period after contracting the disease during which an individual is infective but is not known to have the disease.

The importance of the contact pattern of individuals in epidemic spreading has long been acknowledged by researchers [1] [2] [3] [4] . With the growth of the field of complex networks, there have been a number of studies on infection spreading on networks with nontrivial properties [5] [6] [7] [8] [9] [10] [11] . Typically, the underlying network in epidemic-spreading models is considered to be static. One can then study the effect of network structure on disease propagation. While the assumption of a static network may work well for cases in which the topology of the network does not change significantly during the course of the spreading process, in general we cannot neglect the fact that human contacts evolve over time. Depending on the disease and the type of contacts in which we are interested, the time scales for the change of human contacts and the spread of an epidemic may vary. To take into account the changing contacts of individuals, many researchers have considered disease spread on networks in which links change over time [12] [13] [14] [15] .

In the epidemiological literature, dynamic models where contacts are constantly being formed and dissolved have been considered. Using models based on partnership formation [16] [17] [18] , one can study the effect of dynamic contacts due to mixing. These models do not take into account the contact networks behind partnership formation and assume that contacts form at random. Thus, attempts have also been made to consider the underlying network structure in disease propagation models. For example, Volz and Meyers [15] considered a susceptibleinfective-recovered (SIR) model on a full network in which each individual's contacts change in time. In their model, referred to as the neighbor exchange model, the dynamics of partnership is implemented through edge swapping between two already connected pairs of nodes.

In the complex network community, a class of dynamic network models that has been considered is the so called adaptive network models. In these models, a network's contacts change in response to the disease. Gross et al. [12] studied susceptible-infective-susceptible (SI S) dynamics on * dr.sanjeevk.chauhan@gmail.com adaptive networks where with a given constant probability, susceptibles break their links with infected neighbors and connect the broken links to randomly chosen susceptibles. With changing rewiring rates, their model shows interesting behavior where bistable and oscillatory states are possible. Other adaptive network models with a rewiring procedure have also been considered [13, 14] . A review of epidemic modeling in complex networks can be found in Ref. [19] .

In our study of epidemic spreading on complex networks, we consider a discrete-time dynamic network model that has additional dynamics compared to the simpler models discussed above. The proposed model tries to capture some of the important features of the dynamics of real human networks. In this model, social mixing dynamics and disease evasion causes change in network topology. Social mixing results in the constant evolution of contacts, which is independent of the disease status of the nodes, while disease evasion causes suppression of susceptible-infected links in the network due to the avoidance of infected nodes by the susceptible nodes. We study SIR disease on such dynamic networks where, at any given time, the nodes could be in one of the three possible states, namely susceptible (S), infective (I ), and removed (R). Here, R represents the state in which the node is removed from the network and no longer takes part in any kind of dynamics. The model considers the case of imperfect evasion where susceptible nodes cannot avoid infected nodes completely when new connections are formed in the network. This is in contrast to other models where, after the susceptible-infected links are broken, either the broken links are removed or susceptible nodes reconnect the broken links to noninfected nodes in the network [12] [13] [14] . In our study, we focus on how the above-mentioned network dynamics influences the value of disease transmission probability above which the disease infects a finite fraction of the population in the limit of infinite system size.

We also study the case of hidden infection in the dynamic network model discussed above. Here we consider the case in which there is a period after an individual contracts an infection during which the individual is infective but asymptomatic. Thus, contacts between infected individuals in such a state and susceptibles cannot be avoided. In medical terminology, "occult infection" refers to an infection that presents no clinical signs or symptoms. In our model, we are interested in the case in which the infected individual, while being asymptomatic, is infective. In dynamic network models, hidden infection affects dynamics on and of the network when we have disease evasion dynamics. Note that the effectiveness of disease intervention measures cannot be guaranteed when they are based on models that do not incorporate hidden infection for diseases with such characteristics.

In the next section, we describe our dynamic network model. In Sec. III, we give a mean-field analysis for this model to determine the location of epidemic transition when the period of infectivity is one time step. In Sec. IV, we extend the model discussed in Sec. II to incorporate hidden infection. In Sec. V, we present the results from a computer simulation of our model, and we conclude in Sec. VI.

In our model, the dynamics occur in discrete time steps. We start with all nodes in susceptible state. We then introduce the disease in the network by randomly choosing a node and infecting it. Our goal is to characterize the dynamics that follow after the disease is introduced in this manner.

We consider the acyclic process S → I → R, where R represents the state in which the node is considered removed from the network. At any given time step, the total number of nodes in various states is fixed, i.e., N S,t + N I,t + N R,t = N , where N is the number of nodes in the network we started with, N S,t is the number of susceptible nodes, N I,t is the number of infective nodes, and N R,t is the total number of removed nodes in the network at time step t. The total number of "active nodes" in the population is given by N S,t + N I,t N .

In the model, there are three dynamical processes that are occurring in the network: disease-evasion dynamics, socialmixing dynamics, and disease spread. At the beginning of each time step, the evasion process and social dynamics occur together, followed by disease transmission from infective nodes to susceptible nodes. The evasion process and the social dynamics constitute the topological dynamics of the network in which nodes delete their old links and form new connections. Because of the suppression of susceptible-infected links due to disease evasion, each existing S-I link in the network is deleted with a constant probability η 1 . Due to social dynamics, we assume that the nodes delete their links randomly, independent of their disease status. To account for this, each existing link in the network is deleted with a constant probability φ. Since in our model both the evasion process and social dynamics happen together, each S-S and I -I link is deleted with probability φ while each S-I link is deleted with probability α = η 1 + (1 − η 1 )φ.

All the nodes with links deleted via the above process search for new partners. This also includes nodes from the previous time steps that have deleted links due to other reasons discussed below. In our model, nodes attempt to maintain the number of connections specified by their desired degree (which never changes). Thus the number of partners that a node seeks is equal to the number of its deleted links. While searching for new partners, we assume that the nodes mix randomly. In the mixing population, a node could appear more than once and the multiplicity of a node in equal to the number of its deleted links. While mixing, a node has an equal chance of meeting any other node, independent of their disease status. However, we differentiate between nodes meeting each other and actually forming a new link. When nodes with the same disease status meet (i.e., a potential S-S or I -I link), they form a new link with probability 1. When nodes with a different disease status meet (i.e., a potential S-I link), due to disease evasion, the link is formed with probability 1 − η 2 , where η 2 is a second evasion parameter. This is the case of imperfect evasion where the susceptible nodes avoid getting infected by deleting their links with the infected neighbors, but while searching for new partners there is again a chance of the formation of new susceptible-infected links. When a pair of susceptible and infected nodes is rejected (with probability η 2 ), the rejected pair move to the next time step to search for partners. To keep the dynamics simple, in our simulations we allow the nodes to form self-loops and multiple edges.

In each time step, the topological dynamics described above is followed by the disease transmission dynamics. Disease spreads from an infected node to a susceptible node along each existing S-I link with transmission probability λ. Once a susceptible node gets infected, while being infective, it remains in infected state for a fixed period of time τ , after which the node moves to the removed class. The nodes in the removed class never change their disease status nor do they take part in topological dynamics. When a node moves to the removed class, the active nodes in the network (nodes with disease status S and I ) delete their links with the removed node. These active nodes then search for new partners in the next time step.

Here we present a mean-field analysis giving the location of epidemic transition for the model described in Sec. II when the period of infectivity is one time step. We are interested in finding the value of transition pointλ such that for λ >λ, a finite fraction of the population gets infected in the limit of infinite system size. In our analysis, we assume that networks are large and sufficiently sparse so that loops can be neglected. Before analyzing our model, we first review the case of infinite random static networks with arbitrary degree distributions in cases in which loops can be neglected [20] . Let P (d) denote the probability that a randomly chosen node in the network has degree d. Let Q(d) denote the probability density function for the degree of a node at the end of a randomly chosen edge. For random networks, the distribution Q(d) is given by

where · · · denotes the expectation over the distribution P (d).

For the discrete-time SIR model on infinite random networks, assuming that we start with one infected node, we are interested in the size of the infected component connected to that node. Let z t be the expected number of infected nodes at time step t. We then have

The critical value λ c above which the epidemic incidence is finite is given by z t+1 /z t = 1. Thus, for the SIR model on static networks,

To analyze the dynamic network model proposed in this paper, we modify the above method. Since we consider that the networks are large and sparse, and that new connections in our model are formed randomly, we assume that during the early stages of the epidemic, the dynamic network has locally a treelike structure. Similar to the case of static networks discussed above, to get an estimate ofλ in the mean-field approximation (i.e., neglecting fluctuations), we assume that at the transition point the expected number of infected nodes at time step t is equal to the expected number of infected nodes at time step t − 1. In the following analysis, we set the period of infectivity of nodes τ to be one time step.

Let M SI,t be the expected number of S-I links in the network at the beginning of time step t. During the topological dynamics, each S-I link is deleted with probability α. In the mean-field approximation, the expected number of S-I links that get deleted is αM SI,t . Now, let I t−1 denote the expected number of nodes that got infected in time step t − 1. When the infected nodes from time step t − 2 move to the removed class in time step t − 1, the newly infected nodes from time step t − 1 that were linked to infected nodes from time step t − 2 search for partners in time step t. Thus, the expected total number of infected nodes that will search for partners in time step t is

We do not have a contribution from φM I I,t in the above equation because the period of infectivity τ is one time step and we assumed that the network has locally a treelike structure. Before the topological dynamics in time step t, infected nodes from time step t − 2 move to removed class and we do not have I -I links. Similarly, the expected number of susceptible nodes that will search for partners is

where M SS,t is the expected number of S-S links in the network at the beginning of time step t. In the third term, X t−1 is the number of susceptible-infected pairs that form while nodes search for partners in time step t − 1. Out of these, a fraction η 2 of them get rejected. The susceptible nodes from those rejected pairs search for partners in time step t. Finally, the term Y t−1 accounts for the fact that when infected nodes from time step t − 2 move to the removed class in time step t − 1, the susceptible nodes previously connected to them look for partners in time step t. Here, the time dependence of variables K I and K S is implied. As discussed in the preceding section, the multiplicity of a node in K I or K S is equal to the expected number of its deleted links.

When forming new connections, we assume that the nodes mix randomly. To keep the dynamics simple, the nodes that disconnect their links with each other in a particular time step are allowed again to create links with each other in the same time step. We also allow for self-loops and multiple edges. Under these assumptions, when we haveK I andK S nodes seeking partners [whereK I andK S denote the actual (integer) number, and not the expected number, of nodes seeking partners in a particular realization of the system], the probability ofX susceptible-infected pairs forming, wheñ K I +K S is even, is given by (see the Appendix A)

One can show that over the above distribution, the expected value ofX isK IKS /(K I +K S − 1). Similarly, whenK I +K S is odd, one can show that the expected value ofX is K IKS /(K I +K S ). We assume that the number of nodes seeking partners is large, and we approximate the expected number of susceptible-infected pairs, X t , as

Of the X t pairs of nodes, (1 − η 2 )X t is the expected number of pairs that actually form links. Thus, the expected number of new S-I links that get created at time step t is

We plug in K I and K S from Eqs. (4) and (5) in the above equation and make further simplifications. Since we assume that the networks are large, this means that M SS,t is large. We also assume that the expected number of infected nodes is small at the transition point. Thus, for φ greater than a certain value, at the transition point, K I and αM SI,t + η 2 X t−1 + Y t−1 will be much smaller than φM SS,t . Neglecting terms of higher order, from Eqs. 

After the topological dynamics, the total number of S-I links in the network at time step t includes the S-I links that did not get deleted during the link deletion step, and the newly created S-I links in the equation above. Thus, the total number of S-I links after the topological dynamics at time step t is

For each of these susceptible-infected links, the probability of disease transfer is λ. Thus, the expected number of new infections is

Assuming a treelike structure of the network, the value 

Here we extend the model described in Sec. II to allow for hidden infection. In this case, the flow of nodes from one state to another can be depicted as shown in Fig. 1 . When a susceptible node gets infected, prior to moving to state I , it moves to state I H . In state I H , the infected node does not show symptoms of the infection and thus is not known to have the disease. Although nodes in this state are asymptomatic, they are infective and can infect the susceptible nodes to which they are connected. Thus, the risk of infection spreading in the population increases because the susceptibles cannot avoid nodes with hidden infection.

In the dynamic network model with hidden infection, after spending a fixed amount of time τ 1 in state I H , the infected nodes move to state I , where they show symptoms of the disease and are also infective. For this model, the amount of time the nodes spend in state I is represented by τ 2 . The total period of infectivity τ is thus equal to τ 1 + τ 2 . In our model, we assume that the nodes in states I and I H infect their susceptible neighbors with the same probability λ.

For the purpose of topological dynamics, we treat nodes in states S and I H equally. Thus, during the link deletion process, S-S, I H -I H , S-I H , and I -I links are deleted with probability φ, while S-I and I H -I links are deleted with probability α. While forming new links, nodes mix randomly and form pairs. Similar to the discussion in Sec. II, when a pair is S-S, I H -I H , S-I H , or I -I , a new link is formed with probability 1. When a pair is either S-I or I H -I , a new link is formed with probability 1 − η 2 .

We simulated the models described in Secs. II and IV on Erdös-Rényi and scale-free networks with N = 10 5 and d = 5. The scale-free network, with degree distribution P (d) ∼ d −γ , has γ = 3.5 and maximum degree 300 (given by the natural cutoff [21] ). At the beginning of simulations, we introduce the disease in the network by randomly choosing a node and infecting it, and we study the evolution of the system's dynamics. In the results given below, we are primarily concerned with the location of the epidemic transition with varying system parameters. The size of the epidemic is measured by the final number of R nodes in the network after the disease has died out. for infinite random networks. The epidemic transition in simulations is obtained using the variability measure given in Ref. [22] . Figures 2 and  3 also demonstrate the range of applicability of our mean-field prediction. The figures show that the predictions agree very well with simulations as long as the value of φ is such that φM SS is large.

When φ is not too small, Figs. 2 and 3 show that as φ is increased, the value of the transmission probability at which epidemics first occur also increases. Alternatively, for a given value of transmission probability λ, as φ increases, fewer individuals in the population get infected. This result is contrary to the general belief that with increased social mixing, a disease has a better chance of spreading. In our model, we get this counterintuitive result because of the presence of the second evasion parameter η 2 and the period of infectivity being small (τ = 1). As φ increases, a larger number of S-I links get deleted due to social dynamics. But as the infected nodes previously connected by these deleted links seek new partners, they get rejected with probability η 2 , leading to a reduction in the number of S-I links in the network through which the disease can spread. These rejected infected nodes move to removed class before the next time step.

However, the behavior discussed above for τ = 1 with varying φ is not general. When the period of infectivity is increased, in certain parameter rangesλ can decrease with increasing φ. This is the widely acknowledged behavior that with increasing social mixing, the disease has a better chance of spreading. For τ > 1, with increasing φ more I -I links get deleted and the infected nodes connected by these I -I links can form new connections with susceptible nodes and can increase the spread of disease in the network. Figure 4 shows the results forλ versus φ for τ = 2 for an Erdös-Rényi network. This figure shows that, in certain cases,λ decreases as φ increases, while in other cases,λ increases with increasing φ. For τ = 2, one can derive the predictions for the dynamic network model in a way similar to that discussed for τ = 1 in Sec. III. However, for τ = 2 the equations become complicated and require a numerical solution.

Having explored the role of the social dynamics parameter, we now study the effect of varying evasion parameters (η 1 and η 2 ) with fixed φ (Fig. 5) . The green (light) curve shows the prediction, while symbols show the results from simulations, with varying η 1 for a fixed value of η 2 (= 0.4). As expected, as η 1 increases, the transition point also increases as the disease spread is inhibited. The red (dark) curve shows the prediction, while symbols show the results from simulations, with increasing η 2 for a fixed value of η 1 (= 0.4). As can be seen, increasing η 2 causes an increase inλ. In Fig. 6 , we show the distribution P (ρ) of the size of the epidemic ρ from simulations with changing φ, η 1 , and η 2 for an Erdös-Rényi network when τ = 1. In all three figures, the value of the transmission probability λ is chosen to be above the transition point. As can be seen in Fig. 6 , the distribution of the size of the epidemic is bimodal. In Fig. 6(a) , the fraction of points in the right part of the bimodal distributions are 0.40, 0.26, and 0.12 for φ = 0.1, 0.6, and 1.0, respectively. In Fig. 6(b) , the fraction of points in the right part of the bimodal distributions are 0.54, 0.32, and 0.12 for η 1 = 0.0, 0.6, and 1.0, respectively. In Fig. 6(c) , the fraction of points in the right part of the bimodal distributions are 0.74, 0.48, and 0.10 for η 2 = 0.0, 0.6, and 1.0, respectively. In agreement with the results in Figs. 2 and 5, the results in Fig. 6 show that as φ, η 1 and η 2 are increased, the disease spread is inhibited.

Here we present the results for the case of a disease with hidden infection on an Erdös-Rényi network. For period τ 1 after contracting the disease, infected nodes in this case do not show any sign of infection and thus cannot be detected. Thus, for a given value of transmission probability, we expect the disease to infect a higher number of nodes compared to the case when we do not have hidden infection. Figure 7 shows the results from simulations for different hidden periods of infectivity τ 1 but fixed total period of infectivity τ , which was set to five time steps. We fixed the other parameters of the dynamic network model as φ = 0.1, η 1 = 0.4, and η 2 = 0.4. As expected, with increasing τ 1 , the transition point shifts toward lower values of λ. For the chosen parameters, when τ 1 = 0, the transition point is larger than that for the static network, but for τ 1 = 5 the transition point for the dynamic network is smaller than that for the static network. 

The aim of the paper is to propose a dynamic network model that has some of the important features of the dynamics of real human networks. Incorporating the effects of changing network topology due to disease-independent mixing (social mixing dynamics) as well as disease evasion makes the model more meaningful. In our dynamic network model with both social dynamics and disease evasion (Sec. II), we find that, in certain cases, the value of the transmission probability at which the epidemic first occurs increases with increased mixing (Figs. 2, 3, and 4) . In other words, as social mixing increases, disease spread is inhibited [ Fig. 6(a) ]. This occurs due to the suppression of susceptible-infected links when new connections are formed. When the period of infectivity is greater than 1, in certain parameter ranges we get the behavior that increased social mixing can lead to an increase in the spread of diseases. This can be seen for τ = 2 in Fig. 4 for curves with η 2 = 0.0 and 0.2.

We also studied the dynamic network model by incorporating a class of infected individuals I H who are infective but show no signs of infection (Sec. IV). In static networks, class I H has no effect on epidemic spreading. In the dynamic network model with disease evasion dynamics, the addition of class I H can have a significant effect on disease dynamics. As shown in the results (Fig. 7) , it may be necessary to include this new class of infectives when studying a disease with such characteristics.

The model proposed in this paper can be modified further as needed. For example, in the model in Sec. IV, one can consider different values of transmission probability for infective individuals in class I and individuals in class I H . Other possibilities can also be considered depending on the problem of interest.

The author is thankful to Prof. Michelle Girvan (University of Maryland, College Park) for useful discussions and suggestions.

WhenK S susceptible nodes andK I infected nodes mix randomly, the number of ways in whichX S-I pairs can form is K S (K S − 1) · · · (K S + 1 −X)K I (K I − 1) · · · (K I + 1 −X) X! ,

whereX! accounts for the fact that the pairs are unordered. Of the remainingK I −X nodes, the number of ways of selecting consecutive I -I pairs isK I −X C 2 ,K I −X−2 C 2 , and so on. Thus, the number of ways in which I -I pairs can form is

where we divided byK I −X 2 ! because the order of the pairs does not matter. Similarly, the number of ways in which S-S pairs can form is

The total possible number of ways in which the pairs can form is (K S +K I )! 2 (K S +K I )/2KS +K I 2 ! .

(A4)

Multiplying Eqs. (A1), (A2), and (A3), we get the possible number of cases in which we haveX pairs. Dividing this by Eq. (A4), we get the probability that we haveX pairs in a randomly mixing population.

Gonorrhea Transmission Dynamics and Control

Infectious Diseases of Humans: Dynamics and Control

Proc. Natl. Acad. Sci. USA