3 - Elsevier
Download
Report
Transcript 3 - Elsevier
Propagation in Networks
Propagation in Networks
500 randomly chosen users
500 most active users
Day 8
1
2
3
4
5
6
7
“Network Science: Applications to Global Communications”, Albert-Laszlo Barabasi
Day 8
1
2
3
4
5
6
7
Firefighter Problem
A simple network - a grid where each intersection point is a
node.
1.
Fire starts at one point
2.
1 Firefighter can be deployed to protect a point at each
time step
3.
Fire spreads to all unprotected adjacent vertices in the
next time step.
4.
Repeat
3
4
5
6
7
8
9
Firefighter Problem Strategies
Repeat the example exercise with different
firefighter placement
How much of the network can you protect?
Disease Models
S – Susceptible
I – Infectious
R – Recovered / removed
E – Exposed
Disease Models
SI
Susceptible, and once you catch the disease, you
remain infectious for the rest of your life.
HIV, Herpes
SIR
Susceptible, and then you catch the disease. You are
infectious for a while, but once recovered, you
cannot catch the disease again.
Mono, Chicken Pox
Disease Models
SIRS / SIS
A susceptible person gets sick and is infectious. After
recovering (and possibly enjoying a period of temporary
immunity, indicated by R), the person is susceptible to the
infection again.
Strep throat
SEIR
After becoming infected, the person has a period where
they are not contagious. This period of exposure is
indicated with “E”
Incorporates exposed but non infectious period
How Diseases Track Information
Same models that describe disease spread describe the
spread of rumors, fads, links, etc. in social media.
Discuss
How do S/I/R models apply here.
What does it mean to be susceptible?
What does it mean to be infectious?
What does it mean to be recovered?
What does it mean if you have an SIRS model and go
from recovered to susceptible again?
k-threshold Models
Disease is transmitted if k adjacent nodes are
infected.
1-threshold
C is infected if either A or B is infected
A
C
B
k-threshold Models
2-threshold
C is infected only if 2 neighbors (both A and B) are
infected
A
C
B
Application to Information - Discuss
How do k-thresholds work for information
spreading?
What does it mean to have a 2-threshold?
How can you use this to build strategies?
Apply S/I/R Models and k-thresholds
Exercise
The disease will spread. Then, you can immunize uninfected
nodes. Repeat. Assume a 1-threshold SI model
How many nodes do you immunize and how many are
saved?
1.
You may immunize 1 node at each time period. Disease starts at YY.
Bonus for protecting OO and DD.
2.
You may immunize 1 node at each time period. Disease starts at both OO
and NN.
3.
You may immunize 2 nodes at each time period. Disease starts at B
DD
M
EE
5
FF
CC
L
6
E
F
GG
3
K
A
B
Y
YY
II
Q
S
P
NN
VV
KK
VV
MM
WW
LL
T
V
W
C
OO
X
R
ZZ
JJ
U
N
O
2
HH
Z
I
1
D
AA
I
8
4
BB
J
7
PP
G
RR
QQ
TT
SS
UU
H
Exercise
Now assume a 2-threshold model
How many nodes do you immunize and how many
are saved?
1.
You may immunize 1 node at each time period. Disease
starts a both OO and NN.
2.
You may immunize 2 nodes at each time period. Disease
starts at OO and NN.
Exercise
Assume someone can immunize 2 people in each
round.
Assume a 1-threshold model
You can start the disease in 2 places. Choose them to
cause the largest possible spread.
Assume a 2-threshold model
You can start the disease in 2 places. Choose them to
cause the largest possible spread.
Exercise
Repeat all exercises for
SIR model (once recovered, the node is immune)
SIS model (node is infected for 1 step, then
uninfected but susceptible again)
SIRS model (node is infected for 1 step, then
immune for 1 step, then susceptible again)