Transcript Theorem 1.
Controlling the Spread of Viruses
on Power-Law Networks
Jennifer Tour Chayes
Joint work with N. Berger, C. Borgs, A. Ganesh, A. Saberi, D. B. Wilson
The Internet Graph
appears to have a power-law degree distribution
Faloutsos, Faloutsos and Faloutsos ‘99
The Sex Web and Other Social Networks
also appear to have a power-law degree distribution
Lilijeros et. al ‘01
Model for Power-Law Graphs:
Preferential Attachment
Add one vertex at a time
New vertex i attaches to m ¸ 1
existing vertices j chosen i.i.d. as
follows: With probability , choose j
uniformly and with probability 1- ,
choose j according to
Prob(i attaches to j) / dj
with dj = degree(j)
non-rigorous: Simon ‘55, Barabasi-Albert ‘99,
measurements: Kumar et. al. ‘00,
rigorous: Bollobas-Riordan ‘00, Bollobas et. al. ‘03
Computer Viruses and Worms
Viruses
are programs that
attach themselves to a host program
(executable)
cannot spread unless you run an infected
application or attachment
Worms
are programs that
break into your computer using some
vulnerability
do not require user actions to spread
Mutating Viruses and Worms
So
far, Internet viruses and worms have
been non-mutating
The next big threat is mutating viruses
and worms, e.g. a worm equipped with a
list of vulnerabilities that changes the
vulnerability exploited as a deterministic
or random function of time, or in
response to a command from a central
authority
Model for of Mutating Viruses & Worms:
Contact Process
Definition of model:
infected ! healthy at rate r
healthy ! infected at rate b (# infected nhbrs)
relevant parameter: l = b/r
Studied in probability theory, physics, epidemiology
Kephart and White ’93: modelling the spread of viruses
in a computer network
Epidemic Threshold(s)
l1
Infinite graph:
extinction
l2
weak
survival
strong
survival
Note: l1 = l2 on Zd
l1 < l2 on a tree
Finite subset
of Zd:
logarthmic
survival
time
polynomial exponential
survival (super-poly)
time
survival
time
The Internet Graph
What is the epidemic threshold of the Internet graph,
and is there a way of increasing the threshold, i.e.
controlling the spread of the epidemic?
Part I:
Epidemics of Mutating Viruses and Worms
Question:
What is the epidemic threshold of the
contact process on power-law graphs?
-- work in collaboration with Berger, Borgs & Saberi
(SODA ’05)
Epidemic Threshold in Scale-Free Network
In power-law networks both thresholds are
zero asymptotically almost surely, i.e.
l1 = l2 = 0 a.a.s.
Physics argument: Pastarros, Vespignani ‘01
Rigorous proof: Berger, Borgs, C., Saberi ’05
Moreover, we get detailed estimates (matching upper and
lower bounds) on the survival probability as a function of l
Theorem 1. For every l > 0, and for all n large enough, if
the infection starts from a uniformly random vertex in a
sample of the scale-free graph of size n, then with probability
0.1
2
n
1-O(l ), v is such that the infection survives longer than e
with probability at least
l
log (1/l)
C1 log log (1/l)
and with probability at most
l
log (1/l)
C2 log log (1/l)
where 0 < C1 < C2 < 1 are independent of l and n.
Typical versus average behavior
Notice that we left out O(l2 n) vertices in
Theorem 1.
Q: What are the effect of these vertices on the
average survival probability?
A: Dramatic.
Theorem 2. For every l > 0, and for all n large
enough, if the infection starts from a uniformly
random vertex in a sample of the scale-free graph
of size n, then the infection survives longer than
0.1
n
e with probability at least
lC3
and with probability at most
l
C4
where 0 < C3, C4 < 1 are independent of l and n.
Typical versus average behavior
The survival probability for an infection
starting from a typical (i.e., 1 – O(l2) )
vertex is
log (1/l)
(
l
log log (1/l)
)
The average survival probability is
l
(1)
Key Elements of the Proof:
1. For the contact process
If the maximum degree is much less than 1/l,
then the infection dies out very quickly.
On a vertex of degree much more than 1/l2,
the infection lives for a long time in the
neighborhood of the vertex (“star lemma”).
Star Lemma
If we start by infecting the center
of a star of degree k ,
with high probability,
the survival time is more than
Key Idea: The center infects a constant fraction
of vertices before being cured.
Key Elements of the Proof:
2. For preferential attachment graphs
Lemma: With high probability, the largest degree in
a ball of radius k about a vertex v is at most
(k!)10
and at least
(k!)(m,)
where (m,) > 0.
To prove this, we introduced a Polya Urn
Representation of the preferential attachment graph.
Polya Urn Representation of Graph
Polya’s Urn: At each time step,
add a ball to one of the urns with
probability proportional to the
number of balls already in that urn.
Polya’s Theorem: This is equivalent to choosing a
number p according to the b-distribution, and then
sending the balls i.i.d. with probability p to the left
urn and with probability 1– p to the right urn.
Use this and some work to show that the addition of a
new vertex can be represented by adding a new urn to
the existing sequence of urns and adding edges
between the new urn and m of the old ones.
“Proof” of Main Theorem:
Let
k=
log (1/l)
log log (1/l)
By the preferential attachment lemma, the
ball of radius C1k around vertex v contains a
vertex w of degree larger than
[(C1k)!] > l
v
w
-5
where the inequality follows by taking C1 large.
The infection must travel at most C1k to reach
w, which happens with probability at least
l
C1k
,
at which point, by the star lemma, the survival
time is more than exp(C l-3 ).
Iterate until we reach a vertex z of
sufficiently high degree for exp(n1/10) survival.
z
Iterations to get to
high-degree vertex
Summary of Part I:
Developed a new representation of the
preferential attachment model: Polya Urn
Representation.
Used the representation to:
1. prove that any virus with a positive rate of
spread has a positive probability of becoming
epidemic
2. calculate the survival probability for both
typical and average vertices
Part II:
Control of Mutating Viruses and Worms:
Question:
What is the best way to distribute antidote to
control the epidemic, i.e. to raise the
threshold of the contact process on powerlaw (and more general) graphs?
-- work in collaboration with Borgs, Ganesh, Saberi & Wilson ‘06
For l = b/r, previous results with r = const.:
Our results (BBCS) for growing power-law graphs
Ganesh, Massoulie, Towsley (GMT) for “configurational” power-law graphs
For
stars:
bc = rn-1/2 + o(1)
, amount of antidote R = nr required to
suppress epidemic is bn3/2 + o(1) , i.e.
superlinear in n
For
power-law graphs:
bc ! 0
, amount of antidote R required to suppress
epidemic is superlinear in n
Varying Recovery Rates r = rx
Assume there is a fixed amount of antidote R =
Sxrx to be distributed non-uniformly among the
sites, even depending on the current state of the
infection
Questions:
What is the best policy for distributing R?
Is there a way to control the infection (i.e., to
get lc > 0) on a star or power-law graph with R
scaling linearly in n?
Method 1: Contact Tracing
Contact tracing is a method in epidemiology to
diagnose and treat the contacts of infected individuals
, augmenting the cure rate of neighbors of infected
nodes , cure / infected degree
Theorem 1: Let rx = r + r0ix where ix is the number of
infected neighbors of x. Then the critical infection rate
on the star is
bc = rn-1/3 + o(1) ! 0.
Note: This is an improvement from the case r = const,
where bc = rn-1/2 + o(1), but this still gives bc ! 0, or
alternatively, it takes R = n4/3 + o(1) , i.e. a superlinear
amount, of antidote to control the virus.
Method 2: Cure / Degree
(vs. contact tracing with cure / infected degree)
Theorem 2: Let rx = dx. If b < 1 then the
expected survival time is t = O(logn).
Corollary: For graphs with a bounded average
degree davg, the total amount of antidote needed
to control the epidemic is bdavgn, i.e. linear in n.
Thus, curing proportional to degree is enough
to control epidemics on power-law graphs.
Q: Can we do significantly better?
I.e., can we get bc! 1 as n ! 1 ?
A: No, for expanders. (Recall a graph G = (V,E)
is an (,h)-expander if for each subset W of V of
size at most |V|, the number of edges joining W
to its complement V\W is at least h|W|.)
Condition* (for comparison): Let Xt be the set of
infected vertices at time t, and let rx = rx (Xt,t) be
an arbitrary non-uniform allocation of antidote
obeying the condition that the sum of rx over any
subset of V is less than the sum of the degrees over
that subset.
Expanders, continued:
Theorem 3: Let e > 0, and let Gn be a
sequence of (,h)-expanders on n nodes. Let
rx (Xt,t) obey Condition*. If b ¸
(1+e)davg/(h), then t ¸ exp((nlogn)).
Corollary: For expanders, innoculating
according to degree is a constant-factor
competitive innoculation scheme.
Summary of Part II:
Contact tracing does not control the epidemic in
the sense that it still gives bc = 0 on a star.
On general graphs, curing proportional to degree
does control the epidemic in the sense that it gives
bc > 0.
For expanders with bounded average degree, no
other (inhomogenous, configuration-dependent,
time-dependent) innoculation scheme works more
than a constant factor better than curing
proportional to degree in the sense that any such
scheme gives bc < 1 as n ! 1.
Overall Summary
Mutating viruses and worms with any positive
rate of transmission to neighbors become
epidemic with positive probability.
These epidemics can be controlled with
(1)n doses of antidote if the antidote is
distributed proportionally to the degree of
the nodes.
THE END
1234567890-=
!@#$%^&*()_+
Qwertyuiop[]\
QWERTYUIOP{}|
Asdfghjkl;’
ASDFGHJKL:”
Zxcvbnm,./
ZXCVBNM<>?
`1234567890-=
qwertyuiop[]\
hl
zxcvbnm,./
~!@#$%^&*()_+
WERTYUIOP{}|
S
ZXCVBNM<>?
¸