key: cord-103418-deogedac
authors: Ochab, J. K.; G'ora, P. F.
title: Shift of percolation thresholds for epidemic spread between static and dynamic small-world networks
date: 2010-11-12
journal: nan
DOI: 10.1140/epjb/e2011-10975-6
sha: 
doc_id: 103418
cord_uid: deogedac

The aim of the study was to compare the epidemic spread on static and dynamic small-world networks. The network was constructed as a 2-dimensional Watts-Strogatz model (500x500 square lattice with additional shortcuts), and the dynamics involved rewiring shortcuts in every time step of the epidemic spread. The model of the epidemic is SIR with latency time of 3 time steps. The behaviour of the epidemic was checked over the range of shortcut probability per underlying bond 0-0.5. The quantity of interest was percolation threshold for the epidemic spread, for which numerical results were checked against an approximate analytical model. We find a significant lowering of percolation thresholds for the dynamic network in the parameter range given. The result shows that the behaviour of the epidemic on dynamic network is that of a static small world with the number of shortcuts increased by 20.7 +/- 1.4%, while the overall qualitative behaviour stays the same. We derive corrections to the analytical model which account for the effect. For both dynamic and static small-world we observe suppression of the average epidemic size dependence on network size in comparison with finite-size scaling known for regular lattice. We also study the effect of dynamics for several rewiring rates relative to latency time of the disease.

The epidemic modelling has become a significant and needed branch of complex systems research, as we have witnessed the recent epidemic threats and outbreaks of human diseases (H5N1 and H1N1 influenzas [10, 8] or severe acute respiratory syndrome [9, 2] ) or animal (foot-and-mouth disease [6] ) and plant diseases alike (e.g. Dutch elm disease [14] or rhizomania [13] ). There are two crucial characteristics of the epidemic spread that make it complicated to be modelled on the one hand, and costly to be prevented in reality on the other: firstly, a number of infectious diseases exhibit long-range transmissions of varied 2 Model

We adopt Watts-Strogatz model of a small-world network [16] : first we take a 2-dimensional square lattice with N = L 2 nodes and 2N undirected edges.

To avoid some finite-size effects we impose periodic boundary conditions for the lattice (i.e. we get a torus). Then, we add a number of undirected edges between random pairs of nodes. The number of additional edges ('shortcuts') is set as 2φN , hence φ is shortcut probability per underlying bond. Network with φ = 0 is just a regular lattice. For nonzero φ we call the network a static small-world.

The third type of network is a dynamic small-world. One can construct it by randomly distributing shortcuts in every time step of simulation. Here, we choose 2φN nodes randomly, and keep them fixed for the whole run of the epidemic. In every time step we randomly launch shortcuts anchored in these nodes, which means the dynamics consists in rewiring one end of these shortcuts. For the sake of simplicity we allow for multiple shortcuts being incident with the same node, for shortcuts leading to nearest neighbours, and for loops being formed. The construction of the source nodes launching shortcuts allows for an easier interpretation of the network: the fixed nodes could correspond to centres of activity that can be identified as in the real world networks. 

The SIR (Susceptible-Infectious-Removed) model is adopted, where the disease is transmitted along the edges of the network in discrete time steps. The probability p of infecting a susceptible node by an infectious neighbour during one time step is set equal for short-and long-range links, both static and dynamic. The latency time l of the disease is measured in discrete time units (we take l = 3, 4). Thus, an infectious node can transmit disease to susceptible nodes with probability p every turn for the period of l turns, and after that time it is removed, i.e. it cannot infect nor be reinfected. Every simulation starts with only one initially infecting node, all others being susceptible, and it ends when no node in the infectious state is left. Sample snapshots of the epidemic time development are presented in Fig.2 . Grassberger [4] related the probability of infection to the probability T in bond percolation through T = l t=1 p(1 − p) t−1 = 1 − (1 − p) l , where T is the so called transmissibility (it is the total probability of a node infecting one of its neighbours during the whole latency time). In the case of 2-dimensional square lattice the bond percolation threshold is T c = 0.5.

Numerical data

