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[]\
hl
zxcvbnm,./
~!@#$%^&*()_+
WERTYUIOP{}|
S
ZXCVBNM<>?
¸