Modelling Development of Epidemics with Dynamic Small-World Networks, Hacking and IT E-Book Dump Release
[ Pobierz całość w formacie PDF ]
Modelling Development of Epidemics with
Dynamic Small-World Networks
Jari Saramaki
∗
, and Kimmo Kaski
Laboratory of Computational Engineering, Helsinki University of Technology, P.O.
Box 9203, FIN-02015 HUT, Finland
Abstract
We discuss the dynamics of a minimal model for spreading of infectious diseases,
such as various types of influenza. The spreading takes place on a dynamic small-
world network and can be viewed as comprising short- and long-range spreading
processes. We derive approximate equations for the epidemic threshold as well as
the spreading dynamics, and show that there is a good agreement with numerical
discrete time-step simulations. We then analyze the dependence of the epidemic
saturation time on the initial conditions, and outline a possible method of utilizing
the model in predicting the development of epidemics based on early figures of
infected. Finally, we compare time series calculated with our model to real-world
data.
Key words:
epidemiology, spreading models, complex networks, infectious diseases
1
Introduction
Traditionally, mathematical models for the spread of a disease have relied on
differential equations, describing the dynamics of spreading within uniformly
mixed populations (Bailey, 1975; Anderson and May, 1991; Murray, 2001). The
basic premise of uniform mixing is that all individuals in a group are equally
likely to become infected. The spreading process itself is then captured using
compartments, i.e. individuals belonging to epidemiological classes such as sus-
ceptible (S), exposed (E), infective (I) and recovered (R), between which the
flows of population are described with rate equations. Within this framework,
∗
Corresponding author.
Email address:
jsaramak@lce.hut.fi
(Jari Saramaki).
Preprint submitted to Elsevier Science
11 November 2004
the simplest model is the widely-utilized SIR (Susceptible-Infected-Removed)
model (see e.g. Anderson and May, 1991; Hethcote, 2000), in which suscepti-
ble individuals may become infected and continue to infect others until finally
removed from the system due to recovery, death, or containment.
The apparent shortcomings of the uniform mixing hypothesis have long been
realized, and spatial effecs and heterogeneity have been show to have profound
effects on the transmission, persistence and evolution of diseases (Mollison,
1977; Rand et al., 1995; Lloyd and May, 1996; Rhodes and Anderson, 1996;
Keeling, 1999; Grenfell et al., 2001). Partially owing to the recent advances
in the science of complex networks (Albert and Barabasi, 2002; Dorogovtsev
and Mendes, 2002; Newman, 2003), there has been increased interest in try-
ing to capture the effects of contact patterns between individuals instead of
relying on mean-field models. These patterns can be described using
contact
networks
, where the vertices correspond to individuals and the edges to con-
tacts between them (Wallinga et al., 1999). One of the major motivations for
studying complex networks has been to better understand the structure of
so-
cial networks
(Watts and Strogatz, 1998; Girvan and Newman, 2002). As the
structure of social networks, without a doubt, has to be reflected in contact
networks, there is a natural link between epidemiological modeling and the
science of complex networks.
The network approach to epidemiological modeling has proven to be fruitful in
the context of the spreading dynamics of human disease as well as electronic
viruses (Watts and Strogatz, 1998; Keeling, 1999; Boots and Sasaki, 1999;
Newman, 2002; Pastor-Satorras and Vespignani, 2001; May and Lloyd, 2001;
Read and Keeling, 2003; Meyers et al., 2003, 2005), yielding much insight on
the mechanisms of disease spreading. Overall, the types of network structures
used in these models can be divided into two categories: the so-called
small-
world
and
scale-free
networks. A well-known result of these studies is that bi-
ological and computer viruses spread rapidly on both types of networks, which
is mainly due to the very short average vertex-to-vertex distances along the
links of the networks. In addition, spreading is further accelerated in scale-free
networks due to a broad power-law distribution of connections per individual
- the few highly connected hubs then act as “super-spreaders.”
Generally, the term ’small-world network’ refers to networks where a small
number of shortcuts is introduced on a regular underlying lattice, either by
adding new links between randomly selected vertices or randomly rewiring
a fraction of the links (Watts and Strogatz, 1998). In terms of population
mixing, a small-world structure is analogous to a situation where there are
clusters of connected individuals (social groups), which have contacts with
“nearby” groups as well as “far-off” groups via the sparse long-range links.
In the context of epidemiology, a small-world contact network structure has
lately been found to emerge in large-scale simulations based on urban trac,
2
census, land-use and population-mobility data (Eubank et al., 2004).
Here, our aim is to model the spreading dynamics of a randomly contagious
disease, such as a common influenza. The basic idea is to capture the essential
elements of the dynamics by utilizing the SIR mechanism on a dynamically
changing small-world contact network. Related works on static and dynamic
small-world models (Watts and Strogatz, 1998; Newman and Watts, 1999;
Moore and Newman, 2000; Zekri and Clerc, 2001; Hastings, 2003; Masuda
et al., 2004; Zhu et al., 2004) have shown among others the existence of a
shortcut-density-dependent epidemic threshold as well as novel scaling prop-
erties. Our focus is explicitly on the spreading dynamics, i.e. the time-domain
development of an epidemic, formulated in terms of rate equations derived for
our particular model.
This article is organized such that first we shall describe the spreading model
in terms of a probabilistic discrete time-step process. Next, we will address
the issue of the epidemic threshold and derive necessary conditions for the
epidemic to take off. This is followed by derivation of analytical equations for
a special case of this model, where the probability of infection transmission
between neighbouring infective and susceptible individuals is set to one. We
will then discuss the dependence of the duration of an epidemic on the initial
conditions and the system size, and utilize the results in an attempt to con-
struct a method for predicting the development of an epidemic based on early
time data. Finally, we will compare time series generated with the model to
real-world data.
2 Discrete time-step SIR model on a dynamic small-world network
First, let us discuss our model for the contact network, through which the
spreading occurs. As mentioned above, social networks as well as simulated
contact networks display the small-world property, which means that “long-
range” contacts between individuals result in short average distances along
the edges of the network. These long-range contacts may be viewed either as
infrequent contacts, or random encounters. In addition, these networks have
a regular underlying structure, which may be interpreted as groups of people
with regular contacts – e.g. friends or colleagues. To capture the essentials of
such a network, we define the network as comprising a regular one-dimensional
lattice with
N
vertices having a coordination number 2
z
, with additional ran-
domly occurring long-range links, whose configuration is constantly changing.
Periodic boundary conditions are used. This network acts as the substrate for
spreading (see Fig. 1) in our model. We may also view the spreading process
as composed of two different processes: the short-range (SR) spreading process
corresponds to passing the disease on to the nearest circle of persons, and the
3
Fig. 1. Schematic of epidemic spreading on a dynamic small-world contact network
with coordination number 2
= 0, a single vertex is infected (solid
black circle). Then the infection spreads to neighbouring vertices (
z
=2.Attime
t
t
=1)aswellas
randomly chosen vertices (
t
=2,
t
= 3). Recovered vertices are shown as solid grey
circles.
long-range (LR) process to infecting any randomly encountered person.
The spreading itself is modeled using the SIR mechanism. All individuals in
the network are at all times labeled as either susceptible (S), infected (I)
or recovered (R). Initially, the status of
N − N
0
individuals is set susceptible
with
N
0
individuals infected. The dynamics of the model are such that at every
discrete time step of duration ∆
t
, every infected individual in the network
(1) Infects its nearest neighbours, if susceptible, with probability
p
s
per neigh-
bour,
(2) With probability
p
j
tries to infect one randomly chosen individual, suc-
ceeding if the individual is susceptible,
(3) With probability
p
r
recovers and can no longer be infected or infect oth-
ers.
This process can be readily iterated in numerical simulations until changes no
longer happen. The process step (1) corresponds to transmission of infection
along the regular underlying lattice (the short-range process) and step (2)
4
amounts to the randomly changing long-range connections (the long-range
process).
3 Analytical description
3.1 The epidemic threshold
First, we will derive the necessary conditions for an epidemic to take off, i.e.
the epidemic threshold. For simplicity, we will only consider the case 2
z
=2,so
that each network vertex has two nearest neighbours. As the spreading process
is stochastic in nature, we will describe it with average quantities, which should
be interpreted as averages over several epidemics. Let
I
(
t
) denote the average
number of infected individuals at time
t
and
N
(
t
) the average number of
individuals ever infected. Let us also define an auxiliary quantity
F
(
t
), which
denotes the average number of pairs of vertices where one vertex is infected
and its nearest neighbour susceptible, i.e. the number of fixed edges along
which a short-range transmission can happen. We will call
F
(
t
) the amount of
domain walls, as the short-range spreading process can be viewed as growth of
“domains” of infected people with the “walls” of these domains moving with
velocity
p
s
. Now it is straightforward to write down equations for the changes
in
N
(
t
)and
I
(
t
):
dN
(
t
)
dt
=
p
s
F
(
t
)
,
(1)
and
dI
(
t
)
dt
=
p
s
F
(
t
)
− p
r
I
(
t
)
.
(2)
Next, consider the dynamics of the domain walls. Domain walls are created
by the long-range spreading “jumps”, two walls per jump, and destroyed by
collisions when two spreading domains merge, as well as in events where an
infected individual recovers before transmitting the disease to one of its neigh-
bours. The jumps originate from the infected individuals with probability
p
j
per individual, and succeed if the randomly chosen target is susceptible, the
probability of which equals [
N − N
(
t
)]
/N
. Now consider a situation where at
t
= 0 we have a small initial number
I
0
of infected vertices. For small times
t
and large
N
, we can neglect the effect of domain wall collisions, and write
dF
(
t
)
dt
N − N
(
t
)
N
=2
p
j
I
(
t
)
− p
r
[1
− p
s
]
F
(
t
)
,
(3)
5
[ Pobierz całość w formacie PDF ]