The linear lattice size used for most calculations is L = √ N = 500. In Section 5.2 we take sizes L = 50, 63, 79, 100, 126, 158, 199, 251, 315, 397, 500. The disease latency is set to l = 3 (for faster simulations reported in Sec. 5) or l = 4 (in Sec. 5.3 in order to get larger set of dynamic rates). The range of probability p scanned is p = 0.05 − 0.22 (depending on φ) with resolution of 1/1024, which translates to around T = 0.15 − 0.5. For every p and φ the epidemic is run 1024 times with random distributions of shortcuts each time. The fraction of shortcuts is φ = 0 − 0.5, with steps of 0.025. The simulations are performed for both static and dynamic small-world network. 

In the study of the epidemic spread on networks, we stick to the percolation theory as a reference point. In the theory, a percolation threshold would be the value of p that generates an epidemic cluster spanning between the boundaries of the whole system. Otherwise, it is possible to define percolation as the point at which a cluster of macroscopic size forms (i.e. it occupies a finite fraction of the system for N → ∞). We employ the latter to define percolation threshold (numerically) as the point at which the average epidemic's size divided by N rises above a certain value (here, set to 0.00115). The average is taken over a number of reruns for different shortcut drawings. As we can perform simulations only for finite sizes, we take the results for a relatively large network of √ N = 500. The choice of the threshold value is taken so as to calibrate the results for the static network to the previously confirmed analytical result. We take as the theoretical model [7] , where the generating function and series expansion methods were used to find the approximate position of bond percolation transition in 2D small-world network, which corresponds to the epidemic spread on what we refer to as static small-world.

We can account for the change between static and dynamic networks analytically using the model known for static small-world network [7] . As the original theory has no time variable, it would be a hard task to introduce dynamics explicitly.

The solution, however, is astonishingly simple. One can estimate the average number of nodes infected through shortcuts during latency time l:

i.e. the number of shortcuts in the static network multiplied by the total probability of infecting a neighbouring node (this probability is the same for both regular links and shortcuts). The analogous expression for the dynamic network is found easily

where the sum is an average number of infections transmitted by a single source of dynamic shortcuts for a given latency time. It comes from the fact that a dynamic shortcut can pass infection several times (the factor p i ), while in the static case a node could infect only once (since nodes cannot be reinfected in the SIR model). This expression predicts lowering percolation thresholds, although numerical values of the shift are considerably smaller than the ones obtained from simulations. Figures 3(a) -3(c) explain why the above expression is not yet correct: it is derived only for the source nodes passing the disease on, while it disregards the fact that the node may itself become infected via long-range link. Since on the static network there is no difference between shortcuts' source and target nodes, we can attach the factor φN/2 to both infection graphs presented in Fig.3(a) . For dynamic network, the graphs in Fig.3 (b)-3(c) for infecting a source node through a regular link and through a dynamic link give different counts of how many shortcuts were used. The former was given in Eq.2 as lp, and the latter actually utilises the same formula, but with the substitution l → l + 1. In total, we get

We assume that N dyn = N stat if the epidemic on both networks has the same percolation threshold. Thus, we can obtain the ratio of the two shortcut densities

where p is the probability of infection in one time step and l latency time of a disease. Now, we can calculate T c (rφ)) numerically, just as we do it with the fitted Fig.4 . The ratio in Eq.4 was used to plot the lower solid line in Fig.4 .

In Figure 4 we plot numerical and theoretical values of percolation thresholds T c for both static and dynamic small-worlds. The resulting T c (φ) data points for static small-world network agree with the analytical approximation [7] , which confirms the validity of calibration procedure. As the lower dataset marks the effect of network dynamics, the difference between the two networks proves to be systematic and significant. The dashed line is a fit T c [(1 + v)φ] of the analytical model for the static network, where the fitted parameter v may be interpreted as a virtual percentage of additional shortcuts needed to obtain the dynamic network percolation thresholds. It follows from the fit that percolation thresholds for dynamic network are lower as if the shortcut density were (1+v)φ (where v = 0.207 ± 0.014 is the fitted parameter). Nonetheless, qualitatively the epidemic on dynamic small world behaves in the same way as on the static one for the given range of parameters (φ = 0.5 corresponds to every node in the network having on average two additional links). The analytical correction slightly exceeds the values of simulation data points, but the overall agreement is satisfactory. The difference between the analytical solution and the observed behaviour does not exceed the shift between static and dynamic networks obtained from simulations. The discrepancy might be due to the method of calculating percolation thresholds from numerical data or due to the approximate nature of the correction.

