Transcript Homeland Security What Can Mathematics Do? - dimacs

Homeland Security
What Can
Mathematics Do?
Fred Roberts
Chair, Rutgers University
Homeland Security Research
Initiative
Director, DIMACS Center 1
Dealing with terrorism requires detailed
planning of preventive measures and
responses.
Both require precise reasoning and extensive
analysis.
2
Experimentation or field trials are often
prohibitively expensive or unethical and do not
always lead to fundamental understanding.
Therefore, mathematical modeling becomes
an important experimental and analytical tool.
3
Mathematical models have become important
tools in preparing plans for defense against
terrorist attacks, especially when combined
with powerful, modern computer methods for
analyzing and/or simulating the models.
4
What Can Math Models Do For
Us?
5
What Can Math Models Do For
Us?
•Sharpen our understanding of fundamental
processes
•Compare alternative policies and
interventions
•Help make decisions.
•Prepare responses to terrorist attacks.
•Provide a guide for training exercises and
scenario development.
•Guide risk assessment.
•Predict future trends.
6
OUTLINE
• Examples of Homeland Security Research
at Rutgers that Use Mathematics
• Examples of Research Projects I am
Involved in
• One Example in Detail
7
OUTLINE
• Examples of Homeland Security Research
at Rutgers that Use Mathematics
• Examples of Research Projects I am Involved
in
• One Example in Detail
8
TRANSPORTATION AND BORDER
SECURITY
Pattern recognition for
machine-assisted
baggage searches
The Math: Linear
algebra: “Pattern” defined
as a vector
Border security: decision
support software
The Math: Computer
models
9
TRANSPORTATION AND BORDER
SECURITY
Statistical analysis of
flight/aircraft
inspections
The Math: Statistics
Port-of-entry
inspection algorithms
The Math: Statistics +
“combinatorial
optimization”
10
TRANSPORTATION AND BORDER
SECURITY
Vessel tracking for
homeland defense
The Math:
geometry + calculus
11
COMMUNICATION SECURITY
Resource-efficient security
protocols for providing data
confidentiality and
authentication in cellular, ad
hoc, and wireless local area
networks
The Math:
Network Analysis
Number theory: Cryptography
12
COMMUNICATION SECURITY
Exploiting analogies between
computer viruses and biological
viruses
The Math: Differential
equations, dynamical systems
13
COMMUNICATION SECURITY
Information privacy:
–Identity theft
–Privacy of health care
data
The Math:
Number theory
(cryptography),
Statistics
14
FOOD AND WATER SUPPLY SECURITY
Using economic weapons to
protect against agroterrorism
The Math:
“Game Theory”
Optimization
15
SURVEILLANCE/DETECTION
Detecting a
bioterrorist attack using
“syndromic surveillance”
The Math:
Statistics, Data Mining,
Discrete Math
Anthrax bacillus
16
SURVEILLANCE/DETECTION
Weapons detection
and identification (dirty
bombs, plastic
explosives)
The Math:
Linear algebra,
Statistics,
“Data Mining” (computer
science)
17
SURVEILLANCE/DETECTION
Biometrics
–Face, gait, voice, iris
recognition
–Non-verbal behavior
detection (lying or telling
the truth?) (applications to
interrogation)
The Math:
Optimization, linear
algebra, statistics
18
RESPONDING TO AN
ATTACK
Exposure/Toxicology
–Modeling dose
received
–Rapid risk and
exposure
characterization
The Math:
Differential Equations,
Probability
19
RESPONDING TO AN ATTACK
Simulating
evacuation of
complex
transportation
facilities
The Math:
Computer
simulation
20
RESPONDING TO AN ATTACK
Emergency Communications
–Rapid networking at
emergency locations
–Rapid “telecollaboration”
The Math:
discrete math, network
analysis
21
OUTLINE
• Examples of Homeland Security Research
at Rutgers that Use Mathematics
• Examples of Research Projects I am
Involved in
• One Example in Detail
22
The Bioterrorism Sensor
Location Problem
23
• Early warning is
critical
• This is a crucial
factor underlying
government’s plans
to place networks of
sensors/detectors to
warn of a bioterrorist
attack
The BASIS System
24
Two Fundamental Problems
• Sensor Location
Problem (SLP):
– Choose an
appropriate mix of
sensors
– decide where to
locate them for
best protection and
early warning
25
Two Fundamental Problems
• Pattern Interpretation
Problem (PIP): When
sensors set off an
alarm, help public
health decision makers
decide
– Has an attack taken
place?
– What additional
monitoring is needed?
– What was its extent and
location?
– What is an appropriate
response?
26
The Sensor Location Problem:
Algorithmic Tools
27
Algorithmic Approaches I :
Greedy Algorithms
28
Greedy Algorithms
• Find the most important location first and locate
a sensor there.
• Find second-most important location.
• Etc.
• Builds on earlier work at Institute for Defense
Analyses (Grotte, Platt)
• “Steepest ascent approach.’’
• No guarantee of optimality.
• In practice, gets pretty close to optimal solution.
29
Algorithmic Approaches II :
Variants of Classic Facility
Location Theory Methods
30
Location Theory
• Where to locate facilities to best serve “users”
• Often deal with a network with vertices, edges,
and distances along edges
• Users u1, u2, …, un located at vertices
• One approach: locate the facility at vertex x
chosen so that n
 d ( x, u )
