image Home       image Fowles,       image Fitzgerald,       image r04 06 (9)       image R 22MP (3)       image 45 (3)       

Linki

[ Pobierz całość w formacie PDF ]
PHYSICAL REVIEW E, VOLUME 64, 066112
Infection dynamics on scale-free networks
Robert M. May
1
and Alun L. Lloyd
2,
*
1
Department of Zoology, University of Oxford, South Parks Road, Oxford OX1 3PS, United Kingdom
2
Program in Theoretical Biology, Institute for Advanced Study, Princeton, New Jersey 08540
~
Received 13 June 2001; published 19 November 2001
!
We discuss properties of infection processes on scale-free networks, relating them to the node-connectivity
distribution that characterizes the network. Considering the epidemiologically important case of a disease that
confers permanent immunity upon recovery, we derive analytic expressions for the final size of an epidemic in
an infinite closed population and for the dependence of infection probability on an individual’s degree of
connectivity within the population. As in an earlier study
@
R. Pastor-Satorras and A. Vesipignani, Phys. Rev.
Lett.
86
, 3200
~
2001
!
; Phys. Rev. E.
63
, 006117
~
2001
!#
for an infection that did not confer immunity upon
recovery, the epidemic process—in contrast with many traditional epidemiological models—does not exhibit
threshold behavior, and we demonstrate that this is a consequence of the extreme heterogeneity in the connec-
tivity distribution of a scale-free network. Finally, we discuss effects that arise from finite population sizes,
showing that networks of finite size do exhibit threshold effects: infections cannot spread for arbitrarily low
transmission probabilities.
PACS number
~
s
!
: 89.75.Hc, 05.70.Ln, 89.20.Hh, 87.90.
1
y
DOI: 10.1103/PhysRevE.64.066112
A wide class of infection processes can be modeled using
a network-based approach, in which individuals are modeled
as nodes and possible contacts between individuals by edges
between the nodes
many epidemiological situations and also, we argue, for
computer viruses. We assume that nodes do not recover to a
susceptible state, but rather are permanently immune to fur-
ther infection
either by the development of an appropriate
immune response, or by the installation of antiviral soft-
ware
~
. An immediate question that then
arises is how the properties of the disease and network to-
pology combine to determine the dynamics of the infection.
Recent work
@
1,2
#
!
.
The
resulting
model
is
known
as
a
susceptible-
infected-recovered
model. The long-term maintenance
of the infection is now impossible in a closed population due
to the depletion of susceptible nodes as the epidemic spreads
through the population. In general, if there were a suffi-
ciently rapid input of new susceptibles
~
SIR
!
, inspired by the study of large real-world
social and communication networks
@
1
#
@
3–6
#
, has examined the
spread of computer viruses
@
7,8
#
on the scale-free networks
@
that provide a good description of the connectivity
structure seen in the Internet and the World Wide Web
9,10
#
either by births, or
with the addition of new, unprotected computers to the net-
work
~
@
4,5
#
.
Using
a
susceptible-infected-susceptible
~
SIS
!
model
~
in
, an endemic level of infection could be reached, but in
this study we restrict our attention to the case of a closed
population.
We assume that the probability of a susceptible node ac-
quiring infection from a given neighboring infected node in a
short time interval
dt
is
!
which infected nodes recover to a susceptible state
,itwas
shown that epidemic processes on scale-free networks ex-
hibit several unexpected behaviors. In particular, they do not
exhibit the threshold phenomenon typically seen in epidemi-
ology: computer viruses can spread and persist even when
the probability of transmission is vanishingly small
!
b
dt
, and the the rate at which in-
.
Mathematical epidemiologists have long appreciated the
important role played by heterogeneity in population struc-
ture in determining properties of disease invasion, spread and
persistence, and consequently have developed many tech-
niques to facilitate the study of disease spread in heteroge-
neous populations and derived many general results
@
1
#
fected nodes recover is
g
, i.e., the average duration of infec-
tion is
D
. Furthermore, we assume that the mixing pat-
tern of the population is random, by which we mean that the
probability that a given neighbor of a node of type
i
is of
type
j
depends only on the node-connectivity distribution of
the population, which means that the probability is given by
jP
(
j
)/
5
1/
g
.
Assuming an infinite population, we can formulate the
network model in way directly equivalent to that used by
epidemiologists to study the transmission dynamics of sexu-
ally transmitted diseases, such as gonorrhoea and HIV
(
kP
(
k
)
~
see, for instance, Refs.
@
11,12
#!
@
#
.
Here, we employ these techniques and results to study the
infection dynamics of epidemics on scale-free networks,
whose node-connectivity distribution
11,12
i.e., the distribution of
probabilities that nodes have exactly
k
neighbors
~
@
11 –
!
follows a
13
#
. We denote the fraction of nodes that are both of type
i
k
2n
, where 2
power law of the form
P
(
k
)
3, and for
which the least-connected nodes have connectivity
m
.We
first focus on the
;
,n<
~
and which are susceptible to infection
by
x
i
, and the corresponding fraction of nodes that are both
of type
i
and are infected by
y
i
. The time evolution of these
quantities is given by
i.e., have
i
neighbors
!
3 case, which corresponds to the scale-
free network generated by the simplest algorithm of Barab
´
si
and Albert
n5
.
We consider a description of the infection process that,
compared with the SIS model, is more appropriate both for
@
9
#
, and then generalize to 2
,n<
3
@
10
#
(
j
˙
i
52
x
i
b
ij
y
j
~
1
!
(
j
˙
i
5
x
i
b
ij
y
j
2g
y
i
,
~
2
!
*
Corresponding author. Email address: alun@alunlloyd.com
1063-651X/2001/64
~
6
!
/066112
~
4
!
/$20.00
64
066112-1
©2001 The American Physical Society
ROBERT M. MAY AND ALUN L. LLOYD
PHYSICAL REVIEW E
64
066112
for
i
b
ij
denotes the per capita infection rate
at which sites of type
i
acquire infection from sites of type
j
.
Given the previously discussed assumption of random mix-
ing,
b
ij
5
ij
b
/
>
m
and where
^
k
&
. Here
^
k
&
denotes the average connectivity
of the nodes.
Throughout this paper, we denote the averaged
value of a function
f
(
k
) taken over the networks by
~
^
&
.
For the analysis of the infinite system, we approximate the
infinite sums involved in such averages by the corresponding
integrals.
f
(
k
)
In the initial disease-free state, before the intro-
duction of infection, all individuals are susceptible, so
y
j
5
!
0 for all
j
, and
x
j
5
P
(
j
).
^
&
r
0
would be the av-
erage number of secondary infections caused by the intro-
duction of a single infected individual into an entirely sus-
ceptible population, if the population were homogeneous
~
We define
r
0
5b
D
k
. The quantity
FIG. 1. Fraction ever infected in the SIR model on a scale-free
network with
n5
3 and
m
5
4. Solid curve gives the exact solution
obtained from Eq.
~
9
!
, and the broken curve the approximation
~
12
!
,
which is indeed a good approximation for
r
0
!
1.
^
&
. This
average number of secondary infections is a central quantity
in epidemiological theory, and is known as the basic repro-
ductive number
i.e., if every individual had exactly
k
neighbors
!
.
The standard epidemiological theory
@
12
#
shows that
this model exhibits threshold behavior, with the introduction
of
@
11,12
#
and defining
f5
m
a
and
k
5
mx
,weget
E
1
`
d
x
2
~
1
2
e
2f
x
!5
r
2
1,
where, for the heterogeneous network defined above, the ba-
sic reproductive number
R
0
equals
infection
leading
to
an
epidemic
outbreak
if
R
0
.
f5
r
0
2
@
1
2
E
2
~ f !#
,
~
7
!
@
12,14
#
where
E
2
(
f
) denotes the exponential integral of the second
C
2
R
0
5r
0
~
1
1
!
.
~
3
!
kind of
f
. Use of a standard formula
@
15
#@
Eq.
~
5.1.14
!#
allows Eq.
to be rewritten in terms of exponential inte-
grals of the first kind,
~
7
!
Here
C
V
denotes the coefficient of variation of the connec-
tivity distribution, i.e.,
C
2
k
2
2
5
^
&
^
&
1. For the scale-free
distributions considered here,
C
V
is infinite because the vari-
ance of the connectivity distribution is infinite. In contrast
with the case of a homogeneous network, which exhibits
threshold behavior at
/
k
2
S
D
1
E
1
~
f !
.
e
2f
f
2
r
0
5
1
2
~
8
!
r
0
5
1,
R
0
for the scale-free network
This equation can be solved
~
at least numerically
!
to obtain
~
is infinite for any
nonzero transmission probability and so an outbreak can al-
ways occur
at least for the infinite population case
!
f
r
0
) and hence
I
(
r
0
) can be obtained by substituting into
(
Eq.
~
4
!
,
.
Furthermore, the epidemic theory
@
1
#
E
m
`
d
k
3
~
1
2
e
2
k
a
!
5
1
2
2
E
3
~
f
!
.
@
11,12
#
shows
@
by di-
2
m
2
I
5
~
9
!
rect integration of Eqs.
~
1
!
and
~
2
!#
that the fraction of nodes
ever infected
~
the so-called final epidemic size
!
I
equals
When
r
0
!
1, we can find an approximate analytic solu-
e
2
k
a
I
5
^
1
2
&
,
~
4
!
tion of Eq.
and hence the approximate final epidemic
size. It is easy see that if
~
8
!
must be small, so we
make use of the small value expansion of
E
1
(
r
0
!
1, then
f
where
a
is determined by the equation
f
)
@
15
#@
Eq.
~
5.1.11
!#
to give
a5r
0
^
e
2
k
a
!
&
k
~
1
2
.
~
5
!
2
^
&
k
2/
r
0
52
ln
f1~
1
2g !1f
/2
1
...,
~
10
!
In order to calculate these averages, as discussed above,
we approximate
k
by a continuous quantity, taking
P
(
k
)
5
g
here
is the Euler-Mascheroni constant, 0.577 . . . . Hence
e
2
2/
r
0
e
2
2/
r
0
$
!
%
f5k
1
1
O
~
,
~
11
!
2
m
2
/
k
3
. Here
m
denotes the connectivity of the least con-
nected nodes and the constant of proportionality is deter-
mined by requiring
e
1
2g
'
e
0.423 . . .
where
k5
5
1.527 . . .
.
Finally, use of a
*
`
P
(
k
)
dk
5
1. The average connectivity
standard expression for
E
3
(
f
)
@
15
#@
Eq.
~
5.1.12
!#
gives
I
^
&
5
2
m
and the second moment,
^
k
2
&
of the nodes is
k
,isthe
5
2
f
$
1
1
O
(
f
ln
f
)
%
,or
limiting value of 2
m
2
ln(
k
max
/
m
)as
k
max
!
`
, which is infi-
H
S
D
J
nite.
Substituting this form of
P
(
k
) into expresion
e
2
2/
r
0
r
0
e
2
2/
r
0
I
5
2
k
1
1
O
.
~
12
!
~
5
!
gives
E
m
`
d
k
2
~
1
2
e
2
k
a
!
,
2
m
2
4
m
2
Figure 1 illustrates final epidemic sizes calculated using both
exact
a5r
0
~
6
!
~
9
!
and approximate
~
12
!
solutions.
066112-2
INFECTION DYNAMICS ON SCALE-FREE NETWORKS
PHYSICAL REVIEW E
64
066112
and hence that
f
is given by
FS
D
G~
3
2n !r
0
G
1/(3
2n
)
n2
2
$
~ r
0
!
%
f5
1
1
O
.
~
16
!
n2
1
Performing a similar manipulation on the integral in expres-
sion
~
14
!
and substituting the now known value of
f
gives
S
DFS
D
G
~
3
2n !r
0
G
1/(3
2n
)
n2
1
n2
2
I
5
n2
n2
2
1
r
(
n2
2)/(3
2n
)
3
$
1
1
O
~ r
0
,
!
%
.
~
17
!
Clearly, one could obtain results for the fraction of nodes
of type
i
ever infected, as in the
n5
3 special case discussed
above. But the interesting point here is that the essential
singularity,
I
FIG. 2. Fraction of nodes of each connectivity type that are ever
infected in the SIR epidemic of Fig. 1. The broken curves show
results for four different values of
r
0
~
from left to right: 1.0, 0.4,
0.25, and 0.2
!
, and the solid curve illustrates, for
r
0
5
1, the ap-
proximation discussed in the text.
~
For the smaller values of
r
0
, the
approximate curves are indistinguishable from the corresponding
exact curves.
!
e
2
2/
r
0
,ofthe
;
n5
3 case is now replaced by
;r
1/(3
2n
)
). As an example, for
milder power laws (
I
n
1/2
r
0
/3)
2
r
2
5
2.5,
f'
(
p
$
1
1
O
(
r
0
)
%
and
I
'
(
p
/3)
$
1
1
.
We finish this study with a brief discussion of finite-size
effects. The deterministic model, as described by Eqs.
O
(
r
0
)
%
~
1
!
is known, expressions for the fraction of nodes of
connectivity
k
, which are ever infected during the course of
the epidemic can be obtained. In terms of the scaled variable
i
Once
f
and
, consists of an infinite set of equations. This set may
be truncated
~
2
!
~
e.g., for simulation purposes
!
at connectivity
C
/
k
n
, but note that
C
is dependent
k
5
k
max
. We take
P
(
k
)
5
k
/
m
, the fraction of nodes of type
i
that are ever infected
is given by the standard
5
on
k
max
.
The variance of the node-connectivity distribution is still
large, but not infinite; hence
R
0
@
~
exact
!
result
@
11,12
#
that
I
i
5
1
e
2
i
f
.
2
For
r
0
!
1,
this
can
be
approximated
as
I
i
'
1
~
!#
is no longer infinite.
The finite model does exhibit threshold effects, albeit for
much lower transmission probabilities than for the corre-
sponding homogeneous situations. Using the continuous ap-
proximation discussed above, it is easy to see that, for
Eq.
3
e
2/
r
0
/
2
. We notice that, in general,
few individuals are infected in the low-connectivity classes
~
exp(
2
i
/
i
c
), where
i
c
5
k
but essentially
all individuals are infected in high-connectivity classes
although there are, of course, lots of these
!
~
Fig.
n
2
!
.
1
2
5
r
0
ln(
k
max
/
m
). Whilst it is straightforward to in-
terpret finite-size effects in terms of
k
max
, it is a little more
tricky to interpret
k
max
in terms of the number of nodes
N
in
the finite network. A rough argument, using the continuous
approximation for
P
(
k
) shows that
k
max
/
m
3,
R
0
'
The above results can be generalized to a more general
class of scale-free networks for which the exponent
n
in the
power law lies between 2 and 3
@
10
#
. For this general case,
1)
m
n2
1
/
k
n
,
we have that
P
(
k
)
5
(
n2
^
k
&
5
(
n2
1)/(
n2
2),
N
1/3
'
and that
k
2
1)
m
2
(
k
max
/
m
)
2
and
^
&
is
the
limiting
value
of
(
n2
$
1
6
R
0
'
r
0
ln
N
. As an example, this means that for a network
of size
N
2
1
, which is again infinite.
As before, substituting
P
(
k
) into Eq.
%
/(3
2n
)as
k
max
!
`
10
5
, with
m
190; for comparison, such
networks generated using the Barab
´
si and Albert algorithm
@
5
5
4,
k
max
'
~
5
!
gives an implicit
equation that determines
a
. In terms of the scaled variable
700.
Figure 3 illustrates this finite-size effect: disease invasion
does indeed require higher transmission probabilities when
k
max
is smaller, as the vertical asymptotes of
I
for the finite
models clearly demonstrate the existence of threshold behav-
ior. This result contradicts the claim
9
#
have, on average,
k
max
'
f5
m
a
, we then have
E
f
`
2
f5r
0
~
n2
2
ds
s
n2
1
~
!
f
n2
2
e
2
s
1
2
!
.
~
13
!
~ n2
1
!
@
#
that threshold behav-
ior is absent in networks of finite size. We remark that, for all
but the smallest-sized networks, the curves in Fig. 3 closely
follow
1
Once
) has been found, an expression for
I
follows
upon substitution into Eq.
a ~
or
f
~
4
!
the
analytic
solution
of
the
infinite
model
when
E
1
`
d
x
n
~
1
2
e
2
x
f
!
.
viewed over a restricted range of values of 1/
r
0
, and that the
5
~
n2
~
!
I
1
!
14
figures used to support the claim
employ somewhat re-
stricted ranges of transmission probabilities, with relatively
large transmission probabilities used for the smaller net-
works.
A second finite size effect arises from demographic
stochasticity—the random effects that arise from the popula-
tion consisting of a discrete set of individuals. For instance,
in stochastic simulations of an epidemic on a given network,
there will always be some chance that an initial infective
@
1
#
must be small, and performing
an integration by parts, one can show that the integral in
expression
As before, if
r
0
!
1 then
f
~
13
!
is given by
E
f
`
ds
s
n2
1
~
!
5
G~
2n !
n2
3
1
2
e
2
s
3
2n
$
1
1
O
~
f
!
%
,
~
15
!
2
066112-3
 ROBERT M. MAY AND ALUN L. LLOYD
PHYSICAL REVIEW E
64
066112
alternative to random mixing is assortative mixing, in which
individuals preferentially interact with similarly connected
individuals. This increases the initial rate of increase of the
epidemic, but reduces the final epidemic size
. Local
structure slows disease spread, as the shortest path joining
two individuals often involves many intermediates and also
as such networks exhibit clique behavior, with pairs of con-
nected individuals sharing many common neighbors
@
17,18
#
.
Long-range transmission events, however, even if relatively
infrequent, can substantially enhance disease spread
@
19
#
.
An important finding that emerges from our analysis is the
crucial role played by the most highly connected nodes in
spreading infection and, in the SIS model, in maintaining
infection. This has clear implications for control strategies
for diseases that spread over heterogeneous networks.
Clearly, control programs should be targetted towards the
most highly connected nodes, and such programs will be
much more effective than those that target nodes at random.
We remark that this result is clearly analogous to recent ob-
servations made regarding the attack tolerance of scale-free
networks
@
3
#
FIG. 3. Fraction ever infected in the SIR model, as in Fig. 1,
with the heavy solid curve denoting the analytic solution for the
infinite model, and broken curves denoting quantities calculated for
the finite model with
k
max
5
m
~
i.e., a homogeneous network
!
, 100,
1000, and 10 000
~
from left to right
!
. Notice the threshold phenom-
enon seen as the epidemic-size curves in finite models approach
vertical asymptotes.
@
20
#
. Furthermore, this result is well known to epi-
demiologists
for
instance, programs to prevent the spread of sexually trans-
mitted diseases often target high-risk groups, such as prosti-
tutes
@
11–13
#
; its use in public health policy
~
individual will recover before transmission of infection oc-
curs, particularly if that initial infective has a low number of
neighbors
. Further discussion of finite-size effects will
appear elsewhere
@
14
#
!
testifies that this is no mere academic curiosity.
.
Our analysis assumes random mixing and ignores local
network structure: both assumptions have received consider-
able attention in the epidemiological literature
@
16
#
A.L.L. thanks the Leon Levy and Shelby White Initiatives
Fund for financial support.
@
#
17–19
. One
@
R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett.
86
,
3200
~
2001
!
; Phys. Rev. E
63
, 066117
~
2001
!
.
@
2
#
A.L. Lloyd and R.M. May, Science
292
, 1316
~
2001
!
.
@
3
#
D.J. Watts
1
#
.
@
12
#
R.M. Anderson and R.M. May,
Infectious Diseases of Hu-
mans: Dynamics and Control
Ser. B
321
, 565
~
1988
!
~
Oxford Univ. Press, Oxford,
and
S.H.
Strogatz,
Nature
~
London
!
393
,
440
1991
!
.
@
13
#
H.W. Hethcote and J.A. Yorke, Lect. Notes Biomath.
56
,1
~
1984
!
.
@
14
#
R.M. May, A.R. McLean, and S. Gupta, Philos Trans. R. Soc.
London, Ser. B
356
, 901
~
2001
!
.
@
15
#
Handbook of Mathematical Functions
, edited by A. Abramow-
itz and I.A. Stegun
~
Dover, New York, 1974
!
.
@
16
#
A.L. Lloyd and R.M. May,
~
unpublished
!
.
@
17
#
S. Gupta, R.M. Anderson, and R.M. May, AIDS
3
, 807
~
1989
!
.
@
18
#
L. Sattenspiel, J. Koopman, C. Simon, and J.A. Jacquez, Am.
J. Phys. Anthropol.
82
, 421
~
1990
!
.
@
19
#
M.J. Keeling, Proc. R. Soc. London, Ser. B
266
, 859
~
1999
!
.
@
20
#
R. Albert, H. Jeong, and A.L. Barab
´
si, Nature
~
London
!
406
,
378
~
2000
!
.
~
1998
!
.
@
4
#
R. Albert, H. Jeong, and A.-L. Barab
´
si, Nature
~
London
!
401
,
130
~
1999
!
.
@
5
#
M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Com-
mun. Rev.
29
, 251
~
1999
!
.
@
6
#
L.A. Amaral, A. Scala, M. Barthelemy, and H.E. Stanley, Proc.
Natl. Acad. Sci. U.S.A.
97
, 11 149
~
2000
!
.
@
7
#
F.B. Cohen,
A Short Course on Computer Viruses
~
Wiley, New
York, 1994
!
.
@
8
#
J.O. Kephart, G.B. Sorkin, D.M. Chess, and S.R. White, Sci.
Am.
277
~
5
!
,88
~
1997
!
.
@
9
#
A.L. Barab
´
si and R. Albert, Science
286
, 509
~
1999
!
.
@
10
#
R. Albert and A.-L. Barab
´
si, Phys. Rev. Lett.
85
, 5234
~
2000
!
.
@
11
#
R.M. May and R.M. Anderson, Philos. Trans. R. Soc. London,
066112-4
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • zolka.keep.pl

    		•