The primary motivation of checking finite-size scaling for the system was to utilise it to determine the percolation thresholds very accurately (as the shift of thresholds observed in Fig.4 is relatively small), and to arrive at threshold value for infinite system size. Yet, it is worth noting at this point that the knowledge of thresholds for infinite system sizes would not usually be appropriate for evaluation of risks in the real epidemic, given the sizes of some real networks. To study the size of finite-size effects is thus vital on its own right. In Figure 5 (b) the convergence of the average epidemic size to the threshold behaviour can be observed, and the significant dependence on system size ranges up to the epidemic size of around 0.5N and interval of transmissibility of length around 0.08 (the numbers are very rough estimates). As presented in Fig.5(a) 

where T N are the values of transmissibility for a given system size N and a set section position, and T ∞ is the percolation threshold for infinite system size. For regular lattice T ∞ is fitted correctly for various section positions as 0.500±0.005 (the error may vary for different sections, but does not exceed the given value).

It appears that the dependence on system size for small-world networks (both static and dynamic) is dissimilar to the one of regular lattices, as can be seen in Fig.5.2 (φ = 0.05) . It is suppressed to smaller values of the average epidemic size. For the shortcuts density φ = 0.5 the dependence on system size is already visible only below the epidemic size of 0.03. Because the dependence of the epidemic size on size of the system becomes of the order of magnitude of statistical fluctuations (the quality of the data can already be seen in the Fig.5. 2), any attempts to utilise finite-size scaling for determining percolation threshold are not viable. Indeed, the errors do not allow us to check if the same form of finite-size dependence as in Eq.5 holds.

Dependence on the rate of dynamics

One can generalise the theoretical analysis for various rates of dynamics, given the formula in Eq.2. To explain this, let us notice that there are two time scales in the model: the latency time l of the infection and the duration 1/d between consecutive rewirings of dynamic links (both measured in discrete time steps of the epidemic spread). As the choice of latency l only rescales the total probability of infection T = T (p, l), we can dispose of it, and the crucial parameter ld that accounts for the shift of percolation thresholds is defined as the number of shortcut movements during latency time.

Obviously, for a static network we get d = 0, while for all the above analysis of dynamic network we have ld = 3 (l = 3 and the rewiring was performed every turn, so d = 1). Depending on the interpretation of the model, we could also consider d > 1. However, if p is to be the probability of infection during one time step it is reasonable that shortcuts rewiring faster than one time step would infect with appropriately smaller probability, and there would be no further shift of percolation thresholds.

Since the epidemic spreads with discrete time, which results in sums as in Eq.2, we are interested in rational numbers d ∈ [0, 1]∩Q, particularly of the form 1/i, i ∈ Z. What we need is N dyn calculated in a similar way to that in Eq.2. Here, we take l = 4, d = 1, 1/2, . . . , 1/7, and we plot both the numerical and theoretical results for φ = 0.25 in Fig.7 . Theoretical derivation is to be found in the Appendix. The theoretical approach gives slightly exceeding values (the scale should be noted), which is the same effect as discussed at the end of Section 5.1.

We have shown that introducing dynamics of the long-range links in a smallworld network significantly lowers an epidemic threshold in terms of probability of disease transmission, although the overall dependence on number of shortcuts stays the same. Consequently, the risk of an epidemic outbreak is higher than in any calculations involving static models. The effect remains secondary to the influence that the introduction of additional of shortcuts has on the spread of the disease. It should be noted that the shift of percolation thresholds depends on the relative measure of dynamics of the network with respect to the process on the network (rewiring rate and latency time, respectively). Any accurate analytical calculation or simulation should take this quantity as a significant parameter, to be estimated for a particular disease and type of the network.

As in reality we consider only finite-size networks, and real epidemic sizes do not usually reach values of the order of even 10% of the system size, the information on finite-size effects seemed very much needed. That the epidemic outbreak magnitude does not depend on the system size for small-world networks as much as it does for regular lattices means that we should not expect the epidemic outbreaks below transmissibility threshold value. Thus, finite-size effects seem to become secondary, as well.

