Epidemic Spreading in Real Networks:An Eigenvalue Viewpoint Yang Wang,Deepayan Chakrabarti,Chenxi Wang∗,Christos Faloutsos†
Carnegie Mellon University
5000Forbes Avenue,Pittsburgh,PA,15213
yangwang,deepayan,chenxi,u.edu
Abstract
How will a virus propagate in a real network? Does an epidemic threshold exist for afinite power-law graph,or anyfinite graph?How long does it take to disinfect a network given particular values of infection rate and virus death rate?
We answer thefirst question by providing equa-tions that accurately model virus propagation in any network including real and synthesized network graphs.We propo a general epidemic thresh-old condition that applies to arbitrary graphs:we prove that,under reasonable approximations,the epidemic threshold for a network is cloly related to the largest eigenvalue of its adjacency matrix. Finally,for the last question,we show that infec-tions tend to zero exponentially below the epidemic th
reshold.
We show that our epidemic threshold model subsumes many known thresholds for special-ca ,Erd¨o s-R´e nyi,BA power-law,homoge-neous);we show that the threshold tends to zero for infinite power-law graphs.Finally,we illustrate the predictive power of our model with extensive experi-ments on real and synthesized graphs.We show that our threshold condition holds for arbitrary graphs.
∗This work is partially supported by the National Science Foundation under Grant No.CCR-0208853and a grant from NIST.
†This work is partially supported by the National Science Foundation under Grants No.IIS-9817496,IIS-9988876,IIS-0083148,IIS-0113089,IIS-0209107IIS-0205224by the Penn-sylvania Infrastructure Technology Alliance(PITA)Grant No.22-901-0001,and by the Defen Advanced Rearch Projects Agency under Contract No.N66001-00-1-8936.1.Introduction
Computer virus remain a significant threat to today’s networks and systems.Existing defen mechanisms typically focus on local scanning of virus signatures.While the mechanisms can de-tect and prevent the spreading of known virus, they do little for globally optimal defens.The rece
nt proliferation of malicious code that spreads with virus code exacerbates the problem[10,24,25]. From a network dependability standpoint,the prop-agation of malicious code reprents a particular form of fault propagation,which may lead to the ul-timate demi of the network(consider distributed denial-of-rvice attacks).With the exception of a few specialized modeling studies[7,8,16,19,26], much still remains unknown about the propagation characteristics of computer virus and the factors that influence them.
In this paper,we investigate epidemiological modeling techniques to reason about computer vi-ral propagation.Kephart and White[7,8]are among thefirst to propo epidemiology-bad an-alytic models.Their studies,however,are bad on topologies that do not reprent modern net-works.Staniford et al.[23]reported a study of the Code Red worm propagation,but did not attempt to create an analytic model.The more recent stud-ies by Pastor-Satorras et al.[16,17,18,19,20]and Barab´a si et al.[2,4]focud on epidemic models for power-law networks.现代言情小说
This work aims to develop a general analytic model of virus propagation.Specifically,we are in-terested in models that capture the impact of the underlying topology but are not limited by it.We found that,contrary to prior beliefs,viral propaga-tion is largely determined by intrinsic characteris-tics of the network.Our model holds for arbitrary graphs and renders surprisingly simple but accurate pre
dictions.
The layout of this paper is as follows:ction2 gives a background review of previous models.In ction3,we describe our propod model.We show that our model conforms better to simulation results than previous models over real networks.In ction4,we revisit the issue of epidemic threshold and prent a new theory for arbitrary graphs—the epidemic threshold of a given network is related in-trinsically to thefirst eigenvalue of its adjacency matrix.We summarize in ction6.
2.Earlier models and their limitations
The class of epidemiological models that is most widely ud is the so-called homogeneous mod-els[1,11].A homogeneous model assumes that every individual has equal contact to everyone el in the population,and that the rate of infection is largely determined by the density of the infected population.Kephart and White adopted a mod-ified homogeneous model in which the communi-cation among individuals is modeled as a directed graph[7]:a directed edge from node i to node j denotes that i can directly infect j.A rate of in-fection,called the birth rate,β,is associated with each edge.A virus curing rate,δ,is associated with each infected node.
If we denote the infected population at time t asηt,a deterministic time evolution ofηt in the Kephart-
White model(hereafter referred to as the KW model)can be reprented as
dηt
=β k ηt(1−ηt)−δηt(1) where k is the average connectivity.The steady state solution for Equation1isη=1−δ/(β k )∗N, where N is the total number of nodes.
An important prediction of Equation1is the no-tion of epidemic threshold.An epidemic threshold,τ,is the criticalβ/δratio beyond which epidemics ensue.In a homogeneous or Erd¨o s-R´e nyi network, the epidemic threshold is,
τhom=
1
k (2)
where k is the average connectivity[7].
The earlier models provide a good approxima-tion of virus propagation in networks where the cont
act among individuals is sufficiently homoge-neous.However,there is overwhelming evidence that real networks(including social networks[21], router and AS networks[6],and Gnutella overlay graphs[22])deviate from such homogeneity—they follow a power law structure instead.Computer
virus,therefore,are likely to propagate among
nodes with a high variance in connectivity.
Pastor-Satorras and Vespignani studied epidemic
spread for power-law networks where the connec-
tivity distribution is characterized as P(k)=k−γ(P(k)is the probability that a node has k links)
[14,16,18,19].Power-law networks have a highly
skewed connectivity distribution and for certain val-
ues ofγremble the Internet topology[6].Pastor-
Satorras et al.developed an analytic model(we
refer to their model as the SV model)for the
Barab´a si-Albert(BA)power-law topology(γ=3).工作概况
Their steady state prediction is,
η=2e−δ/mβ(3)
where m is the minimum connection in the net-work.The SV model,however,depends critically on the assumptionγ=3,which does not hold for real networks[9,6].This model yields less than accurate predictions for networks that deviate from the BA topology,as we will show later in the pa-per.Pastor-Satorras et al.[18]also propod an epidemic threshold condition
τSV= k (4)
where k is the expected connectivity and k2 sig-nifies the connectivity divergence.
Following[19],Bogu˜n´a and Satorras studied epi-demic spreading in correlated networks where the connectivity of a node is related to the connectiv-ity of its neighbors[3].The correlated networks include Markovian networks where,in addition to P(k),a function P(k|k )determines the probability that a node of degree k is connected to a node of degree k .山七镇
While some degree of correlations may exist in real networks,it is often difficult to character-ize connectivity correlations with a simple P(k|k ) function.Indeed,prior studies on real networks [6,15]have not found any conclusive evidence to support the type of correlation as defined in[3]. Hence,we will not discuss models for correlated networks further in this paper.
We prent a new analytic model that does not assume any particular propagation topology.We will show later that our model subsumes previous models that are tailored tofit special-ca graphs (homogeneous,BA power-law,etc.).
3.The propod model
In this ction,we describe a model that does not assume homogeneous connectivity or any par-ticular topology.We assume a connected network G=(N,E),where N is the number of nodes in the network and E is the t of edges.We assume a universal infection rateβfor each edge connected to an infected node,and a virus death rateδfor each infected node.Table1lists the symbols ud.βVirus birth rate on a link connected
to an infected node
δVirus curing rate on an infected node
t Time stamp
p i,t Probability that node i is infected at t
ζi,t Probability that node i does not
receive infections from its neighbors at t ηt Infected population at time t
k Average degree of nodes in a network k2 Connectivity divergence
Table1.Table of Symbols
3.1.Model
Our model assumes discrete time.During each time interval,an infected node i tries to infect its neighbors with probabilityβ.At the same time, i may be cured with probabilityδ.We denote the probability that a node i is infected at time t as p i,t. We defineζi,t,the probability that a node i will not receive infections from its neighbors at time t as,ζi,t= j:neighbor of i(p j,t−1(1−β)+(1−p j,t−1))
= j:neighbor of i(1−β∗p j,t−1)(5) We assume that a node i is healthy at time t if
•i was healthy before t and did not receive in-fections from its neighbors at t(defined byζi,t) OR
•i was infected before t,cured at t and did not receive infections from its neighbors(defined byζi,t)OR
•i was infected before t,received and ignored infections from its neighbors,and was sub-quently cured at t Note that the third bullet above is due to poten-tially concurrent curing and infection events.
We subquently define the healthy probability of a node i at time t,1−p i,t,to be
1−p i,t=(1−p i,t−1)ζi,t+δp i,t−1ζi,t
+
1
2
δp i,t−1(1−ζi,t)N(6) Note that for the last term on the right hand side of Equation6we assume that the probability that a curing event at node i takes place after infection from neighbors is roughly50%.
Given a network topology and particular values ofβandδ,we can solve Equation6numerically and obtain the time evolution of infected population,ηt, whereηt= N i=1p i,t.
3.2.Experiments
In this ction,we prent a t of simulation results.The simulations are conducted to answer the question—how does our model perform in real, BA power law,and homogeneous graphs?We u a real network graph collected at the Oregon router views1.This datat contains31180links among 10900AS peers.All synthesized power-law graphs ud in this study are generated using BRITE[12]. Unless otherwi specified,each simulation plot is averaged over15individual runs.
We begin each simulation with a t of randomly chon infected nodes on a given network topology2. Simulation proceeds in steps of one time unit.Dur-ing each step,an infected node attempts to infect each of its neighbors with probabilityβ.In addi-tion,every infected node is cured with probability δ.An infection attempt on an already infected node has no effect.
Figure1shows the time evolution ofηas pre-dicted by our model(e Equation6)on the10900-node Oregon AS graph,plotted against simulation results and the steady state prediction of the SV model in Equation3(Since the SV model does not estimate the transients,we plot the steady state only.)As s
hown,our model yields a strictly more preci result than the SV model.
Figure2compares the predictions of our model against the SV model for Barab´a si-Albert networks (e Equation3).The topology ud in Figure2is a synthesized1000-node BA network.Since the SV
2The number of initially-infected nodes does not affect the equilibrium of the propagation.It is chon bad on the particular values ofβandδfor each run
(a)(b)
Figure1.Experiments show the time evolution of infection in an10900-node power-law network. Both simulations were performed on an Oregon network graph,with k =5.72andβ=0.14.In both cas,our model conforms much clor to the simulation results than the SV model.
model(e Equation3)is specifically tailored for BA networks,we expect the comparison to be sim-ply a sanity check.As shown,both models conform nicely to the simulation results,though our model appears to be slightly more
preci.
Figure 2.Experiments on BA topology:
shows time evolution of infected popula-
tion in a1000-node power-law network.
Our model outperforms the SV model in
its steady state prediction.
Figure3shows simulation results of epidemic spreading on a synthesized1000-node random net-work,plotted against the KW model[7]and our model.The network is constructed according to the Erd断机杼怎么读
¨o s-R´e nyi model[5].Since an Erd¨o s-R´e nyi network is sufficiently clo to being homogeneous as far as epidemiological models are concerned,the results in Figure3suggest that our model is as pre-ci as the KW model,which is designed specifically for homogeneous networks.In one ca whereβis 0.2andδis0.72,the simulated spreading appears to follow our prediction more cloly than that of the KW庐山古诗
锦鲤购买model.
Figure 3.Experiments on ER topology:
shows time evolution of infected popu-
lation in a1000-node random Erd¨os net-
work.Our model generally yields similar
predictions to the KW model,but outper-
forms it whenδis high.
The experiments we show here,conducted on a real network,a synthesized BA power-law network, and an Erd¨o s-R´e nyi network,illustrate the predic-tive power of our model—as a general model,it sub-sumes prior models and produces predictions that equal or outperform predictions that target specific topologies.
4.Epidemic threshold and eigenvalues
As described previously,an epidemic threshold
is a critical state beyond which infections become
endemic.Predicting the epidemic threshold is an
important part of an epidemiological model.The
epidemic threshold of a graph depends fundamen-
tally on the graph itlf.The challenge therefore is
to capture the esnce of the graph in as few param-
eters as possible.We prent one such model here
that predicts the epidemic threshold with a single
parameter—the largest eigenvalue of the adjacency
matrix of the graph—for arbitrary graphs.
We note that previous models have derived
threshold conditions for special-ca graphs.For in-
stance,the epidemic threshold for a homogeneous
network is the inver of the average connectivity,
k .Similarly,the threshold for infinite power-law networks is zero.However,a unifying model for
arbitrary,real graphs has not appeared in the lit-
erature.The clost model thus far is the one put
forth by Pastor-Satorras et al.(e Equation4).
We show later that their model is not accurate for
arbitrary graphs.
In this ction,we describe a general theory for
河长制工作epidemic threshold that holds for arbitrary graphs.
We obrve that the epidemic threshold is a con-
dition linking the virus’birth and curing rate to
the adjacency matrix of the graph,such that an in-
fection becomes an epidemic if the condition holds,
and dies out if it does not.Our theory is surpris-
ingly simple yet accurate at the same time.We
南韩是哪个国家
show later in this ction that this new threshold
condition subsumes prior models for special-ca
graphs.Table2lists the symbols ud in this c-
tion.
A Adjacency matrix of the network
tr A The transpo of matrix A
λi,A The i-th largest eigenvalue of A
u i,A Eigenvector of A corresponding toλi,A S The‘system’matrix describing the
equations of infection
λi,S The i-th largest eigenvalue of S
Table2.Symbols for eigenvalue analysis
Next,we will show that our estimate for the epi-
demic thresholdτis
τ=1
λ1,A
(7) whereλ1,A is the largest eigenvalue of the adjacency matrix A of the network.
Theorem1(Epidemic Threshold)If an epi-demic dies out,then it is necessarily true that β
δ
<τ=1
λ1,A
,whereβis the birth rate,δis the curing rate andλ1,A is the largest eigenvalue of the adjacency matrix A.
Proof:Restating Equation6,
1−p i,t=(1−p i,t−1)ζi,t+δp i,t−1ζi,t
+
1
2
δp i,t−1(1−ζi,t)N Rearranging the terms,
1−p i,t=
1
2
δp i,t−1+ 1+ 12δ−1 p i,t−1 ζi,t =
1
δp i,t−1+1+ 1δ−1 p i,t−1
−β j p j,t−1
=1+δp i,t−1−p i,t−1−β j p j,t−1(8) This us the approximation
(1−a)(1−b)≈1−a−b(9) when a 1,b 1.
We thus have
so,p i,t=(1−δ)p i,t−1+β j p j,t−1(10)
Converting Equation10to matrix notation(P t is the column vector(p1,t,p2,t,...,p N,t)),
P t=((1−δ)I+βA)P t−1(11) Thus,P t is of the form
P t=SP t−1(12)
=S t P0(13) where S=(1−δ)I+βA.We call S the system matrix.
As we show in Lemma1in the Appendix,the matrices A and S have the same eigenvectors u i,S, and their eigenvalues,λi,A andλi,S,are cloly re-lated:
λi,S=1−δ+βλi,A∀i(14) Using the spectral decomposition,we can say
S= iλi,S u i,S tr(u i,S) and,S t= iλt i,S u i,S tr(u i,S)(15)
Using this in Equation13,
P t= iλt i,S u i,S tr(u i,S)P0(16)
Without loss of generality,order the eigenvalues such thatλ1,A≥λFor an infection to die offand not become an epidemic,the vector P t should go to zero for large t,which happens when∀i,λt i,S tends to0.That impliesλ1,S<1.So,
1−δ+βλ1,A<1(17)
which means that,τ=1
λ1,A
2 Theorem2(Exponential Decay)When an
epidemic is diminishing(thereforeβ/δ<1
1,A ),the
probability of infection decays exponentially over time.
Proof:We have:
P t=S t P0(from Equation13)
≈ iλt i,S u i,S tr(u i,S)P0(from Equation15)≈λt1,S∗C(18) where C is a constant vector.Since the value of λ1,S is less than1(becau of the no-epidemic con-dition).the values of p i,t are decreasing exponen-tially over time.2 Corollary1When the network is below the epi-demic threshold,the number of infected nodes de-cays exponentially over time.
Proof:Let n t denote the number of infected nodes at time t.
n t=
N i=1p i,t
= iλt1,S∗C i
=λt1,S∗ i C i
where C i are the individual elements of the matrix C in Equation18above.Becau i C i is a con-stant andλ1,S<1(from Theorem1),we e that n t decays exponentially with time.2.
The exponential decay in the number of infected nodes is shown clearly in Figure4,where we plot the logarithm of the number of infected nodes,ηt, versus t.Two plots are shown:One for the star topology,and one for the Oregon datat.In both cas,we obrve that for large values of time t,the plots become linear,implying that the number of infected nodes decays exponentially.5.Discussion—generality of our
threshold condition
We now turn to show that our threshold condi-tion is general and holds for other graphs.In par-ticular,
we show that the threshold condition holds for a)homogeneous,b)star,c)infinite power-law, and d)finite power-law graphs.We do that with the following corollaries.
Corollary2The new threshold model holds for homogeneous or random Erd¨o s-R´e nyi graphs. Proof:As reported previously,the epidemic threshold in a homogeneous network or a random Erd¨o s-R´e nyi graph isτhom=1/ k where k is the average connectivity[7].It is easily shown that, in a homogeneous or random network,the largest eigenvalue of the adjacency matrix is k .There-fore,our model yields the same threshold condition as the homogeneous models[11].2 Corollary3The epidemic threshold,τ(as defined in ction2),for a star topology is exactly1√
d
, where
√is the square root of the degree of the central node.
Proof:In a star topology,we have two types of nodes,the center node and the satellite nodes.Sup-po that we have d satellites,thefirst eigenvalue of the adjacency matrix,λ1,is
√d.The stability condition then becomes
λ1=1−δ+β∗
√d=1(19) which means thatδ=β∗
√d to achieve stability, thus renderingτ=1√.2 Figure5shows an infection spread over time in a100-node star graph withβ=0.016.Givenτ= 1/
√99,the criticalδon the threshold is0.16.We plotted our propagation model as given by Equa-tion6in Figure5(b).As shown,the propagation model confirms our prediction for the criticalδ. More specifically,the theoretical results rendered by the propagation model cloly reflect the simu-lation whenδ>0.16.Forδ<0.16,there is no epidemic.Forδ=0.16,a very interesting tting appears.
For the ca ofδ=0.16,our propagation model ems to show that the expected number of infected nodesηt drops approximately at the rate of t−1, which is qualitatively different from the other two cas:forδ>0.16,ηt≈λt1;forδ<0.16,ηt stabi-lizes.This suggests a pha transition phenomenon.
