Transcript ppt

Simulating Diffusion Processes on
Very Large Complex networks
Jiangzhuo Chen
Joint work with Keith Bisset, Xizhou Feng,
Madhav Marathe, and Anil Vullikanti
SIAM Conference on Parallel Processing for Scientific Computing (PP10)
February 25, 2010
Network Dynamics & Simulation Science Laboratory
Talk Outline
• Background: simulation of infectious disease
propagation on social contact networks
• HPC-based parallel epidemic simulation tools
developed at NDSSL:
–
–
–
–
EpiSims
EpiSimdemics
EpiFast
Indemics
• Summarize
Network Dynamics & Simulation Science Laboratory
Epidemic Simulation
• This talk will focus on simulating a major
diffusion process – epidemic evolution – on large
scale social contact networks
• Models and ideas can be extended to other
diffusion processes on large scale networks like:
– Norms and fads in social networks
– Worms in communication networks
Network Dynamics & Simulation Science Laboratory
Disease Spread in a Social Network
• Within-host disease progression is modeled as a local
state transition function, called PTTS (probabilistic timed
transition system)
– Health states include: susceptible, infected but not infectious
(incubating), infectious but asymptomatic, infectious and
symptomatic, recovered.
– State transitions are probabilistic and timed
• Between-host disease transmission occurs along edges of
a social contact network
– Represented by people-location graph or people-people graph
– Transmissions are probabilistic
– Probability of a person getting infected depends only on his local
properties and people that he has contact with: symmetry
assumption
Network Dynamics & Simulation Science Laboratory
Interventions
• Pharmaceutical interventions (PI’s): vaccination or antiviral
changes an individual’s role in the transmission chain
– Lower susceptibility to infection
– Lower infectiousness if infected
– The degree these are lowered depends on the efficacy of the vaccine
or antiviral
• Non-pharmaceutical interventions (NPI’s): social distancing
measures change people activities and change the social
network
– Generic social distancing, school closure, isolation, etc.
• Interventions are often associated with trigger conditions and
selected subpopulations
– When, how, and to whom these are applied can have different impact
on the course of the epidemic
Network Dynamics & Simulation Science Laboratory
EpiSims: Precise Simulation
• Parallel discrete event simulation (PDES)
• Within-host disease progression: coupled PTTS
(probabilistic timed transistion system)
• Between-host disease transmission: peoplelocation bipartite graph
• Complex interventions:
– NPI’s change people activity schedules, so change
people-location graph
– PI’s change people susceptibility/infectivity
Network Dynamics & Simulation Science Laboratory
EpiSims: Parallel Algorithm
• Symmetric computations among processors
• Locations are partitioned and assigned to processors
• Each person v has corresponding data Dv
(demographics, health state, activity schedule, etc.)
• Dv is moved from the processor which has location A
to the processor which has location B if v moves from
A to B
• System synchronizes at every event: person changes
activity location, person health state changes, etc.
Network Dynamics & Simulation Science Laboratory
EpiSims: Performance
• Too many events: too many synchronizations
• High communication cost for moving data
between processors
• Scales poorly for large urban populations (size >
10 million)
• Simulation running time: magnitude of
hours~days for Chicago (9 million people)
• Good for small populations or small number of
replicates
Network Dynamics & Simulation Science Laboratory
EpiSimdemics: Fast Simulation
• Parallel discrete time simulation
• Within-host disease progression: coupled
PTTS (highly configurable disease model)
• Between-host disease transmission:
people-location bipartite graph
• Complex interventions specified by
scenario scripting language:
– NPI’s change people activity schedules, so change
people-location graph
– PI’s change people susceptibility/infectivity
Network Dynamics & Simulation Science Laboratory
EpiSimdemics: Peformance
• Parallel algorithm:
– Partition locations and assign them to processors
– Partition people and assign them to processors
– At each time step, for each location compute a serial DES; system
synchronization
• Approximations (from PDES):
– discrete time simulation
– Relaxation of causality constraint: system synchronization at
every time step (every simulation day)
• C++/MPI implementation
• Scaling: 100 million people on 1k cores
• Simulation running time: magnitude of hours for large
urban populations
Network Dynamics & Simulation Science Laboratory
EpiSimdemics Algorithm
Generate the population
Set initial infections
Based on activities move
the people to the locations
Compute interactions
among the people at the
locations
Some exposed people
may become infected
After their activities, the
people are moved back
to their home PE
Update state of person at
his home PE
Network Dynamics & Simulation Science Laboratory
EpiSimdemics: Use Case
• Flu in Alabama
– Similar to studies done for sponsors (NIH, CDC, DTRA,
etc.)
– Population size = 4.3 million
• 4 interventions (16 combinations)
–
–
–
–
Vaccination (prevaccinate children, critical workers)
School closure (close/reopen on per county basis)
Quarantine of critical workers
Self isolation (when global attack rate is high)
Network Dynamics & Simulation Science Laboratory
Disease Model
Network Dynamics & Simulation Science Laboratory
Results
Network Dynamics & Simulation Science Laboratory
Results for Critical Workers
• Quarantine of critical workers has no effect on
the general population
• When critical workers are vaccinated and
quarantined, their infection rate drops from 40%
to 18%
• May be important for continuous functioning of
society
Network Dynamics & Simulation Science Laboratory
EpiFast: Faster Simulation
• Parallel discrete time simulation based on
percolation model
• Within-host disease progression: standard SEIR
disease model
• Between-host disease transmission: through
edges of people-people contact network
• Interventions
– Pharmaceutical or non-pharmaceutical: predefined
impacts on network nodes and edges
– On day <t> or when a given threshold <x> is met,
apply intervention <i> on subpopulation <s>
Network Dynamics & Simulation Science Laboratory
EpiFast: Social Contact Network
• From people-location graph to people-people contact network:
–
–
–
–
–
People follow daily activity schedules
Activities take them to locations
At locations they interact with each other
Interactions form contact network
Nodes are people, edges are contacts, edge weights are contact durations
• Interactions in a population can get very complex
– e.g. New York city has 18 million people and a total of 1 billion interactions
• Disease spread in contact network depends on
–
–
–
–
Duration of contact
Types of activities while in contact
Characteristics of the infectious person
Characteristics of the susceptible person
• EpiFast assumes the network remains the same from day to day
unless with interventions
Network Dynamics & Simulation Science Laboratory
EpiFast: Algorithm
• Parallel implementation:
– Master-slave model
– Partition contact network: each slave processor is assigned a
subset of nodes and all outgoing edges
– Single master processor: communication; many slave processors:
computation
– Highly portable C++/MPI implementation
• Approximations (from PDES):
– Network edges (contacts) are not ordered by time
– Network remains the same from day to day unless with
interventions
– Synchronizes every simulation day
– Interventions change the contact network (node or edge
properties); changes are approximate
Network Dynamics & Simulation Science Laboratory
EpiFast: Performance
• By far the fastest (to our best knowledge) among
all epidemic simulations that can handle realistic
synthetic populations and provide comparable
support for realistic intervention measures.
– Network of 16 million nodes and 900 million edges:
<20 minutes per replicate on as few as 32 processors
• Scales well on distributed memory systems
– Good strong and weak scaling properties
Network Dynamics & Simulation Science Laboratory
EpiFast Performance: Strong Scaling
Network Dynamics & Simulation Science Laboratory
EpiFast Performance: Week Scaling
Population Population Size CPU Number
Running Time (seconds)
per simulation day
Miami
2.09
32
0.47
Boston
4.15
64
0.54
Chicago
9.05
128
0.54
Network Dynamics & Simulation Science Laboratory
EpiFast: Use Case
Factorial design: 2x2x2x2 x 25 replicates = 400 runs
Network Dynamics & Simulation Science Laboratory
Indemics: Interactive Simulation
• Indemics: Interactive Epidemic Simulation and Modeling
Environment
• New data-centric architecture for interactive epidemic
simulation environments
• Decouples the data, disease diffusion, intervention and
user interaction
– Simplify design and implementation of simulation engine
– performance can be optimized separately
• High performance computing service architecture
– User can access the system via a web server from anywhere
– HPC-based system supports coordination, data management and
disease diffusion
– Reduction in speed is easily compensated by ease of interaction
and rich feature set
Network Dynamics & Simulation Science Laboratory
Indemics: System Architecture
Indemics database running on a data server
Semistructured
database
Temporal
database
Relational
database
Indemics Server, running on head node of HPC
Indemics
Server
New Interventions
Queries & Interventions
New disease state
Indemics
Adapter
Indemics
Adapater
Interactive
Client
Batch
Client
Indemics web-interface Client,on PC
Analyst sees only this module
HPC Epidemic Simulator
(e.g. EpiFast)
Network Dynamics & Simulation Science Laboratory
Indemics: Abstractions
• Data Models:
– Relational data about individuals (P)
– Social contact network (N)
– Transmission network/dendrogram (D)
• Models of Interaction between user, data and model
– Query: function of (P,N,D)
• E.g. who are sick, how many of a concerned subpop are sick
• Does not change the disease progression
• Can be expressed by SQL script
– Intervention: active interaction
• makes a change to the social network, individual behavior, or
disease model; and moves the simulation forward
• apply intervention <i> to subpopulation <g> with parameter <p>
Network Dynamics & Simulation Science Laboratory
Indemics: Queries
• Queries on a single data type
– (P) Find all school-age people in Seattle
– (N) Find all network neighbors (contacts) of a specific person
– (D) Find all people infected in last week
• Queries across multiple data types
– Count number of infected persons in zip code 24060 (Blacksburg, VA)
– Find infectious students in Blacksburg high school and their family members
• Users interact with the system using well-defined languages
– Indemics commands: count infected persons : group = seniors, infected day =
between 20 and 22
– SQL statements: select edge_head from network table SN and infection table
INF where SN.edge_tail = INF.infected_pid and infection_day = 20 (find
contacts of people infected on day 20)
– Libraries of queries can be pre-defined by expert users
Network Dynamics & Simulation Science Laboratory
Indemics: Interventions
• Intervention abstraction
apply intervention <i> to subpopulation <g> with parameter <p>
• Intervention types
vaccination, antiviral, school closure, work closure, generic social
distancing, etc.
• Subpopulations (to which interventions are applied)
– Predefined groups: preschool, school age, adult, senior, critical workers, etc
– Dynamic group: result of any query
e.g.: group g = {family members of persons who were infected on day 10}
• Indemics command
– apply interventions: type = antivirus, duration = 20, group = school age,
infected_day = between 24 and 30
– apply interventions: type=work closure, duration = 20, group = adults, infected
day = between 20 and 21; type = school closure, duration = 5, group = school
age
Network Dynamics & Simulation Science Laboratory
Indemics: Performance
• Simulates what the original simulator can simulate,
with small overhead
– E.g. same scenario: vaccinate preschools on threshold
condition. Indemics occurs 70% overhead running time on
top of EpiFast.
• Far larger modeling capabilities with reasonably
good performance
– E.g. household level interventions were not supported in
EpiFast.
– Indemics can handle them easily. Cost of interaction and
data communication is marginal (~20%) comparing with
simulation cost.
– Overhead for interactions is easily offset by infinitely larger
capability and flexibility provided by Indemics.
Network Dynamics & Simulation Science Laboratory
Indemics Performance: Cost of
Interaction/Communication
Network Dynamics & Simulation Science Laboratory
Indemics: Use Case
Public intervention versus private intervention:
• Ring vaccination
– Administered by public health authorities
– All direct contacts of any infectious individual are
identified and vaccinated (by government)
• D1 vaccination
– Individual self-motivated
– People voluntarily take vaccines when they find the
number of infectious people among their direct
contacts exceed some threshold
Network Dynamics & Simulation Science Laboratory
Results
Network Dynamics & Simulation Science Laboratory
Summary of Our Epidemic Simulation Tools
• EpiSims: precise but slow; good for smaller
populations and complicated scenarios and
interventions.
• EpiSimdemics: fast, good scaling; good for large
populations and complicated scenarios and
interventions but only a few replicates
• EpiFast: fastest, good scaling; good for large
population with simple scenarios and predefined
interventions but large number of replicates
• Indemics: most capable and flexible, extra running
time; good for exploring various intervention
strategies
Network Dynamics & Simulation Science Laboratory
Thanks!
Network Dynamics & Simulation Science Laboratory
Work funded in part by NIGMS, NIH MIDAS program, CDC, Center of
Excellence in Medical Informatics, DTRA CNIMS, NSF, NeTs, NECO and OCI
program, VT Foundation.
Network Dynamics & Simulation Science Laboratory