The usefulness of such a model for risk prediction still depends on our knowledge of the probability of transmission (p or T ) of a given disease, which is not easy to obtain for diseases spreading outside of well controlled environments like hospitals. Relatively good estimates, thanks to the nature of transmission, exist for syphilis. Transmissibility of the disease is reviewed in [3] , where authors give values ranging from 9.2% to 63% per partner, and decide on 60% as the lower boundary for untreated disease. This seems to be well above the epidemic threshold, irrespective of very different network topology for such diseases. However, this also shows that errors on estimates of transmission probabilities exceed the effect of threshold shifting studied here.

Though the 2-dimensional network structure used here may be said to correspond mainly to that of plantations, it is worth noting its generality: nodes may be interpreted as plants, animals or humans, but also on a larger scale as farms, households, or cities and airports; in turn, long-range links could mean wind (on farms), disease vectors, occasional human contacts, or airline connections. Still, it has some other fairly realistic characteristics: according to [11] , who analysed the structure of human social interactions, 'the majority of encounters (76.70%; 75.26-78.07) occur with individuals never again encountered by the participant during the 14 days of the survey.' This may mean that about 24% of the repeated contacts corresponds roughly to our regular underlying lattice with z = 4 neighbours for each node, while the 76% correspond to around 3z dynamic contacts distributed over over 14 days. This gives on average φ ≈ 0.20 for simulation with daily time steps, which lies within the parameter range studied in this paper.

A 0 (p, 5) = · · · · · A 1 (p, 5) = ·| · · · · + · · · · |· = 2 · | · · · · A 2 (p, 5) = · · | · · · + · · · | · · = 2 · ·| · · · (7)

A 11 (p, 5) = ·| · · · | · A 12 (p, 5) = ·| · ·| · · + · · | · ·|· = 2 · | · ·| · · where the symbol '|' marks rewiring, and '·' one epidemic time step during latency period. For instance ·| · · would correspond to three turns with one rewiring, during which either 0, 1 or 2 infections are possible. The derivation involves only very easy combinatorics, but for longer latency periods one would need to repeat these calculations to obtain more terms and different prefactors. Now, one can easily obtain expressions for N dyn for any 1/d ∈ Z. Below we give only the general expression for 1/d ≥ l: where l = 4. The first term in the brackets corresponds to Fig.3 (b) and the second to Fig.3(c) . For greater numbers of rewiring per turn d, we need to consider the terms A 11 , A 12 . The result is plotted against simulated data in Fig.7 .

Modelling control of epidemics spreading by long-range interactions

Modeling the sars epidemic

The natural history of syphilis: implications for the transmission dynamics and control of infection

On the critical behavior of the general epidemic process and dynamical percolation

Epidemic dynamics on an adaptive network

Dynamics of the 2001 UK Foot and Mouth Epidemic: Stochastic Dispersal in a Heterogeneous Landscape

Percolation and epidemics in a two-dimensional small world

World Health Organization. Avian influenza (h5n1)

World Health Organization. Severe acute respiratory syndrome (sars)

World Health Organization. Swine influenza (h1n1)

Dynamic social networks and the implications for the spread of infectious disease

Modelling development of epidemicswith dynamic small-world networks

A model for the invasion and spread of rhizomania in the united kingdom: implications for disease control strategies

Dutch elm disease and the future of the elm in the uk: a quantitative analysis

Susceptible-infected-recovered epidemics in dynamic contact networks

Collective dynamics of 'small-world' networks

This work is supported by the International PhD Projects Programme of the Foundation for Polish Science within the European Regional Development Fund of the European Union, agreement no. MPD/2009/6.

Below we present the way to calculate N dyn for latency periods l = 4, 5 (in the simulation we set l = 4, but we need to take into account also the process from Fig.3(c) , which in a sense increases latency by 1). Let us definewhere we substituted T (1) for p on the right-hand sides, and we leave out the argument p in T (p, l) to simplify the notation. Those quantities correspond to the average number of infections during one latency period depending on when the rewiring takes place. One can present those diagrammatically (here for l = 5) as