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.
- R. M. Anderson and R. M. May. Population biology of infectious diseases: Part I. Nature, 280:361--367, Aug. 1979.Google ScholarCross Ref
- N. Bailey. The Mathematical Theory of Infectious Diseases and Its Applications. Hafner Press, New York, 1975.Google Scholar
- C. L. Barrett, K. R. Bisset, S. Eubank, X. Feng, and M. V. Marathe. Episimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks. In Proceedings of the ACM/IEEE Conference on High Performance Computing (SC), page 37, 2008. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Dept. of Health and Human Services. HHS pandemic influenza plan, 2007.Google Scholar
- P. S. Dodds and D. J. Watts. A generalized model of social and biological contagion. Journal of Theoretical Biology, 232:587--604, 2005.Google ScholarCross Ref
- S. Eubank. Scalable, efficient epidemiological simulation. In SAC'02: Proceedings of the 2002 ACM symposium on Applied computing, pages 139--145, New York, NY, USA, 2002. ACM. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- N. Ferguson et al. Strategies for mitigating an influenza pandemic. Nature, 442:448--452, 2006.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1):359--392, 1999. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Y. Kuznetsov and C. Piccardi. Bifurcation analysis of periodic SEIR and SIR epidemic models. Journal of Mathematical Biology, 32:109--121, 1994.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- J. D. Murray. Mathematical Biology I. An Introduction, volume 19 of Biomathematics. Springer-Verlag, 3rd edition, 2002.Google ScholarCross Ref
- M. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.Google ScholarDigital Library
- J. Parker. A flexible, large-scale, distributed agent based epidemic model. In Winter Simulation Conference, 2007. Google ScholarDigital Library
- World Health Organization. World health report 2007: A safe future: global public health security in the 21st century, 2007.Google Scholar
Index Terms
- EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems
Recommendations
Multigrain shared memory
Parallel workstations, each comprising tens of processors based on shared memory, promise cost-effective scalable multiprocessing. This article explores the coupling of such small- to medium-scale shared-memory multiprocessors through software over a ...
A Framework for Exploiting Task and Data Parallelism on Distributed Memory Multicomputers
Distributed Memory Multicomputers (DMMs), such as the IBM SP-2, the Intel Paragon, and the Thinking Machines CM-5, offer significant advantages over shared memory multiprocessors in terms of cost and scalability. Unfortunately, the utilization of all ...
Simulating the Spread of an Epidemic in a Small Rural Kansas Town
Substantial research has been dedicated to simulating the spread of infectious diseases. These simulation models have focused on major urban centers. Rural people have drastically different interaction and travel patterns than urban people. This paper ...
Comments