key: cord-0856685-dm1dwlui
authors: Croccolo, Fabrizio; Eduardo Roman, H.
title: Spreading of infections on random graphs: A percolation-type model for COVID-19
date: 2020-07-03
journal: Chaos Solitons Fractals
DOI: 10.1016/j.chaos.2020.110077
sha: 9a3586e520e44b271573c59c9d79f9eee62afa87
doc_id: 856685
cord_uid: dm1dwlui

We introduce an epidemic spreading model on a network using concepts from percolation theory. The model is motivated by discussing the standard SIR model, with extensions to describe effects of lockdowns within a population. The underlying ideas and behaviour of the lattice model, implemented using the same lockdown scheme as for the SIR scheme, are discussed in detail and illustrated with extensive simulations. A comparison between both models is presented for the case of COVID-19 data from the USA. Both fits to the empirical data are very good, but some differences emerge between the two approaches which indicate the usefulness of having an alternative approach to the widespread SIR model.

The study of epidemics spreading in human populations has a long history both on the mathematical aspects (see e.g. Kermack and McKendrick (1927) ; Bailey (1957) ; Bollobás (2013) ), as well as on the modelling of outbreak and control of their evolution (Anderson and May (1991) ; Fraser et al. (2004) ; Fernández-Villaverde and Jones (2020); Chen et al. (2020) ; Yang et al. (2020) ). Spreading phenomena has been studied extensively also in the realm of statistical physics of disordered systems (e.g. Ben-Avraham and Havlin (2000) ; Bunde and Havlin (2012) ; Stauffer and Aharony (2018) ).

In this paper, we introduce a lattice network model for epidemics spreading based in part on concepts taken from percolation theory. To motivate the network approach to spreading, we first discuss the SIR model (Kermack and McKendrick (1927) ), also extending it to encompass the effects of lockdowns mimicked by using a time decaying reproduction number. To assess the usefulness of the lattice model, we consider COVID-19 data from the USA and compare the results of the simulations with SIR predictions, both in the presence of lockdowns.

The paper is organized as follows: We start out in Sect. 2 with a brief review of the SIR model, with emphasis on some analytical results and its extension to the description of lockdown effects. Illustrative examples are shown, together with a motivation for the need of going beyond a 'meanfield' approach. The network model is then discussed in detail in Sect. 3, and the percolation ideas, relevant to the present case, are discussed. Extensive (Monte Carlo) simulations are shown to illustrate the advantages and difficulties typically associated with such lattice models. In Sect. 4, we apply it to the current case of COVID-19 USA data, by comparing the network results with the predictions of the SIR model. The paper ends with our concluding remarks in Sect. 5.

Infection spreading is typically modelled by the SIR model, introduced by Kermack and McKendrick (1927) . We briefly review it for the purpose of introducing the notation and presenting extensions to describe lockdown effects. We follow standard terminology in epidemic literature 2 .

We consider a population with a fixed number of individuals, N . To describe the outbreak of an infectious disease, the population can be divided into the following four categories: Susceptible (S), Infected (I), Recovered (R) and Dormant (D). The number of individuals in each of the first three categories depends on time t, so that we will indicate them as S(t), I(t) and R(t), while the number of Dormant D remains constant during the whole process. Susceptible are initially healthy but can become infected; infected people carry the infection and can transmit it to susceptible ones, while recovered people are infected who have healed or have died, thus they do not spread the infection any further. The fourth category, D, includes non-susceptible (perhaps immune individuals to the specific disease), and in general healthy subjects who do not get in contact with infected ones during the whole spreading process (Fig. 1) . The reason for introducing the fourth category will become clearer when discussing solutions of the SIR system of equations.

At any time t, the number of individuals in each category must obey the conservation equation,

where we have denoted N 0 = D. We assume the unit of time to be one day. The SIR model is described by a set of three differential equations for the time variation of the number of individuals in each category, S(t), I(t) and R(t), which, upon taking into account the condition Eq. (1), read,

where N eff = N −N 0 = S(t)+I(t)+R(t), is the effective number of individuals taking part in the process, β is the infection (or contact) rate between infected and susceptible subjects,β = βN eff /N is the effective infection rate in the presence of dormant, and γ is the healing (or immunization) rate of infected. It is convenient to work with normalized quantities, s(t) = S(t)/N eff , i(t) = I(t)/N eff , and r(t) = R(t)/N eff , so that the SIR equations become, dr dt = γ i(t).

