EpiSimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks

ABSTRACT

Preventing and controlling outbreaks of infectious diseases such as pandemic influenza is a top public health priority. We describe EpiSimdemics - a scalable parallel algorithm to simulate the spread of contagion in large, realistic social contact networks using individual-based models. EpiSimdemics is an interaction-based simulation of a certain class of stochastic reaction-diffusion processes. Straightforward simulations of such process do not scale well, limiting the use of individual-based models to very small populations. EpiSimdemics is specifically designed to scale to social networks with 100 million individuals. The scaling is obtained by exploiting the semantics of disease evolution and disease propagation in large networks. We evaluate an MPI-based parallel implementation of EpiSimdemics on a mid-sized HPC system, demonstrating that EpiSimdemics scales well. EpiSimdemics has been used in numerous sponsor defined case studies targeted at policy planning and course of action analysis, demonstrating the usefulness of EpiSimdemics in practical situations.

REFERENCES

• 1: World Health Organization, "World health report 2007: A safe future: global public health security in the 21st century," 2007.
• 2: Stephen Eubank, Scalable, efficient epidemiological simulation, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508819]
• 3: S. Eubank, H. Guclu, M. V. Marathe et al., "Modelling disease outbreaks in realistic urban social networks," Nature, vol. 429, no. 6988, pp. 180--184, May 2004.
• 4: M. E. Halloran, N. M. Ferguson, S. Eubank et al., "Modeling targeted layeredcontainment of an influenza pandemic in the United States," Proceedings of the National Academy of Sciences, vol. 105, no. 12, pp. 4639--4644, 2008.
• 5: K. M. Carley, D. B. Fridsma, E. Casman et al., "Biowar: Scalable agent-based model of bioattacks," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 36, no. 2, pp. 252--265, 2006.
• 6: Dina Goldin , Scott A. Smolka , Peter Wegner, Interactive Computation: The New Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 7: Stephen Eubank , V. S. Anil Kumar , Madhav V. Marathe , Aravind Srinivasan , Nan Wang, Structural and algorithmic aspects of massive social networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: C. L. Barrett, S. Eubank, and M. V. Marathe, "An interaction based approach to computational epidemics," in AAAI' 08: Proceedings of the Annual Conference of AAAI. Chicago USA: AAAI Press, 2008.
• 9: C. L. Barrett, R. J. Beckman et al., "TRANSIMS: Transportation analysis simulation system," Los Alamos National Laboratory Unclassfied Report, Tech. Rep. LA-UR-00-1725, 2001.
• 10: Jon Parker, A flexible, large-scale, distributed agent based epidemic model, Proceedings of the 39th conference on Winter simulation: 40 years! The best is yet to come, December 09-12, 2007, Washington D.C.
• 11: N. M. Ferguson, D. A. T. Cummings, C. Fraser, J. C. Cajka, P. C. Cooley, and D. S. Burke, "Strategies for mitigating an influenza pandemic," Nature, vol. 442, pp. 448--452, Apr. 2006.
• 12: T. C. Germann, K. Kadau, I. M. Longini, Jr., and C. A. Macken, "Mitigation strategies for pandemic influenza in the United States," Proc. of National Academy of Sciences, vol. 103, no. 15, pp. 5935--5940, Apr. 11 2006.
• 13: C. L. Barrett, K. Bisset, S. Eubank, M. V. Marathe, V. A. Kumar, and H. Mortveit, Modeling and Simulation of Biological Networks. AMS, 2007, ch. Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction Based Approach, pp. 101--147.
• 14: M. Newman, "The structure and function of complex networks," SIAM Review, vol. 45, no. 2, pp. 167--256, 2003.
• 15: P. S. Dodds and D. J. Watts, "A generalized model of social and biological ccontagion," Journal of THeoretical Biology, vol. 232, pp. 587--604, 2005.
• 16: K. Atkins, C. L. Barrett, R. J. Beckman et al., "Simulated pandemic influenza outbreaks in Chicago: NIH DHHS study final report," NDSSL, Tech. Rep. 06--023, 2006.
• 17: K. Atkins, C. L. Barrett, R. J. Beckman et al., "DTRA National Guard study capability demonstration," NDSSL, Tech. Rep. 06--060, 2006.
• 18: K. Atkins, C. L. Barrett, R. J. Beckman et al., "An analysis of public health interventions at military bases during a pandemic influenza event," NDSSL, Tech. Rep. 07--019, 2007.
• 19: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 20: Kalyan S. Perumalla, Parallel and distributed simulation: traditional techniques and recent advances, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
• 21: NDSSL, "Synthetic data products for societal infrastructures and protopopulations: Data set 2.0," NDSSL, Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, Tech. Rep. NDSSL-TR-07-003, 2007, http://ndssl.vbi.vt.edu/Publications/ndssl-tr-07-003.pdf.
• 22: C. on Modeling Community Containment for Pandemic Influenza and I. of Medicine, Modeling Community Containment for Pandemic Influenza: A Letter Report. Washington D.C.: The National Academies Press, 2006.
• 23: S. Riley, "Large-scale spatial-transmission models of infectious disease," Science, vol. 316, no. 5829, pp. 1298--1301, 2007.
• 24: N. M. Ferguson, M. J. Keeling et al., "Planning for smallpox outbreaks," Nature, vol. 425, no. 6959, pp. 681--685, 2003.
• 25: I. Longini, A. Nizam et al., "Containing pandemic influenza at the source," Science, vol. 309, no. 5737, pp. 1083--1087, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance