Preventing and slowing the spread of epidemics
is achieved through techniques such as vaccination and social
distancing. Given practical limitations on the number of vaccines
and cost of administration, optimization becomes a necessity.
Previous approaches using mathematical programming methods
have shown to be effective but are limited by computational
costs. In this work, we present PREEMPT, a new approach for
intervention via maximizing the influence of vaccinated nodes on
the network.We prove submodular properties associated with the
objective function of our method so that it aids in construction
of an efficient greedy approximation strategy. Consequently, we
present a new parallel algorithm based on greedy hill climbing
for PREEMPT, and present an efficient parallel implementation
for distributed CPU-GPU heterogeneous platforms. Our results
demonstrate that PREEMPT is able to achieve a significant
reduction (up to 6:75) in the percentage of people infected
and up to 98% reduction in the peak of the infection on a cityscale
network. We also show strong scaling results of PREEMPT
on up to 128 nodes of the Summit supercomputer. Our parallel
implementation is able to significantly reduce time to solution,
from hours to minutes on large networks. This work represents
a first-of-its-kind effort in parallelizing greedy hill climbing and
applying it toward devising effective interventions for epidemics.
more »
« less
Agent-Based Computational Epidemiological Modeling
The study of epidemics is useful for not only understanding outbreaks and trying to limit their adverse effects, but also because epidemics are related to social phenomena such as government instability, crime, poverty, and inequality. One approach for studying epidemics is to simulate their spread through populations. In this work, we describe an integrated multi-dimensional approach to epidemic simulation, which encompasses: (i) a theoretical framework for simulation and analysis; (ii) synthetic population (digital twin) generation; (iii) (social contact) network construction methods from synthetic populations, (iv) stylized network construction methods; and (v) simulation of the evolution of a virus or disease through a social network. We describe these aspects and end with a short discussion on simulation results that inform public policy.
more »
« less
- Award ID(s):
- 1916670
- NSF-PAR ID:
- 10310251
- Date Published:
- Journal Name:
- Journal of the Indian Institute of Science
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)The U.S. is in the grips of a devastating opioid and heroin co-epidemic affecting nearly all socio-economic populations at great human (~7,800 new users/day) and financial ($78.5 billion/year) costs but with no obvious solution. We describe recent work and challenges to develop, integrate, and use several analytic multi-scale simulation models of these epidemics to develop insight into the epidemic’s complex underlying dynamics, generate causal hypotheses, and inform effective policy interventions. We developed preliminary agent-based, differential equation, network spread, and cellular automata models that reasonably replicate at multiple scales the past 17 years of this epidemic’s growth and spread at town, county, state, and national levels. Results suggest that some current approaches are unlikely to be very effective, some in fact may worsen the epidemic, and ultimately only certain combinations and sequences of policies are likely to have value, with important implications on both model architecture and policy optimization.more » « less
-
Contagion dynamics on networks are used to study many problems, including disease and virus epidemics, incarceration, obesity, protests and rebellions, needle sharing in drug use, and hurricane and other natural disaster events. Simulators to study these problems range from smaller-scale serial codes to large-scale distributed systems. In recent years, Python-based simulation systems have been built. In this work, we describe a new Python-based agent-based simulator called CSonNet. It differs from codes such as Epidemics on Networks in that it performs discrete time simulations based on the graph dynamical systems formalism. CSonNet is a parallel code; it implements concurrency through an embarrassingly parallel approach of running multiple simulation instances on a user-specified number of forked processes. It has a modeling framework whereby agent models are composed using a set of pre-defined state transition rules. We provide strong-scaling performance results and case studies to illustrate its features.more » « less
-
Contagion dynamics on networks are used to study many problems, including disease and virus epidemics, incarceration, obesity, protests and rebellions, needle sharing in drug use, and hurricane and other natural disaster events. Simulators to study these problems range from smaller-scale serial codes to large-scale distributed systems. In recent years, Python based simulation systems have been built. In this work, we describe a new Python-based agent-based simulator called CSonNet. It differs from codes such as Epidemics on Networks in that it performs discrete time simulations based on the graph dynamical systems formalism. CSonNet is a parallel code; it implements concurrency through an embarrassingly parallel approach of running multiple simulation instances on a user-specified number of forked processes. It has a modeling framework whereby agent models are composed using a set of pre-defined state transition rules. We provide strong-scaling performance results and case studies to illustrate its features.more » « less
-
Sybil attacks present a significant threat to many Internet systems and applications, in which a single adversary inserts multiple colluding identities in the system to compromise its security and privacy. Recent work has advocated the use of social-network-based trust relationships to defend against Sybil attacks. However, most of the prior security analyses of such systems examine only the case of social networks at a single instant in time. In practice, social network connections change over time, and attackers can also cause limited changes to the networks. In this work, we focus on the temporal dynamics of a variety of social-network-based Sybil defenses. We describe and examine the effect of novel attacks based on: (a) the attacker's ability to modify Sybil-controlled parts of the social-network graph, (b) his ability to change the connections that his Sybil identities maintain to honest users, and (c) taking advantage of the regular dynamics of connections forming and breaking in the honest part of the social network. We find that against some defenses meant to be fully distributed, such as SybilLimit and Persea, the attacker can make dramatic gains over time and greatly undermine the security guarantees of the system. Even against centrally controlled Sybil defenses, the attacker can eventually evade detection (e.g. against SybilInfer and SybilRank) or create denial-of-service conditions (e.g. against Ostra and SumUp). After analysis and simulation of these attacks using both synthetic and real-world social network topologies, we describe possible defense strategies and the trade-offs that should be explored. It is clear from our findings that temporal dynamics need to be accounted for in Sybil defense or else the attacker will be able to undermine the system in unexpected and possibly dangerous ways.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/s41745-021-00260-2