i
i 1
is minimized.
31
Location Theory
f
1
a
1
1
e
b
1
1
1’s represent
distances along
edges
d
1
c
32
1
f
1
a
1
u1
e
b
u2
1
1
d
1
c
x=a: d(x,ui)=1+1+2=4
u3
x=b: d(x,ui)=2+0+1=3
x=c: d(x,ui)=3+1+0=4
x=d: d(x,ui)=2+2+1=5
x=e: d(x,ui)=1+3+2=6
x=f: d(x,ui)=0+2+3=5
x=b is optimal
33
Algorithmic Approaches II :
Variants of Classic Location
Theory Methods: Complications
• We don’t have a network with vertices and edges;
we have points in a city
• Sensors can only be at certain locations (size,
weight, power source, hiding place)
• We need to place more than one sensor
• Instead of “users,” we have places where potential
attacks take place.
• Potential attacks take place with certain
probabilities.
• Wind, buildings, mountains, etc. add
34
complications.
The Pattern Interpretation
Problem
35
The Pattern Interpretation
Problem
• It will be up to the
Decision Maker to
decide how to
respond to an
alarm from the
sensor network.
36
Approaching the PIP: Minimizing
False Alarms
37
Approaching the PIP: Minimizing
False Alarms
• One approach:
Redundancy. Require
two or more sensors to
make a detection
before an alarm is
considered confirmed
• Require same sensor
to register two alarms:
Portal Shield requires
two positives for the
same agent during a
specific time period.
38
Approaching the PIP: Minimizing
False Alarms
• Redundancy II: Place two or more
sensors at or near the same location.
Require two proximate sensors to give off
an alarm before we consider it confirmed.
• Redundancy drawbacks: cost, delay in
confirming an alarm.
39
Approaching the PIP: Using
Decision Rules
• Existing sensors
come with a
sensitivity level
specified and
sound an alarm
when the number
of particles
collected is
sufficiently high –
above threshold.
40
Approaching the PIP: Using
Decision Rules
• Let f(x) = number of particles collected at sensor x
in the past 24 hours. Sound an alarm if f(x) > T.
• Alternative decision rule: alarm if two sensors
reach 90% of threshold, three reach 75% of
threshold, etc.
Alarm if:
f(x) > T for some x,
or if f(x1) > .9T and f(x2) > .9T for some x1,x2,
or if f(x1) > .75T and f(x2) > .75T and f(x3) > .75T
for some x1,x2,x3.
41
Monitoring
Message Streams:
Algorithmic
Methods for
Automatic
Processing of
Messages
42
Objective:
Monitor huge communication streams, in particular,
streams of textualized communication, to
automatically detect pattern changes and
"significant" events
Motivation: monitoring
email traffic, news,
communiques, faxes,
voice intercepts (with
speech recogntion)
43
Technical Approaches:
• Given stream of text in any language.
• Decide whether "events" are present in the flow
of messages.
• Event: new topic or topic with unusual level of
activity.
• Initial Problem: Retrospective or “Supervised”
Event Identification: Classification into preexisting classes. Given example messages on
events/topics of interest, algorithm detects
44
instances in the stream.
More Complex Problem: Prospective
Detection or “Unsupervised”
Filtering
• Classes change - new classes or change
meaning
• A difficult problem in statistics
• Recent new C.S. approaches
“Semi-supervised Learning”:
• Algorithm suggests a possible new
event/topic
• Human analyst labels it; determines its
significance
45
The Approach: “Bag of Words”
• List all the words of interest
that may arise in the
messages being studied:
w1, w2,…,wn
• Bag of words vector b has
k as the ith entry if word wi
appears k times in the
message.
• Sometimes, use “bag of
bits”: Vector of 0’s and 1’s;
count 1 if word wi appears in
the message, 0 otherwise.
46
The Approach: “Bag of Words”
• Key idea: how close are two such vectors?
• Known messages have been classified
into different groups: group 1, group 2, …
• A message comes in. Which group should
we put it in? Or is it “new”?
• You look at the bag of words vector
associated with the incoming message
and see if “fits” closely to typical vectors
associated with a given group.
47
The Approach: “Bag of Words”
• Your performance can improve over time.
• You “learn” how to classify better.
• Typically you do this “automatically” and
try to program a machine to “learn” from
past data.
48
“Bag of Words” Example
Words:
w1 = bomb, w2 = attack, w3 = strike
w4 = train, w5 = plane, w6 = subway
w7 = New York, w8 = Los Angeles, w9 =
Madrid, w10 = Tokyo, w11 = London
w12 = January, w13 = March
49
“Bag of Words”
Message 1:
Strike Madrid trains on March 1.
Strike Tokyo subway on March 2.
Strike New York trains on March 11.
Bag of words b1 = (0,0,3,2,0,1,1,0,1,1,0,0,3)
w1 = bomb, w2 = attack, w3 = strike
w4 = train, w5 = plane, w6 = subway
w7 = New York, w8 = Los Angeles, w9 =
Madrid, w10 = Tokyo, w11 = London
50
w12 = January, w13 = March
“Bag of Words”
Message 2:
Bomb Madrid trains on March 1.
Attack Tokyo subway on March 2.
Strike New York trains on March 11.
Bag of words b2 = (1,1,1,2,0,1,1,0,1,1,0,0,3)
w1 = bomb, w2 = attack, w3 = strike
w4 = train, w5 = plane, w6 = subway
w7 = New York, w8 = Los Angeles, w9 =
Madrid, w10 = Tokyo, w11 = London
51
w12 = January, w13 = March
“Bag of Words”
Note that b1 and b2 are “close”
b1 = (0,0,3,2,0,1,1,0,1,1,0,0,3)
b2 = (1,1,1,2,0,1,1,0,1,1,0,0,3)
Close could be measured using distance d(b1,b2)
= number of places where b1,b2 differ
(“Hamming distance” between vectors).
Here: d(b1,b2) = 3
The messages are “similar” – could belong to the
same ”class” of message.
52
“Bag of Words”
Message 3:
Go on on strike against Madrid trains on March
1.
Go on strike against Tokyo subway on March 2.
Go on strike against New York trains on March
11.
Bag of words b3 = same as b1.
BUT: message 3 is quite different from message 1.
Shows trickiness of problem. Maybe missing some
key words like “go” or maybe we should use pairs
53
of words like “on strike” (“bigrams”)
Streaming Data
• We often have just one shot at the data as it
comes “streaming by” because there is so much
of it. This calls for powerful new algorithms.
54
OUTLINE
• Examples of Homeland Security Research
at Rutgers that Use Mathematics
• Examples of Research Projects I am
Involved in
• One Example in Detail
55
Mathematics and Bioterrorism:
Graph-theoretical Models of
Spread and Control of Disease
56
Mathematics and Bioterrorism:
Graph-theoretical Models of
Spread and Control of Disease
Warning: Next
Few Slides
Contain
Graphic
Material
57
Great concern about the deliberate
introduction of diseases by bioterrorists has
led to new challenges for mathematical
scientists.
smallpox
58
I got involved right after September 11 and the
anthrax attacks.
anthrax
59
Bioterrorism issues are typical of many
homeland security issues.
The rest of this talk will emphasize
bioterrorism, but many of the “messages”
apply to homeland security in general.
Waiting on line
to get smallpox
vaccine during
New York City
smallpox epidemic
1947
60
Models of the Spread and
Control of Disease through
Social Networks
•Diseases are spread through social networks.
•This is especially relevant to sexually transmitted
diseases such as AIDS.
•“Contact tracing” is an important part of any
strategy to combat outbreaks of diseases such as
smallpox, whether naturally occurring or resulting
61
from bioterrorist attacks.
The Basic Model
Social Network = Graph
Vertices = People
Edges = contact
State of a Vertex:
simplest model: 1 if infected, 0 if not infected
(SI Model)
More complex models: SI, SEI, SEIR, etc.
S = susceptible, E = exposed, I = infected, R =
recovered (or removed)
62
Example of a Social Network
63
More About States
Once you are infected, can you be cured?
If you are cured, do you become immune or can
you re-enter the infected state?
We can build a “directed graph” reflecting the
possible ways to move from state to state in the
model.
64
The State Diagram for a
Smallpox Model
The following diagram is from a Kaplan-CraftWein (2002) model for comparing alternative
responses to a smallpox attack. This has been
considered by the Centers for Disease Control
(CDC) and Office of Emergency Preparedness in
Dept. of Health and Human Services.
65
66
The Stages
Row 1: “Untraced” and in various stages of
susceptibility or infectiousness.
Row 2: Traced and in various stages of the
queue for vaccination.
Row 3: Unsuccessfully vaccinated and in
various stages of infectiousness.
Row 4: Successfully vaccinated; dead
67
Moving From State to State
Let si(t) give the state of vertex i at time t.
Two states 0 and 1.
Times are discrete: t = 0, 1, 2, …
68
Threshold Processes
Basic k-Threshold Process: You change your state
at time t+1 if at least k of your neighbors have
the opposite state at time t.
Disease interpretation? Cure if sufficiently many of
your neighbors are uninfected. Does this make
sense?
69
Threshold Processes II
Irreversible k-Threshold Process: You change
your state from 0 to 1 at time t+1 if at least k
of your neighbors have state 1 at time t. You
never leave state 1.
Disease interpretation? Infected if sufficiently
many of your neighbors are infected.
Special Case k = 1: Infected if any of your
neighbors is infected.
70
Basic 2-Threshold Process
71
72
73
Irreversible 2-Threshold
Process
74
75
76
Complications to Add to Model
•k = 1, but you only get infected with a certain
probability.
•You are automatically cured after you are in the
infected state for d time periods.
•You become immune from infection (can’t reenter state 1) once you enter and leave state 1.
•A public health authority has the ability to
“vaccinate” a certain number of vertices, making
77
them immune from infection.
Periodicity
State vector: s(t) = (s1(t), s2(t), …, sn(t)).
First example, s(1) = s(3) = s(5) = …,
s(0) = s(2) = s(4) = s(6) = …
Second example: s(1) = s(2) = s(3) = ...
In all of these processes, because there is a finite
set of vertices, for any initial state vector s(0), the
state vector will eventually become periodic, i.e.,
for some P and T, s(t+P) = s(t) for all t > T.
The smallest such P is called the period.
78
Periodicity II
First example: the period is 2.
Second example: the period is 1.
Both basic and irreversible threshold processes are
special cases of symmetric synchronous neural
networks.
Theorem (Goles and Olivos, Poljak and Sura): For
symmetric, synchronous neural networks, the
79
period is either 1 or 2.
Periodicity III
When period is 1, we call the ultimate state vector
a fixed point.
When the fixed point is the vector s(t) = (1,1,…,1)
or (0,0,…,0), we talk about a final common state.
One problem of interest: Given a graph, what
subsets S of the vertices can force one of our
processes to a final common state with entries
equal to the state shared by all the vertices in S in
the initial state?
80
Periodicity IV
Interpretation: Given a graph, what subsets S of
the vertices should we plant a disease with so that
ultimately everyone will get it? (s(t)  (1,1,…,1))
Economic interpretation: What set of people do we
place a new product with to guarantee “saturation”
of the product in the population?
Interpretation: Given a graph, what subsets S of
the vertices should we vaccinate to guarantee that
ultimately everyone will end up without the
81
disease? (s(t)  0,0,…,0))
Conversion Sets
Conversion set: Subset S of the vertices that can
force a k-threshold process to a final common state
with entries equal to the state shared by all the
vertices in S in the initial state. (In other words, if
all vertices of S start in same state x = 1 or 0, then
the process goes to a state where all vertices are in
state x.)
Irreversible k-conversion set if irreversible
process.
82
1-Conversion Sets
k = 1.
What are the conversion sets in a basic 1-threshold
process?
83
1-Conversion Sets
k = 1.
The only conversion set in a basic 1-threshold
process is the set of all vertices. For, if any two
adjacent vertices have 0 and 1 in the initial state,
then they keep switching between 0 and 1 forever.
What are the irreversible 1-conversion sets?
84
Irreversible 1-Conversion Sets
k = 1.
Every single vertex x is an irreversible 1conversion set if the graph is connected. We make
it 1 and eventually all vertices become 1 by
following paths from x.
85
Conversion Sets for Odd Cycles
C2p+1
2-threshold process.
What is a conversion set?
86
Conversion Sets for Odd Cycles
C2p+1.
2-threshold process.
Place p+1 1’s in “alternating” positions.
87
88
89
Conversion Sets for Odd Cycles
We have to be careful where we put the initial 1’s.
p+1 1’s do not suffice if they are next to each
other.
90
91
92
Irreversible Conversion Sets for
Odd Cycles
What if we want an irreversible conversion set
under an irreversible 2-threshold process?
Same set of p+1 vertices is an irreversible
conversion set. Moreover, everyone gets infected in
one step.
93
Vaccination Strategies
If you didn’t know whom a bioterrorist might
infect, what people would you vaccinate to be sure
that a disease doesn’t spread very much?
(Vaccinated vertices stay at state 0 regardless of
the state of their neighbors.)
Try odd cycles again. Consider an irreversible 2threshold process. Suppose your adversary has
enough supply to infect two individuals.
Strategy 1: “Mass vaccination”: make everyone 0
94
and immune in initial state.
Vaccination Strategies
In C5, mass vaccination means vaccinate 5
vertices. This obviously works.
In practice, vaccination is only effective with a
certain probability, so results could be different.
Can we do better than mass vaccination?
What does better mean? If vaccine has no cost and
is unlimited and has no side effects, of course we
95
use mass vaccination.
Vaccination Strategies
What if vaccine is in limited supply? Suppose we
only have enough vaccine to vaccinate 2 vertices.
Consider two different vaccination strategies:
Vaccination Strategy I
Vaccination Strategy II
96
Vaccination Strategy I: Worst Case
(Adversary Infects Two)
Two Strategies for Adversary
Adversary Strategy Ia
Adversary Strategy Ib
97
The “alternation” between your choice of a
defensive strategy and your adversary’s
choice of an offensive strategy suggests
we consider the problem from the point of
view of game theory.
The Food and Drug Administration is
studying the use of game-theoretic models
in the defense against bioterrorism.
98
Vaccination Strategy I
Adversary Strategy Ia
99
Vaccination Strategy I
Adversary Strategy Ib
100
Vaccination Strategy II: Worst Case
(Adversary Infects Two)
Two Strategies for Adversary
Adversary Strategy IIa
Adversary Strategy IIb
101
Vaccination Strategy II
Adversary Strategy IIa
102
Vaccination Strategy II
Adversary Strategy IIb
103
Conclusions about
Strategies I and II
If you can only vaccinate two individuals:
Vaccination Strategy II never leads to more
than two infected individuals, while Vaccination
Strategy I sometimes leads to three infected
individuals (depending upon strategy used by
adversary).
Thus, Vaccination Strategy II is better.
104
k-Conversion Sets
k-conversion sets are complex.
Consider the graph K4 x K2.
105
k-Conversion Sets II
Exercise: (a). The vertices a, b, c, d, e form a 2conversion set.
(b). However, the vertices a,b,c,d,e,f do not.
Interpretation: Immunizing one more person can be
worse! (Planting a disease with one more person
can be worse if you want to infect everyone.)
Note: the same does not hold true for irreversible
k-conversion sets.
106
NP-Completeness
Problem: Given a positive integer d and a graph
G, does G have a k-conversion set of size at
most d?
Theorem (Dreyer 2000): This problem is NPcomplete for fixed k > 2. (NP-complete probably
implies we will never have an efficient computer
algorithm for solving the problem.)
(Whether or not it is NP-complete for k = 2
remains open.)
Same conclusions for irreversible k-conversion set.
107
k-Conversion Sets in Regular
Graphs
G is r-regular if every vertex has degree r.
Set of vertices is independent if there are no edges.
Theorem (Dreyer 2000): Let G = (V,E) be a
connected r-regular graph and D be a set of
vertices.
(a). D is an irreversible r-conversion set iff V-D
is an independent set.
(b). D is an r-conversion set iff V-D is an
108
independent set and D is not an independent set.
k-Conversion Sets in Regular
Graphs II
Corollary (Dreyer 2000):
(a). The size of the smallest irreversible 2conversion set in Cn is ceiling[n/2].
(b). The size of the smallest 2-conversion set in Cn
is ceiling[(n+1)/2].
ceiling[x] = smallest integer at least as big as x.
This result agrees with our observation.
109
k-Conversion Sets in Grids
Let G(m,n) be the rectangular grid graph with m
rows and n columns.
G(3,4)
110
Toroidal Grids
The toroidal grid T(m,n) is obtained from the
rectangular grid G(m,n) by adding edges from the
first vertex in each row to the last and from the first
vertex in each column to the last.
Toroidal grids are easier to deal with than
rectangular grids because they form regular graphs:
Every vertex has degree 4. Thus, we can make use
of the results about regular graphs.
111
T(3,4)
112
4-Conversion Sets in Toroidal
Grids
Theorem (Dreyer 2000): In a toroidal grid T(m,n)
(a). The size of the smallest 4-conversion set is
max{n(ceiling[m/2]), m(ceiling[n/2])} m or n odd
{
mn/2 + 1
m, n even
(b). The size of the smallest irreversible 4conversion set is as above when m or n is
odd, and it is mn/2 when m and n are even.
113
Part of the Proof: Recall that D is an irreversible
4-conversion set in a 4-regular graph iff V-D is
independent.
V-D independent means that every edge {u,v} in
G has u or v in D. In particular, the ith row
must contain at least ceiling[n/2] vertices in D and
the ith column at least ceiling[m/2] vertices in D
(alternating starting with the end vertex of the row
or column).
We must cover all rows and all columns, and so
need at least max{n(ceiling[m/2]), m(ceiling[n/2])}
vertices in an irreversible 4-conversion set.
114
4-Conversion Sets for
Rectangular Grids
More complicated methods give:
Theorem (Dreyer 2000): The size of the smallest 4conversion set and smallest irreversible 4conversion set in a grid graph G(m,n) is
2m + 2n - 4 + floor[(m-2)(n-2)/2]
115
4-Conversion Sets for
Rectangular Grids
Consider G(3,3):
2m + 2n - 4 + floor[(m-2)(n-2)/2] = 8.
What is a smallest 4-conversion set and why 8?
116
4-Conversion Sets for
Consider G(3,3): Rectangular Grids
2m + 2n - 4 + floor[(m-2)(n-2)/2] = 8.
What is a smallest 4-conversion set and why 8?
All boundary vertices have degree < 4 and so must
be included in any 4-conversion set. They give
117
a conversion set.
More Realistic Models
Many oversimplifications. For instance:
•What if you stay infected only a certain number of
days?
•What if you are not necessarily infective for the
first few days you are sick?
•What if your threshold k for changes from 0 to 1
changes depending upon how long you have been
118
uninfected?
Alternative Models to Explore
Consider an irreversible process in which you stay
in the infected state (state 1) for d time periods
after entering it and then go back to the uninfected
state (state 0).
Consider a k-threshold process in which we
vaccinate a person in state 0 once k-1 neighbors are
infected (in state 1).
Etc. -- let your imagination roam free ...
119
More Realistic Models
Our models are deterministic. How do probabilities
enter?
•What if you only get infected with a certain
probability if you meet an infected person?
•What if vaccines only work with a certain
probability?
•What if the amount of time you remain infective
exhibits a probability distribution?
120
Alternative Model to Explore
Consider an irreversible 1-threshold process in
which you stay infected for d time periods and
then enter the uninfected state.
Assume that you get infected with probability p if
at least one of your neighbors is infected.
What is the probability that an epidemic will end
with no one infected?
121
The Case d = 2, p = 1/2
Consider the following initial state:
122
The Case d = 2, p = 1/2
With probability 1/2, vertex a does not get infected
at time 1.
Similarly for vertex b.
Thus, with probability 1/4, we stay in the same
states at time 1.
123
The Case d = 2, p = 1/2
Suppose vertices are still in same states at time 1 as
they were at time 0. With probability 1/2, vertex a
does not get infected at time 2.
Similarly for vertex b.
Also after time 1, vertices c and d have been
infected for two time periods and thus enter the
uninfected state.
Thus, with probability 1/4, we get to the following
124
state at time 2:
125
The Case d = 2, p = 1/2
Thus, with probability 1/4 x 1/4 = 1/16, we enter
this state with no one infected at time 2.
However, we might enter this state at a later time.
It is not hard to show (using the theory of finite
Markov chains) that we will end in state (0,0,0,0).
(This is the only absorbing state in an absorbing
Markov chain.). Thus: with probability 1 we will
eventually kill the disease off entirely.
126
The Case d = 2, p = 1/2
Is this realistic? What might we do to modify the
model to make it more realistic?
127
How do we Analyze this or
More Complex Models for
Graphs?
Computer simulation is an important tool.
Example: At the Johns Hopkins University and the
Brookings Institution, Donald Burke and Joshua
Epstein have developed a simple model for a
region with two towns totalling 800 people. It
involves a few more probabilistic assumptions
than ours. They use single simulations as a
learning device. They also run large numbers of
simulations and look at averages of outcomes. 128
How do we Analyze this or
More Complex Models for
Graphs?
Burke and Epstein are using the model to do
“what if” experiments:
What if we adopt a particular vaccination
strategy?
What happens if we try different plans for
quarantining infectious individuals?
There is much more analysis of a similar nature
that can be done with graph-theoretical models.
129
Would Graph Theory help with a
deliberate outbreak of Anthrax?
130
What about a deliberate release
of smallpox?
131
Similar approaches, using mathematical
models based on mathematical methods, have
proven useful in many other fields, to:
•make policy
•plan operations
•analyze risk
•compare interventions
•identify the cause of observed events
132
Why shouldn’t these approaches work in the
defense against bioterrorism?
133
134