The above equations have exactly the same form as in the case N 0 = 0. The idea of considering explicitly a fraction of the whole population not taking part in the spreading phenomenon, f 0 = N 0 /N (0 ≤ f 0 ≤ 1), allows us to interpret the so-called reproduction number, R 0 , as composed of two factors, a purely 'biological' one, ∼ β/γ, and a 'structural' one ∼ (1 − f 0 ), denoted as,R 0 = (β/γ)(1 − f 0 ). The second factor represents the effect of dormant non-in-contact with others, thus 'hindering' or slowing down the spreading process. The fraction f 0 can change in time, but for simplicity we assume it constant. Within the realm of the SIR model dormant people do not seem necessary, however, they play a prominent role within the context of network models of infection spreading, as we will discuss in detail in Sect. 3. More generally, dormant subjects can be considered as those individuals who interact very weakly with others, thus representing a subset of the population being in a sort of 'quarantine' from others. One can derive some general relations between the categories by conside-ring ratios between the SIR differential equations (Eqs. (5,6,7)). First, divide (6) by (5), yielding,

and dividing (5) by (7), we find,

By specifying the conditions,

which can be written as,

Notable limits are, s(∞) = s(0) whenR 0 → 0, and s(∞) = 0 whenR 0 → ∞. Also Eq. (6) admits a partial solution when di/dt = 0, in particular at t = t peak , i.e. at the peak of the infected curve, yielding,

Lockdown effects can be modelled using an exponential time dependence of β (see e.g. Palladino et al. (2020) ). Here, we employ a softer decay that appears to work very well, i.e.

andβ(t) =β, for t ≤ τ 0 , where τ 0 is the time at which lockdown starts, and q > 0 is a parameter. This means we deal with a time decaying reproduction number,R 0 (t) =β(t)/γ. Using this form in Eq. (6), we can obtain the time t lock at which the infected curve displays its new maximum. The condition is,R 0 (t lock )s(t lock ) = 1, which, together with Eq. (12), yields,

since s(t lock ) > s(t peak ), as there are more susceptible subjects in the presence of lockdowns than otherwise. Illustrative examples are reported in Fig. (2) , forR 0 = 16.5 (with β = 1.1 and γ = 1/30) and f 0 = 1/2. In the upper panel, we show the standard case, with γ representing the inverse of a typical COVID-19 healing period. We show also for comparison the case f 0 = 0 (dashed lines). In this case, Eq. (11) predicts s(∞) ∼ = 0, clearly consistent with the numerical data. As is apparent from the upper panel of Fig. (2) , the effect of f 0 > 0 is to shift the infected peak at longer times by keeping a still high reproduction number. The effects of lockdowns, using relation Eq. (13), are displayed in the lower panel of the figure, for the typical cases τ 0 = 18 days and q = 2. Notice that Eq. (14) predicts t lock ∼ = 18 0.66/0.06 ∼ = 60 days, in agreement with the numerical results, and the infected peak is reduced by a factor of about 4.

Let us return to Eq. (11). In the language of random graph theory (Erdős and Rényi (1960) ; Erdős (1973) ; Bollobás (2013)), Eq. (11) is formally equivalent to the self-consistent relation for the fraction of nodes, P ∞ ≡ 1 − s(∞), belonging to the giant component of random graphs with a finite mean node degree k , given by,

where 0 < p < 1 is the probability of occupancy of a link between two nodes. It can be shown that a giant cluster exists when k p = c > 1. This model is also related to the mean-field theory of random spin glasses with finite coordination number (see e.g. Kanter and Sompolinsky (1987) ). Clearly,

The correspondence with Eq. (11) is achieved if we takeR 0 ≡ c and assume s(0) = 1, which is the case since s(0) ≈ 1 in our spreading model. Using 1 − s(∞) = r(∞), we find,

This correspondence is actually not surprising since the SIR equations are valid in a mean-field sense, where fluctuations and correlations among the categories are neglected. This analogy suggests us that we should go beyond mean-field theory by studying infectious spreading on a network where correlations can be implemented. This is done in the following Section.

