EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems

ABSTRACT

Large scale realistic epidemic simulations have recently become an increasingly important application of high-performance computing. We propose a parallel algorithm, EpiFast, based on a novel interpretation of the stochastic disease propagation in a contact network. We implement it using a master-slave computation model which allows scalability on distributed memory systems.

EpiFast runs extremely fast for realistic simulations that involve: (i) large populations consisting of millions of individuals and their heterogeneous details, (ii) dynamic interactions between the disease propagation, the individual behaviors, and the exogenous interventions, as well as (iii) large number of replicated runs necessary for statistically sound estimates about the stochastic epidemic evolution. We find that EpiFast runs several magnitude faster than another comparable simulation tool while delivering similar results.

EpiFast has been tested on commodity clusters as well as SGI shared memory machines. For a fixed experiment, if given more computing resources, it scales automatically and runs faster. Finally, EpiFast has been used as the major simulation engine in real studies with rather sophisticated settings to evaluate various dynamic interventions and to provide decision support for public health policy makers.

REFERENCES

• 1: R. M. Anderson and R. M. May. Population biology of infectious diseases: Part I. Nature, 280:361--367, Aug. 1979.
• 2: N. Bailey. The Mathematical Theory of Infectious Diseases and Its Applications. Hafner Press, New York, 1975.
• 3: Christopher L. Barrett , Keith R. Bisset , Stephen G. Eubank , Xizhou Feng , Madhav V. Marathe, EpiSimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
• 4: C. L. Barrett, S. Eubank, and M. Marathe. An interaction based approach to computational epidemics. In AAAI'08: Proceedings of the Annual Conference of AAAI, Chicago USA, 2008. AAAI Press.
• 5: K. M. Carley, D. B. Fridsma, E. Casman, A. Yahja, N. Altman, L.-C. Chen, B. Kaminsky, and D. Nave. BioWar: scalable agent-based model of bioattacks. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 36(2):252--265, 2006.
• 6: Dept. of Health and Human Services. HHS pandemic influenza plan, 2007.
• 7: P. S. Dodds and D. J. Watts. A generalized model of social and biological contagion. Journal of Theoretical Biology, 232:587--604, 2005.
• 8: 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]
• 9: S. Eubank, H. Guclu, V. S. A. Kumar, M. V. Marathe, A. Srinivasan, T. Z., and N. Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6988):180--184, May 2004.
• 10: N. Ferguson, D. Cummings, S. Cauchemez, C. Fraser, S. Riley, A. Meeyai, S. Iamsirithaworn, and D. Burke. Strategies for containing an emerging influenza pandemic in Southeast Asia. Nature, 437:209--214, 2005.
• 11: N. Ferguson et al. Strategies for mitigating an influenza pandemic. Nature, 442:448--452, 2006.
• 12: T. C. Germann, K. Kadau, I. M. L. Jr., and C. A. Macken. Mitigation strategies for pandemic influenza in the United States. Proc. of National Academy of Sciences, 103(15):5935--5940, April 11 2006.
• 13: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 14: W. O. Kermack and A. G. McKendrick. A contribution to the mathematical theory of epidemics. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 115(772):700--721, Aug. 1927.
• 15: Y. Kuznetsov and C. Piccardi. Bifurcation analysis of periodic SEIR and SIR epidemic models. Journal of Mathematical Biology, 32:109--121, 1994.
• 16: I. M. Longini, A. Nizam, S. Xu, K. Ungchusak, W. Hanshaoworakul, D. A. T. Cummings, and M. E. Halloran. Containing pandemic influenza at the source. Science, 309(5737):1083--1087, 2005.
• 17: L. A. Meyers. Contact network epidemiology: Bond percolation applied to infectious disease prediction and control. Bulletin of The American Mathematical Society, 44:63--86, 2007.
• 18: L. A. Meyers, M. E. J. Newman, and B. Pourbohloul. Predicting epidemics on directed contact networks. Journal of Theoretical Biology, 240(3):400--418, 2006.
• 19: L. A. Meyers, B. Pourbohloul, M. E. J. Newman, D. M. Skowronskic, and R. C. Brunham. Network theory and SARS: predicting outbreak diversity. Journal of Theoretical Biology, 232(1):71--81, 2005.
• 20: J. D. Murray. Mathematical Biology I. An Introduction, volume 19 of Biomathematics. Springer-Verlag, 3rd edition, 2002.
• 21: M. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 22: 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.
• 23: World Health Organization. World health report 2007: A safe future: global public health security in the 21st century, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

General Terms:
Algorithms, Experimentation, Human Factors, Performance

Keywords:
distributed memory, epidemics, parallel algorithm, seir, simulation, social contact network