[ Pobierz całość w formacie PDF ]
Eur. Phys. J. B
38
, 269–276 (2004)
DOI: 10.1140/epjb/e2004-00119-8
T
HE
E
UROPEAN
P
HYSICAL
J
OURNAL
B
Immunization and epidemic dynamics in complex networks
N. Madar
1
, T. Kalisky
1
,R.Cohen
1
,
2
,
a
, D. ben-Avraham
3
, and S. Havlin
1
1
Minerva Center and Department of Physics, Bar-Ilan University, Ramat-Gan, 52900, Israel
2
Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
3
Department of Physics, Clarkson University, Potsdam NY 13699-5820, USA
Received 3 November 2003
Published online 14 May 2004 – c
EDP Sciences, Societa Italiana di Fisica, Springer-Verlag 2004
Abstract.
We study the behavior of epidemic spreading in networks, and, in particular, scale free networks.
We use the Susceptible–Infected–Removed (SIR) epidemiological model. We give simulation results for
the dynamics of epidemic spreading. By mapping the model into a static bond-percolation model we
derive analytical results for the total number of infected individuals. We study this model with various
immunization strategies, including random, targeted and acquaintance immunization.
PACS.
02.50.Cw Probability theory – 02.10.Ox Combinatorics; graph theory – 89.20.Hh World Wide
Web, Internet – 64.60.-i General studies of phase transitions
1 Introduction
is recovered and can no longer be infected by the disease.
For a general introduction to epidemiology, see [10].
Another issue regarding the model used is the underly-
ing network topology. The network of (possible) contacts
between individuals determines which individuals can in-
fect each other. In general, this network may also be dy-
namic and change during the spread of the disease. We
will assume that the network is static during the epidemic
outbreak. We will also assume that the network is sparse,
i.e., that the number of links is proportional to the num-
ber of individuals. We will focus on scale free network
topologies.
Moreover, we will also allow a fraction of the individ-
uals to be immunized, i.e., these individuals can not be
infected. When a vaccination for a disease exists, immu-
nizing certain individuals against being infected by a dis-
ease as a preemptive method may be the most ecient
way to prevent loss of time and funds (and, of course,
suffering, when dealing with infected people) due to the
disease. Obviously, immunization of the entire population
will eradicate the disease entirely, but this is not always
possible, or may involve high costs and effort. Therefore,
the choice of which individuals to immune is an impor-
tant step in the immunization process, and may increase
the eciency of the immunization strategy.
The study of epidemic spreading is based upon the notion
that a disease is conveyed by contact between an infected
individual and an uninfected individual who is susceptible
to the disease. An endemic stage is reached if a finite frac-
tion of the population is infected. Similarly, this notion
may describe the spreading of a computer virus through
a network of computers. Recently, it has been shown that
in a class of scale free networks an epidemic may spread
regardless of how low is its rate of infection [1–3].
An extensive research was dedicated to the subject
of attacks on networks [4–7], by targeting individuals ei-
ther randomly or by intentionally. In particular, the Inter-
net and the WWW were shown to be robust to random
breakdowns and fragile to intentional attacks, due to their
scale-free distribution of nodes. However, these studies fo-
cused on the results of damaging computers by an outside
source, and did not take into account the possibility of
a propagation of a problem throughout the connections
amongst the computers themselves, in a way similar to a
spreading of a disease. The application of network stabil-
ity to immunization has been studied in [8], and the effect
of partial information has been studied in [9].
Several models have been proposed for epidemic dy-
namics, differing in the disease stages, the dynamical pa-
rameters, and the underlying structure of contacts. The
most common models for the disease dynamics are the
SIR, SIS and SIRS models, which represent the develop-
ment of each individual’s disease in a network. In this
paper we will focus on the SIR model, where an infected
individual is infective for some period of time, and then
2 Epidemic dynamics
A contagious disease may turn into an epidemic, if the
number of infected (sick) individuals is of the order of the
number of individuals in the whole system. When there are
no more sick individuals in the system (only susceptible
a
e-mail:
cohenr@shoshi.ph.biu.ac.il
270
The European Physical Journal B
left, and the others are removed), we may say that the
disease is cured.
In many cases, an epidemic is indeed being cured. The
main consideration therefore should be how much time is
required for the system to reach such a stage, and how
many individuals are being infected throughout the pro-
cess. If both the time of the contagious period and the
number of people exposed to it can be reduced, then the
amount of suffering and loss of resources can be reduced
as well.
from a site which is, in itself, reached by following a link.
This is similar to the course of the epidemic. If an infected
individual infects, on average, at least one other individ-
ual, then the epidemic can reach an endemic state. Since
a site can be reached by one of its
k
links, its probability
of being reached is
kP
(
k
)
/
(
N k
), where
N
is the num-
ber of nodes,
P
(
k
) is the fraction of nodes having degree
=
k
kP
(number of links)
) denotes the av-
erage degree of nodes in the network. The probability of
each of its
k
,and
k
(
k
k −
1 outgoing links of infecting its neighbor
is
p
b
. Since the network is randomly connected, as long
as the epidemic is not spread yet, the average number of
influenced neighbors is:
2.1 The SIR model
p
b
k
P
(
k
)
k
(
k −
1)
The SIR model represents the development of a disease
in a network of connected individuals. S stands for the
susceptible stage, where the individual is healthy. I stands
for the infected stage, where the individual is infected with
the disease and can infect other individuals in contact with
it. R is the removed stage, where the individual is either
recovered and has acquired immunization to the disease
or otherwise permanently removed from the system.
In our numerical simulations all the individuals (ver-
tices) are at first susceptible, i.e., they are all healthy and
none of them is immuned to the disease. One vertex, cho-
sen randomly, is being infected. At each time step, every
susceptible neighbor of an infected vertex has a probabil-
ity of becoming infected itself, and each infected vertex
has a probability to be removed from the system. We as-
sume here that both probabilities (infection and removal)
are the same for each vertex and its neighbors (networks
having different probabilities for each vertex are studied
in [3]).
n
i
=
.
(1)
k
n
i
>
Therefore, an endemic state can be reached only if
1, leading to [5,6]
k
2
k
−
1
>p
−
1
b
.
(2)
From this expression it can easily be seen that scale free
networks, with degree distribution
P
k
∼ k
−γ
,with
(
)
γ ≤
3, having a divergent second moment, undergo
the transition only at
0 [5,6]. That is, an epi-
demic can spread in this network regardless of how small
the infection probability and how quick is the recovery
process [1,2].
p
b
→
3 Immunization
In general immunization can be seen as a site percolation
problem. Each immunized individual can be regarded as
a site which is removed from the network. The goal of the
immunization process is to pass (or at least approach) the
percolation threshold, leading to minimization of the num-
ber of infected individuals. The complete model of SIR and
immunization can be considered as a site–bond percola-
tion model, and the immunization is considered successful
if the network is below the percolation threshold.
It is well established that immunization of randomly
selected individuals requires immunizing a very large frac-
tion
2.2 The SIR model as bond percolation
One of the nicest features of the SIR model is that de-
spite it being a dynamic model it can be mapped into a
completely static one [3,11,12]. Consider a network where
each node transmits the epidemic to each of its neighbors
with rate
.
The infection can be, therefore, considered as a Poisson
process, with average
r
, and is removed with average recovery time
τ
. Thus, the probability for each
neighbor
not
to be infected is
rτ
e
−rτ
.
The outcome of this process is therefore the same as
bond percolation, in which each directed link is occupied
with probability
of the population, in order to arrest epidemics
that spread upon contact between infected individuals
[1,4,5,10,13–15]. Many diseases require 80%–100% immu-
nization. For example, Measles requires 95% of the pop-
ulation to be immunized [10]. The same is correct for
the Internet, where stopping computer viruses requires al-
most 100% immunization [1,4,5,16]. On the other hand,
targeted immunization of the most highly connected in-
dividuals [4,6–8,10,17], while effective, requires global in-
formation about the network in question, rendering it im-
practical in many cases. Here, we develop a mathematical
model and propose an effective strategy, based on the im-
munization of a small fraction of
random acquaintances
of randomly selected nodes. In this way, the most highly
connected nodes are immunized, and the process prevents
f
− e
−rτ
.If
have the same
value for each node, the network can be taken to be non-
directed. While information on the epidemic dynamics is
lost by this description, the critical threshold for the dy-
namic model can be deduced from the bond percolation
problem. Furthermore, the total fraction of infected indi-
viduals in the endemic state is the same as the size of the
giant component of the percolation model, and the prob-
ability of a single disease event to decay before reaching
the endemic state equals the fraction of finite components
in the percolation networks.
To find the threshold for bond percolation in networks
one should consider the average number of links outgoing
p
b
=1
r
and
τ
N. Madar et al.: Immunization and epidemic dynamics in complex networks
271
k
∗
and 0
epidemics with a small finite immunization threshold and
without requiring specific knowledge of the network.
and
<c≤
1 are determined by the condition
P
(
k
)
θ
f
(
k
)=1
− f.
(5)
k
3.1 Random immunization
To find the critical immunization threshold using this
strategy, one can again find the fraction giving, on average,
one outgoing infective link per infected individual. this
amounts to the demand:
Social networks are known to possess a broad distribution
of the number of links (contacts),
, emanating from a
node (an individual) [18–22]. Examples are the web of sex-
ual contacts [23], movie-actor networks, science citations
and cooperation networks [24,25] etc. Computer networks,
both physical (such as the Internet [26]) and logical (such
as the WWW [27], e-mail [28] and trust networks [29])
are also known to possess wide, scale-free, distributions.
Studies of percolation on broad-scale networks show that
a large fraction
k
k
(
k −
1)
P
(
k
)
θ
f
c
(
k
)
p
−
1
b
=
.
(6)
k
k
Solving equation (6) in conjunction with equation (5) al-
lows the calculation of the exact immunization threshold.
The implications of partial knowledge of the node degrees,
leading to functions other than
f
c
of the nodes need to be removed (im-
munized) before the integrity of the network is compro-
mised. This is particularly true for scale-free networks,
P
θ
f
(
k
), were studied in [9].
ck
−γ
3—thecase
of most known networks [18–20] — where the percolation
threshold
(
k
)=
(
k ≥ m
), where 2
<γ<
3.3 Acquaintance immunization
1, and the network remains connected
(contagious) even after removal of most of its nodes [5]. In
other words, with a random immunization strategy almost
all of the nodes need to be immunized before an epidemic
is arrested (see Fig. 1).
To calculate the immunization threshold, one should
consider the site–bond percolation model. The considera-
tions are the same as for the epidemic threshold (Eq. (2)),
with the exception that a site may also be immunized, in
which case it can not propagate the disease. This adds
another factor of
f
c
→
3.3.1 Description
One problem with the targeted immunization approach is
that it requires a complete, or at least fairly good knowl-
edge of the degree of each node in the network. Such global
information often proves hard to gather, and may not even
be well-defined (as in social networks, where the number
of social relations depends on subjective judging). The ac-
quaintance immunization strategy proposed herein works
at low immunization rates,
f
, and obviates the need for
, the probability that a site is
not immunized, to the calculation. Leading to
k
2
k
−
p
s
=1
− f
global information.
In our approach [30], we choose a random fraction
p
1
of the
nodes and look for a random acquaintance with
whom they are in contact (thus, the strategy is purely
local, requiring minimal information about randomly se-
lected nodes and their immediate environments ). The ac-
quaintances, rather than the originally chosen nodes, are
the ones immunized. The fraction
N
p
s
p
b
)
−
1
.
>
(
(3)
As can be seen, in this case as well, the epidemic will only
be arrested if
0, meaning that for every epidemic
almost the entire population must be immunized in order
to prevent the epidemic spreading.
p
b
p
s
→
may be larger than
1, for a node might be queried more than once, on aver-
age, while the fraction of nodes immunized
p
f
is always less
than or equal to 1.
3.2 Targeted immunization
3.3.2 Analysis
When the most highly connected nodes are targeted first,
removal of just a small fraction of the nodes results in the
network’s disintegration [4,6,7]. This has led to the sug-
gestion of targeted immunization of the HUBs (the most
highly connected nodes in the network) [8,9].
The simplest targeted immunization strategy calls for
the immunization of the most highly connected individ-
uals. To use this approach, the number of connections of
each individual should be known (at least approximately
– see [9]). In this case, the probability that a site is not
immunized, when the immunization rate is
Suppose we apply the acquaintance strategy on a random
fraction
f
c
,
needed to stop the epidemic can be analytically calculated.
In each event, the probability that a particular node with
k
p
of the network. The critical fractions,
p
c
and
)
[6,5]. This quantifies the known fact that randomly se-
lected acquaintances have, on average, a higher degree
than randomly selected nodes [31,32].
Suppose we follow some possible branch in the course
of the epidemic, starting from a random link of the span-
ning cluster. That is, we study the possible spread of the
epidemic by considering nodes that are not immunized,
and therefore are susceptible to the epidemic that may
become infected. In some layer (hop-distance from the
contacts is selected for immunization is
kP
(
k
)
/
(
N k
f
,is
θ
f
(
k
),
where,
,k<k
∗
,
c,
1
k
∗
,
θ
f
(
k
)=
k
=
(4)
,k>k
∗
,
0
272
The European Physical Journal B
k
) nodes of degree
k
.In
starting point),
l
,wehave
n
l
(
Substituting these results in (7) yields:
k
−
the next layer (
1new
neighbors (excluding the one through which we arrived).
Let us denote the event that a node of degree
l
+ 1) each of those nodes has
e
−p/k
k
e
−p/k
p
b
ν
k−
2
k
)(
k
−
n
l
+1
(
k
)=
φ
(
k
)
n
l
(
1)
.
p
is suscep-
tible to the disease (not immunized, and therefore may
be infected through the course of epidemic spreading) by
s
k
. To find out the number of nodes,
k
(12)
k
,itleads
to the stable distribution of degree in a layer
Since the sum in (12) does not depend on
l
:
n
l
(
k
)=
n
l
+1
(
k
), of degree
a
l
ν
k−
2
e
−p/k
,forsome
φ
(
k
)
a
l
. Substituting this into (12)
k
that are susceptible and are reached in the course of
the epidemic, we multiply the number of links going out
of the
p
yields:
p
b
k
l
th layer by the probability of reaching a node of
ν
k
−
2
p
e
−
2
p/k
k
)(
k
−
n
l
+1
(
k
n
l
(
k
φ
.
)=
)
(
1)
(13)
degree
k
through following a link from a susceptible node,
k|k
,s
k
). Then, we multiply by the probability that this
node is also susceptible given both the node and the neigh-
bor’s degrees, and the fact that the neighbor is also sus-
ceptible,
p
(
Therefore, if the sum is larger than 1 the branching pro-
cess will continue forever (the percolating phase), while if
it is smaller than 1 immunization is sub-critical and the
epidemic is arrested. Thus, we obtain a relation for
s
k
|k, k
,s
k
). Since below and at the critical
percolation threshold loops are irrelevant [5], one can ig-
nore them for the calculation of the threshold. Therefore,
p
(
p
c
:
ν
k−
2
p
c
e
−
2
p
c
/k
=
p
−
1
b
φ
(
k
)(
k −
1)
,
(14)
p
b
k
k
)(
k
−
k|k
,s
k
)
s
k
|k, k
,s
k
)
k
n
l
+1
(
k
)=
n
l
(
1)
p
(
p
(
.
where the case
1 corresponds to full immunization,
i.e. stopping the epidemic regardless of its infection rate.
The fraction of immunized nodes is easily obtained
from the fraction of nodes which are not susceptible,
p
b
→
(7)
By using Bayes’ rule:
s
k
|k, k
)
k|k
)
k|k
,s
k
)=
p
(
p
(
p
(
.
(8)
ν
p
c
,
f
c
=1
−
P
(
k
)
p
(
s
k
|k
)=1
−
P
(
k
)
(15)
p
(
s
k
|k
)
k
k
where
P
(
k
) is the regular distribution, and
p
c
is found nu-
Assuming that the network is uncorrelated (no degree-
degree correlations), the probability
ν
k−
2
p
c
merically using equation (14). The term
in equation
(14) induces an exponential cutoff on the degree distri-
bution of susceptible nodes for 0
φ
(
k
)ofreachinga
k
:
node with degree
k
via a link is independent of
1. Therefore,
the sum in equation (14) becomes finite for some finite
ν
p
c
>
<ν
p
c
<
k|k
)=
φ
(
k
)
≡ p
(
kP
(
k
)
/k .
(9)
0. Substituting this into equation (15) indicates that
f
c
= 1, and is finite even in the thermodynamic limit.
A related immunization strategy calls for the immu-
nization of acquaintances referred to by at least
(A study of cases where correlations exists can be found
in [3,33,34].)
A random site (of degree
n
nodes.
k
) is selected in each step
(Above, we specialized to
n
= 1.) The threshold is lower
with probability 1
. The probability of being redirected
to a specific acquaintance is 1
/N
the larger
is, and may justify, under certain circum-
stances, this somewhat more involved protocol.
To analyze the threshold for the double acquaintance
n
/k
. Thus, the probability
that the acquaintance is
not
selected in one particular at-
tempt, is 1
Nk
), and in all
−
1
/
(
Np
vaccination attempts,
(
= 2) case, we should replace the probabilities for sus-
ceptibility with the appropriate probabilities considering
the fact that a node is immunized only if 2 of its contacts
point at it. Since the process is a Poisson process (in the
limit of large
n
it is
1
Np
1
Nk
≈ e
−p/k
k
)
ν
p
(
≡
−
.
(10)
N
), the probabilities are:
If the neighbor’s degree is not known, the probability is
ν
p
≡ν
p
(
e
−p/k
s
k
|k, k
)=
e
−p/k
k−
2
, where the average (and all averages hence-
forth) is taken with respect to the probability distribution
φ
k
)
p
(
(16)
e
−p/k
1+
k
pe
−p/k
k
×
(
k −
1) +
,
(
k
). In general, the probability that a node with degree
k
e
−p/k
k
,ifnootherinforma-
tion exists on its neighbors. If the degree of one neighbor
(which is the one through which the epidemic propagated)
is known to be
p
s
k
|k
is susceptible is
(
)=
and
e
−p/k
k−
1
pe
−p/k
k
e
−p/k
p
(
s
k
|k
)=
k
+
.
(17)
e
−p/k
×e
−p/k
k−
1
.Since
the fact that a neighbor with a known degree is immunized
does not provide any further information about a node’s
probability of immunization, it follows that
k
:
s
k
|k, k
)=
p
(
ν
p
≡ e
−p/k
We will use the notation
and
µ
p
≡
pe
−p/k
/k
. Using Bayes’ rule as before and substituting
into equation (7), one obtains
s
k
|k, k
)=
p
(
p
s
k
|k, k
,s
k
). Using the above equations one obtains:
(
p
b
k
n
l
(
e
−p/k
e
−p/k
k
)
ν
p
k−
3
n
l
+1
(
k
)=
φ
(
k
)
(18)
e
−p/k
e
−p/k
k
)
k
|k, s
k
)=
φ
(
(
k
−
1)
[
(
k
−
1)
µ
p
+
(
1+
k
)
ν
p
][
(
k−
1)
µ
p
+
(
1+
k
)
ν
p
]
ν
p
+
k
µ
p
p
(
.
(11)
×
.
N. Madar et al.: Immunization and epidemic dynamics in complex networks
273
1
It can now be seen that the kernel of equation (18) is
separable into three functions
0.8
ν
p
k−
3
e
−p/k
+
c
l
k
n
l
(
k
)=
φ
(
k
)
a
l
+
b
l
k
.
(19)
0.6
f
c
Substituting this back into equation (18) leads to the ma-
trix notation
0.4
a
l
+1
b
l
+1
c
l
+1
a
l
b
l
c
l
p
b
k
e
−
2
p/k
ν
p
k
−
3
k
)(
k
−
φ
(
1)
0.2
=
,
M
ν
p
+
k
µ
p
0
2
2.5
3
3.5
(20)
λ
where
M
is the matrix:
Fig. 1.
Critical immunization threshold,
f
c
, as a function of
γ
in scale-free networks (with
m
= 1), for the random immuniza-
tion (
◦
), acquaintance immunization (
), double acquaintance
immunization (
), and targeted immunization (
)strategies.
Curves represent analytical results, while data points represent
simulation data, for a population
N
=10
6
(due to the popu-
lation’s final size
f
c
<
1 for random immunization even when
γ<
3). Full symbols are for random and acquaintance immu-
nization of assortatively mixed networks (where links between
sites of degree
k
1
A
p
(
k
)
k
k
)
k
A
p
(
k
)
A
p
(
,
µ
p
B
p
(
k
)
k
M
=
k
)
k
µ
p
B
p
(
k
)
(21)
µ
p
B
p
(
k
)
pν
p
C
p
(
k
)
k
k
)
k
pν
p
C
p
(
pν
p
C
p
(
k
)
k
µ
p
− µ
p
,
and we have used the definition
B
p
(
≡ ν
p
+
≡ ν
p
−µ
p
+
ν
p
p
k
k
)
k
)
k
)
k
)+
C
p
(
pµ
p
ν
p
.
Since this is a branching process, it is controlled by the
largest eigenvalue of the matrix
and
A
p
(
≡ C
p
(
B
p
(
N
,
and
k
2
(
>k
1
) are rejected with probability
0
.
7
1
−
k
k
2
).
=
k
e
−
2
p/k
ν
p
k
−
3
k
)(
k
−
φ
(
1)
N
M
.
(22)
ν
p
+
k
µ
p
1
This eigenvalue can be calculated numerically using stan-
dard methods and the immunization threshold is obtained
when
0.8
λ
1
≡
max
v
||
Mv
||/||
v
||
, the largest eigenvalue of
N
,
0.6
satisfies
/p
b
. This can be solved numerically for
a given degree distribution
λ
1
=1
f
c
P
(
k
). The critical value
p
c
is
then obtained and can be used to evaluate
f
c
, the fraction
0.4
of immunized individuals,
0.2
ν
p
c
k−
1
(
f
c
=1
−
P
(
k
)
ν
p
c
+
pkµ
p
c
)
.
(23)
k
0
0
20
40
60
80
100
d
Fig. 2.
Critical concentration,
f
c
, for the bimodal distribution
(of two Gaussians) as a function of
d
, the distance between
the modes. The first Gaussian is centered at
k
=3andthe
second one at
k
=
d
+ 3 with height 5% of the first. Both
have variance 2 (solid lines) or 8 (dashed lines). Top 2 lines
are for random immunization. The bottom 2 lines are for ac-
quaintance immunization. All curves are analytically derived
from equations (15) and (14). Very similar results have been
obtained for bimodal distributions of two Poissonians. Note
that also for the case
d
= 0, i.e. a single Gaussian, the value of
f
c
reduces considerably due to the acquaintance immunization
strategy. Thus the strategy gives improved performance even
for relatively narrow distributions [36].
3.3.3 Discussion
The acquaintance immunization strategy is effective for
any broad-scale distributed network. Here we give exam-
ples for scale-free and bimodal distributions, which are
common in many natural networks. We also give an exam-
ple of an assortatively mixed network (where high degree
nodes tend to connect to other high degree nodes [35]). We
also discuss the effectiveness of the strategy in conjunction
with the SIR epidemiological model.
In Figure 1, we show the immunization threshold
f
c
needed to stop an epidemic in networks with 2
5
(this covers all known cases). Plotted are curves for the
(inecient) random strategy, and the strategy advanced
here, for the cases of
<γ<
3
.
tend to connect to other high degree nodes, which is the
case for many real networks.
Figure 2 gives similar results for a bimodal distri-
bution (consisting of two Gaussians, where high degree
nodes are rare compared to low degree ones). This distri-
bution is also believed to exist for some social networks,
in particular, for some networks of sexual contacts. The
n
= 1 and 2. Note that while
f
c
=1
<γ<
for networks with 2
3 (e.g. the Internet) it decreases
dramatically to values
25 with the suggested strat-
egy. The figure also shows the strategy’s effectiveness in
case of assortatively mixed networks [35], i.e., in cases
where
f
c
≈
0
.
k
|k
p
(
) does depend on
k
, and high degree nodes
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mirabelkowy.keep.pl