Tracing infected people in a population and how they move is essential to make an accurate assessment of the extent a virus has spread in a region, country or the whole world, in order to implement effective lockdowns in each particular place (see e.g. Chinazzi et al. (2020) ). Here we discuss a simple network model defined on a two dimensional square lattice. The sites of the lattice represent individuals belonging to one of the four categories (S, I, R, D), which we will distinguish with different colours in the plots, i.e. green, red, blue, and yellow, respectively.

Two individuals are said to be connected, i.e. transmission of the disease can occur, if they are nearest-neighbours (NN) on the lattice, representing a 'short-range' contact interaction. The NN choice is done just for convenience, and it can be relaxed in other versions of the model. The bonds between sites represent therefore the links in the graph, and the coordination number of 4 gives the maximum node degree, under 'static' conditions. The latter mean that the individuals are considered to be at rest in their lattice locations, initially, while the virus can move around from site to site if the following rules are obeyed: (1) The virus can cross a bond from an infected site to a susceptible one; (2) no virus transmission occurs otherwise; (3) infected sites heal after τ H days, becoming recovered sites, so that they can neither infect others nor being infected again (immune sites); and (4) dormant sites do not participate in the spreading process.

It is essential to consider additional links 'dynamically' as the spreading goes on. This is done in order to describe those individuals who move around for different reasons. Thus, any infected site can reach sites that are not NN to it, and the infection can spread according to the above rules. In this case, the infection is transmitted with a probability β L = t 0 /τ L , with τ L > t 0 , and t 0 = 1 day, provided the target site is a susceptible one.

In summary, we have taken a two dimensional lattice to facilitate the visualization of the network, and considering both NN transmissions as well as long-range ones, though with a lower probability. Since the extra links are not determined from the beginning, but are added dynamically, we do not show them in the plots, facilitating the identification of the categories. Another reason for choosing a square lattice is that the percolation threshold for site percolation (in this case the susceptible sites) is about 0.6, meaning that if we take say, f 0 = 1/2, there are not percolating ('infinite') clusters of susceptible subjects on the lattice. This 'hindering' effect is useful when implementing lockdowns, since the remaining susceptible clusters (of connected NN sites) are disconnected from each other (they are indeed 'finite'). One can say that 'long-range' links can connect different susceptible clusters, which otherwise would remain disconnected. The model parameters are: τ 0 = 20 (start of lockdowns) and τ L = ∞ (no long range transmissions) yielding β L = 0. The average node degree for the starting configuration is k = 2, while additional links are added dynamically until t = τ 0 . The newly created links yield an additional mean degree ∆k = 156/5043 ∼ = 0.03, corresponding to an effective mean node degree k eff = 2.03.

We show in Fig. 3 and 4 results of simulations for a single configuration, without and with lockdowns, respectively, on a (100x100) lattice for times t ≤ 100 days. Fixed boundary conditions are employed. The starting con-figuration has a random distribution of either susceptible or dormant sites, chosen with probability f 0 = 1/2. The initial conditions include a single infected site right at the centre of the lattice, and no recovered subject. We keep track of the existing infected sites, each carrying a clock that starts ticking when the site gets infected. After a time τ H it becomes recovered (immune). Death sites are not implemented, but they can be estimated simply as a fraction of recovered ones. (Fig. 3) . (Lower panel) Lockdowns: t ≥ τ 0 = 20 (Fig. 4) .

We count the number of dynamical links generated during the spreading, from which we can determine, a posteriori, the effective mean node degree, k eff , in our network. We find k eff ∼ = 2.22 without lockdowns (Fig. 3) and k eff ∼ = 2.03 with lockdowns (Fig. 4) , indicating an effective reproduction number R eff = k eff − 1 1. It turns out that the relatively small reduction of the mean node degree in the presence of lockdowns is sufficient to reduce the number of infected subjects considerably, as one can see from the very different structure of recovered clusters from both figures. The time evolution of the three categories are displayed in Fig. 5 , and look qualitatively similar to those from the SIR model in Fig. 2 . We should mention that a single lattice simulation takes few seconds on a typical laptop, even for lattices of size (400x400), allowing to obtain accurate mean values by averaging over several configurations if required.

As an application of the present ideas we consider COVID-19 USA data (see also Wu et al. (2020) ; Dong et al. (2020) ; Xu et al. (2020) ), from the point of view of both SIR and network models. In order to do so, and due to the complexity of the data, we need to introduce additional features in particular for the SIR model.

