RAPID COMMUNICATIONS
PHYSICAL REVIEW E, VOLUME 65, 055103 R
Halting viruses in scale-free networks
Zoltán DezsQ and Albert-LászlĂł Barabási
Department of Physics, University of Notre Dame, Notre Dame, Indiana 46556
Received 7 March 2002; published 21 May 2002
The vanishing epidemic threshold for viruses spreading on scale-free networks indicate that traditional
methods, aiming to decrease a virus spreading rate cannot succeed in eradicating an epidemic. We demonstrate
that policies that discriminate between the nodes, curing mostly the highly connected nodes, can restore a finite
epidemic threshold and potentially eradicate a virus. We find that the more biased a policy is towards the hubs,
the more chance it has to bring the epidemic threshold above the virus spreading rate. Furthermore, such
biased policies are more cost effective, requiring less cures to eradicate the virus.
DOI: 10.1103/PhysRevE.65.055103 PACS number s : 89.75.Fb, 89.75.Hc, 89.20.Hh
While most diffusion processes of practical interest, rang- ber of nodes, and are therefore easily infected. Once infected,
ing from the spread of computer viruses to the diffusion of they pass on the virus to a significant fraction of the nodes in
sexually transmitted diseases, take place on complex net- the system.
works, the bulk of diffusion studies have focused on model The finding that the epidemic threshold vanishes in scale-
systems, such as regular lattices or random networks 1 3 .
free networks has a strong impact on our ability to control
A series of recent results indicate, however, that real net-
various virus outbreaks. Indeed, most methods designed to
works significantly deviate from the structure of these model
eradicate viruses biological or computer based aim at re-
systems 4 deviations that have a strong impact on the
ducing the spreading rate of the virus, hoping that if falls
diffusion dynamics as well. In particular, the networks re-
under the critical threshold , the virus will die out natu-
c
sponsible for the spread of computer viruses, such as the
rally. With a zero threshold, while a reduced spreading rate
Internet 5 or the email network 6 , have a scale-free topol-
will decrease the virus prevalence, there is little guarantee
ogy 7 , exhibiting a power-law degree distribution P(k)
that it will eradicate it. Therefore, from a theoretical perspec-
k , where ranges between 2 and 3. Similarly, a recent
tive viruses spreading on a scale-free network appear unstop-
study indicates that the social network responsible for the
pable. The question is, can we take advantage of the in-
spread of sexually transmitted diseases, such as AIDS, also
creased knowledge accumulated in the past few years about
exhibits a scale-free structure 8 . The topology of scale-free
network topology to understand the conditions in which one
networks fundamentally deviate from the topology of both
can successfully eradicate viruses?
regular lattices and random networks 9 , differences that
Here we study the spreading of a virus to which there is a
impact the network s robustness and attack tolerance 10 or
cure, eradicating the virus from the node to which it is ap-
the dynamics of synchronization 11 . It is not unexpected,
plied to, but which does not offer a permanent protection
therefore, that the broad degree distribution leads to unex-
against the virus. If such a cure is available to all nodes,
pected diffusion properties as well 12 .
treating simultaneously all infected nodes will inevitably
A simple model often used to study the generic features of
wipe the virus out. However, due to economic or policy con-
virus spreading is the susceptible-infected-susceptible SIS
siderations the number of available cures is often limited.
model. In this model an individual is represented by a node,
which can be either healthy or infected. Connections This applies to AIDS, for which relatively effective but pro-
between individuals along which the infection can spread are hibitively expensive cures are available, unable to reach the
represented by links. In each time step a healthy node is most affected segments of population due to economic con-
infected with probability if it is connected to at least one
siderations 13 . But it also applies to computer viruses,
infected node. At the same time an infected node is cured
where only a small fraction of users commit the time and
with probability , defining an effective spreading rate
investment to update regularly their virus protection system.
/ for the virus. We show that distributing the cures randomly in a scale-free
The behavior of the SIS model is well understood if the network is ineffective, being unable to alter the fundamental
nodes are placed on a regular lattice or a random network properties of the threshold-free diffusion process. However,
1 . Diffusion studies indicate that viruses whose spreading even weakly biased strategies, that discriminating between
rate exceeds a critical threshold will persist, while those the nodes, curing with a higher probability the hubs than the
c
under the threshold will die out shortly. Recently, however, less connected nodes, can restore the epidemic threshold. We
Pastor-Satorras and Vespignani have shown 12 that for find that such hub-biased policies are more cost effective as
scale-free networks with 3 the epidemic threshold van- well, requiring fewer cures than those distributing the cures
ishes, i.e., 0. This finding implies that on such networks indiscriminately.
c
even weakly infectious viruses can spread and prevail. This Curing the hubs. The vanishing epidemic threshold of a
vanishing threshold is a consequence of the hubs nodes virus spreading in a scale-free network is rooted in the infi-
with a large number of links encoded by the tail of power nite variance of the degree distribution 12 . Indeed, the
law P(k). Indeed, the hubs are in contact with a large num- threshold depends on the variance as
c
1063-651X/2002/65 5 /055103 4 /$20.00 65 055103-1 ©2002 The American Physical Society
RAPID COMMUNICATIONS
ZOLTÁN DEZSP AND ALBERT-LÁSZLĂ“ BARABÁSI PHYSICAL REVIEW E 65 055103 R
FIG. 1. The epidemic threshold as a function of k0.
FIG. 2. Prevalence measured as the fraction of infected nodes
in function of the effective spreading rate for 0( ),
k
0.25( ), 0.50( ), 0.75( ), and 1( ), as predicted by Monte
. 1
c
Carlo simulations using the SIS model on a scale-free network with
k2
N 10 000 nodes.
On a regular lattice the degree distribution is a function,
while on a random network it follows a Poisson distribution, administering a cure to an infected node with k links in a
in both cases resulting in a finite k2 , and therefore nonzero given time frame depends on the node s degree as k , where
. In contrast, if the virus spreads on a scale-free network, characterizes the policy s ability to identify hubs. In this
c
for which P(k) follows a power law with 3, the variance framework 0 corresponds to random cure distribution,
is infinite and the epidemic threshold is 0. Therefore, to which is expected to have zero epidemic threshold while
c
restore a finite epidemic threshold, which would allow the corresponds to an optimal policy that treats all hubs with
infection to die out, one needs to induce a finite variance. As degree larger than k0. Within the framework of the SIS
the origin of the infinite variance is in the tail of the degree model we assume that each node is infected with probability
distribution, dominated by the hubs, one expects that curing , but each infected node is cured with probability
all hubs with degree larger than a given degree k0 would k , again becoming susceptible to the disease. We define
0
restore a finite variance and therefore a nonzero epidemic the spreading rate as / . As each healthy node is sus-
0
threshold. Indeed, if on a scale-free network nodes with de- ceptible again to the disease, a node can get multiple cures
gree k k0 are always healthy, the epidemic threshold is fi- during a simulation.
nite and has the value 14 We place the nodes on a scale-free network 16 and ini-
tially infect half of them. After a transient regime the system
k k0 m k0 1
reaches a steady state, characterized by a constant average
ln . 2
c
density of infected nodes , which depends on both the
k2 k0m m
spreading rate and Fig. 2 . The 0 limit corresponds
This expression indicates that the more hubs we cure i.e., to random immunization in which case the epidemic thresh-
the smaller k0 is , the larger the value of the epidemic thresh- old is zero. As treating only the hubs will restore the nonzero
old Fig. 1 15 . Therefore, the most effective policy against epidemic threshold, for we expect a nonzero . Yet,
c
an epidemic would be to cure as many hubs as economically the numerical simulations indicate that we have a finite c
viable. The problem is that in most systems of interest we do well before the limit. Indeed, as Fig. 2 shows, is
c
not have detailed network maps, thus we cannot effectively clearly finite for 1 and so is for smaller value of as
identify the hubs. Indeed, we do not know the number of well. The numerical simulations do not give an unambiguous
sexual partners for each individual in the society, thus we answer to the crucial question: Is there a critical value of at
cannot identify the social hubs that should be cured if in- which a finite appears, or for any nonzero we have a
c
fected. Similarly, on the email network we do not know finite ?
c
which email accounts serve as hubs, as these are the ones Mean-field theory. To interpret the results of the numeri-
that, for the benefit of all email users, should always carry cal simulations we studied the effect of a biased policy using
the latest antivirus software. the mean-field continuum approach 1,12 . Denoting by
Short of a detailed network map, no method aiming to
(t) the density of infected nodes with connectivity k, the
k
identify and cure the hubs is expected to succeed at its goal
time evolution of (t) can be written as 12
k
of finding all hubs with degree larger than a given k0. Yet,
policies designed to eradicate viruses could attempt to iden- t k t 1 t k . 3
t k 0 k k
tify and cure as many hubs as possible. Such biased policy
The first term in the right-hand side rhs describes the prob-
will inevitably be inherently imperfect, as it might miss some
ability that an infected node is cured, and it is therefore pro-
hubs, and falsely identify some smaller nodes as hubs. The
portional to the number of infected nodes (t) and the prob-
question is, however, would a policy biased towards curing
k
the hubs, without a guarantee that it can identify all of them, ability k that a node with k links will be selected for a
0
succeed at restoring the epidemic threshold? cure. The second term is the probability that a healthy node
To investigate the effect of incomplete information about with k links is infected, proportional to the infection rate ( ),
the hubs we assume that the likelihood of identifying and the number of links (k), the number of healthy nodes with k
055103-2
RAPID COMMUNICATIONS
HALTING VIRUSES IN SCALE-FREE NETWORKS PHYSICAL REVIEW E 65 055103 R
links 1 (t) , and the probability ( ) that a given link
k
points to an infected node. The probability ( ) is propor-
tional to kP(k), therefore, it can be written as
kP k
. 4
k
k
sP s
s
Using / and imposing the (t) 0 stationary con- FIG. 3. The dependence of the epidemic threshold on as
0 t k c
dition we find the stationary density as predicted by our calculations continuous line based on the con-
tinuum approach, and by the numerical simulations based on the
SIS model boxes . The small deviation between the numerical re-
. 5
k sults and the analytical prediction is due to the uncertainty in deter-
k 1
mining the precise value of the threshold in Monte Carlo simula-
tions.
Combining Eqs. 4 and 5 and using the fact that the con-
nectivity distribution P(k) 2m2/k 3 for the scale-free net-
virus to die out naturally. To test the validity of prediction 9
work 7 , we obtain
we determined numerically the ( ) curve from the simula-
tions shown in Fig. 2. As Fig. 3 shows, we find excellent
dk
m 1. 6
agreement between the simulations and the analytical predic-
m
k2 k 1
tion 9 .
Cost effectiveness. A major criteria for any policy de-
The average density of infected nodes is given by
signed to combat an epidemic is its cost effectiveness. Sup-
plying cures to all nodes infected by a virus is often prohibi-
dk
P k k 2m2 . tively expensive. Therefore, policies that obtain the largest
k m
k3 k 1
effect with the smallest number of administered cures are
7
more desirable. To address the cost effectiveness of a policy
targeting the hubs we calculated the number of cures admin-
Equations 6 and 7 allow us to calculate the average den-
istered in a time step per node for different values of .
sity of infected nodes for any value of . For 0 they
Figure 4 indicates that increasing the policy s bias towards
reduce to the case studied in Ref. 12 giving 0. For
c
the hubs by allowing a higher value for decreases rapidly
1 we can solve Eq. 6 , and using Eq. 7 we obtain
the number of necessarily cures. Therefore, policies that dis-
tribute the cures mainly to the nodes with more links are
1
, 8
1 more cost effective than those that spread the cures ran-
domly, blind to the node s connectivity. We can understand
the origin of the rapid decay in c( ) by noticing that the
which indicates that for 1 the epidemic threshold is fi-
number of cures administered per unit time is proportional to
nite, having the value ( 1) 1 15 .
c
the density of infected nodes. From Fig. 2 we see that for a
To determine the epidemic threshold as a function of
given value of the spreading rate the prevalence is decreasing
we need to solve the ( ) 0 equation. While we cannot get
as increases, decreasing the number of necessary cures as
( ) for arbitrary values of , we can solve Eq. 6 in
well.
using that at the threshold we have ( ) 0. In this
c c
case Eq. 6 predicts that the epidemic threshold depends on
as
m 1. 9
c
For 0 we recover 0, confirming that random immu-
c
nization cannot eradicate an infectious disease. For 1 Eq.
9 predicts that the epidemic threshold is 1, in agree-
c
ment with Eq. 8 . Most important, however, Eq. 9 indi-
cates that is nonzero for any positive , i.e., any policy
c
that is biased towards curing the hubs can restore a finite
epidemic threshold. Furthermore, policies with larger are
FIG. 4. The number of cures c administered in a unit time per
expected to be more likely to lead to the eradication of the
node for different values of . The rapidly decaying c indicates that
virus, as they result in larger values. Therefore, Eq. 9
c
the more successful a policy is in selecting and curing hubs larger
indicates that a potential avenue to eradicating a virus is to
is ), the fewer the cures are required for a fixed spreading rate
increase the effectiveness of identifying and curing the hubs.
( 0.75). For 0 the number of cures is calculated by c
Indeed, if the virus has a fixed spreading rate, increasing
/( ) /(1 ) which gives c 0.43, which value is in
could increase beyond , thus making it possible for the good agreement with the numerical results.
c
055103-3
RAPID COMMUNICATIONS
ZOLTÁN DEZSP AND ALBERT-LÁSZLĂ“ BARABÁSI PHYSICAL REVIEW E 65 055103 R
In summary, our numerical and analytical results indicate the higher are its chances of eradicating the virus. Finally,
that targeting the more connected infected nodes can restore the simulations show that a biased treatment policy is
the epidemic threshold, therefore making possible the eradi- not only more efficient but it is also less expensive
cation of a virus. Most important, however, is the finding than random immunization. These results, beyond improving
that even moderately successful policies with small our understanding of the basic mechanisms of virus
can lead to a nonzero epidemic threshold. As the magnitude spreading, could also offer important input into designing
of rapidly decreases with , the more effective a policy effective policies to eradicate computer or biological infec-
c
is at identifying and curing the hubs of a scale-free network, tions.
1 R. M. Anderson and R. M. May, Infectious Diseases of Hu- 378 2000 ; D. S. Callaway, M. E. J. Newman, S. H. Strogatz,
mans: Dynamics and Control Oxford University Press, Ox- and D. J. Watts, Phys. Rev. Lett. 85, 5468 2000 ; R. Cohen, K.
ford, 1991 ; J. D. Murray, Mathematical Biology Springer- Erez, D. ben-Avraham, and S. Havlin, ibid. 86, 3682 2001 ;
Verlag, Berlin, 1993 ; O. Diekmann and J. A. P. Heesterbeek, 85, 4626 2000 .
Mathematical Epidemiology of Infectious Diseases: Model 11 X. F. Wang and G. R. Chen, IEEE Trans. Circuits Syst., I:
Building, Analysis, and Interpretation Wiley, New York, Fundam. Theory Appl. 49, 54 2002 ; J. Jost and M. P. Joy,
2000 . Phys. Rev. E 65, 016201 2002 .
2 D. ben-Avraham and S. Havlin, Diffusion and Reactions in 12 R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86,
Fractals and Disordered Systems Cambridge University 3200 2001 ; Phys. Rev. E 63, 066117 2001 ; e-print
Press, Cambridge, 2000 . cond-mat/0202298.
3 M. E. J. Newman, e-print cond-mat/0201433; C. Moore and 13 P. Piot, M. Bartos, P. D. Ghys, N. Walker, and B. Schwart-
M. E. J. Newman, Phys. Rev. E 61, 5678 2000 ; M. Kuper- lander, Nature London 410, 968 2001 .
man and G. Abramson, Phys. Rev. Lett. 86, 2909 2001 ; P. 14 A. L. Lloyd and R. M. May, Science 292, 1316 2001 ; R. M.
Grassberger, Math. Biosci. 63, 157 1983 . May and A. L. Lloyd, Phys. Rev. E 64, 066112 2001 .
4 R. Albert and A. L. Barabási, Rev. Mod. Phys. 74, 47 2002 ; 15 A result similar to immunizing all nodes with degree k k0
S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51, 1079 i.e., ) and the 1 case was studied independently by
2002 ; A. L. Barabasi, Phys. World 33 July 2001 . Pastor-Satorras and Vespignani R. Pastor-Satorras and A.
5 M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Com- Vespignani, Phys. Rev. E 65, 036104 2002 , who considered
mun. Rev. 29, 251 1999 . the permanent immunization of a (1 1/ k) fraction of nodes
6 H. Ebel, L. I. Mielsh, and S. Bornholdt, e-print with k links, finding a finite epidemic threshold. Under perma-
cond-mat/0201476. nent immunization nodes offered the cure will be immune to
7 A. L. Barabási and R. Albert, Science 286, 509 1999 ; A. L. the virus, in contrast with the case studied here, in which cured
Barabási, R. Albert, and H. Jeong, Physica A 272, 173 1999 . nodes again become susceptible to the disease.
8 F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. 16 To generate the scale-free network, we start from a small num-
Aberg, Nature London 411, 907 2001 . ber of nodes (m0) and for each time step we add a new node to
9 P. Erdös and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 the network, with m links that are connected to an old node i
1960 ; B. Bollobás, Random Graphs Academic Press, Lon- with ki links according to the probability ki / kj. After iter-
j
don, 1985 . ating the system we obtain a network with connectivity distri-
10 R. Albert, H. Jeong, and A. L. Barabási, Nature London 406, bution P(k) k 3 and average connectivity k 2m 7 .
055103-4
Wyszukiwarka
Podobne podstrony:
What do you like doing in your free timemanaging in complex business networksQoS in Integrated 3G Networks Robert Lloyd EvansScale Free Heating Hydro Dynamics, Inc2008 06 Living Free Free Communications on the Freenet NetworkMalware in Popular Networksexploring the social ledger negative relationship and negative assymetry in social networks in organhao do they get there An examination of the antecedents of centrality in team networksNeural networks in non Euclidean metric spacestheory,empirisicm and parctice archeaeological discourses in a networ of dependency and oppositionModeling Virus Propagation in Peer to Peer NetworksE in T?atures & nescessity2007 01 Web Building the Aptana Free Developer Environment for AjaxFunctional Origins of Religious Concepts Ontological and Strategic Selection in Evolved MindsYou maybe in love Blue Cafewięcej podobnych podstron