For the USA data (Fig. 6) , the lockdown regime can be described by the Ansatz, similar to Eq. (13),

whereβ D = (β D /γ)(1−f 0 ), with, in general, a time dependent exponent q(t).

Let us consider first the case of the SIR model (upper panel in Fig. 6 ). For the latter, we use the decreasing function with time, q(t) = q − t/100, with the constant value q = 2.5. This feature was needed in order to reproduce the slowly decreasing behaviour of the daily cases (blue circles in Fig. 6 ). In addition, a rather complicated form for the factor d(t) determining the time evolution of deaths, Deaths= d(t) × R(t), was required. We find that the form d(t) = 0.17 [0.3 + 1/(t/60)] reproduces the curve of deaths quite well (black circles in Fig. 6 ), but the results might be improved using more parameters. This remains to be understood. The whole fitting curves were shifted in time by an amount t Lag = 29 days, that is, the initial data were actually discarded from the fits. In the case of the network model (lower panel in Fig. 6 ), the situation is simpler since all parameters can be taken as constants; the values depending on the regime under consideration. Regarding lockdowns (t ≥ τ 0 ), the value q = 2.5 works rather well, while we take a finite long-range transmission probability β LD = 1/32, i.e. 4 times smaller than its value β L = 1/8 (t < τ 0 ), suggesting that indeed the lockdowns are not fully implemented and few additional infected subjects are still moving around. Also the number of deaths can be estimated from the actual recovered ones using a single value d = 0.06 (6%). As well as in the case of SIR, also here we used times lags for the fits, i.e. t Lag = 45 for the cases and t Lag = 21 for deaths.

We have introduced a network model for the spreading of an infectious disease in a population based on random graph and percolation theory concepts. The model is conveniently defined on a square lattice allowing a simple visualization of the four different categories in the problem: Infected, susceptible, recovered and dormant subjects. The first three groups form the core of the widely used SIR model, while the fourth one is introduced here for representing those individuals who are disconnected to some extent from the rest of the population. They do not participate in the spreading phenomena but their presence acts as an effective slowing down of spreading by blocking an otherwise direct transmission between infected and susceptible people. In the language of percolation theory, the 'connected' susceptible subjects form finite clusters on the lattice that are separated from each other. To allow the spreading to overcome these 'connection gaps' as the process evolves in time, we allow infected people to reach any other susceptible site in the lattice, and infect it with a relatively lower probability than inside a finite cluster via NN contacts. We denote these new links, not present initially in the 'lattice graph', dynamical links. This dynamical approach allows us to describe lockdown effects in terms of the slowing down or total lacking of the dynamical links.

We have assessed the performance of the network model by fitting COVID-19 USA data and compared the results with predictions using the SIR model. The network model works very well by just using constant parameters, while the SIR model requires more involved time dependent parameters to achieved similar fitting accuracy. We conclude that the present network model can become a valuable technique to complement the widely used SIR model.

Infectious diseases of humans: dynamics and control

The mathematical theory of epidemics

Diffusion and reactions in fractals and disordered systems

Modern graph theory

Fractals and disordered systems

2020. A Time-dependent SIR model for COVID-19 with Undetectable Infected Persons

Estimating the risk of sustained community transmission of COVID-19 outside Mainland China

An interactive web-based dashboard to track COVID-19 in real time

The Art of Counting

On the evolution of random graphs

Estimating and Simulating a SIRD Model of COVID-19 for Many Countries, States, and Cities

Factors that make an infectious disease outbreak controllable

Mean-field theory of spin-glasses with finite coordination number

A contribution to the mathematical theory of epidemics

Modelling the spread of Covid19 in Italy using a revised version of the SIR model

The SIR Model for Spread of Disease

Introduction to percolation theory

Estimating clinical severity of COVID-19 from the transmission dynamics in Wuhan, China

Pathological findings of COVID-19 associated with acute respiratory distress syndrome. The Lancet respiratory medicine

Modified seir and ai prediction of the epidemics trend of covid-19 in china under public health interventions

☒ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.☐The authors declare the following financial interests/personal relationships which may be considered as potential competing interests:HE Roman developed the model and performed the simulations. Both authors discussed the results and wrote the paper.