IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0291871.html
   My bibliography  Save this article

Scalable parallel and distributed simulation of an epidemic on a graph

Author

Listed:
  • Guohao Dou

Abstract

We propose an algorithm to simulate Markovian SIS epidemics with homogeneous rates and pairwise interactions on a fixed undirected graph, assuming a distributed memory model of parallel programming and limited bandwidth. This setup can represent a broad class of simulation tasks with compartmental models. Existing solutions for such tasks are sequential by nature. We provide an innovative solution that makes trade-offs between statistical faithfulness and parallelism possible. We offer an implementation of the algorithm in the form of pseudocode in the Appendix. Also, we analyze its algorithmic complexity and its induced dynamical system. Finally, we design experiments to show its scalability and faithfulness. In our experiments, we discover that graph structures that admit good partitioning schemes, such as the ones with clear community structures, together with the correct application of a graph partitioning method, can lead to better scalability and faithfulness. We believe this algorithm offers a way of scaling out, allowing researchers to run simulation tasks at a scale that was not accessible before. Furthermore, we believe this algorithm lays a solid foundation for extensions to more advanced epidemic simulations and graph dynamics in other fields.

Suggested Citation

  • Guohao Dou, 2023. "Scalable parallel and distributed simulation of an epidemic on a graph," PLOS ONE, Public Library of Science, vol. 18(9), pages 1-34, September.
    • Handle: RePEc:plo:pone00:0291871
    DOI: 10.1371/journal.pone.0291871
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0291871
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0291871&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0291871?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Neil M. Ferguson & Derek A. T. Cummings & Christophe Fraser & James C. Cajka & Philip C. Cooley & Donald S. Burke, 2006. "Strategies for mitigating an influenza pandemic," Nature, Nature, vol. 442(7101), pages 448-452, July.
    2. Qu, Bo & Wang, Huiijuan, 2017. "SIS epidemic spreading with correlated heterogeneous infection rates," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 472(C), pages 13-24.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Catalina Amuedo-Dorantes & Neeraj Kaushal & Ashley N. Muchow, 2021. "Timing of social distancing policies and COVID-19 mortality: county-level evidence from the U.S," Journal of Population Economics, Springer;European Society for Population Economics, vol. 34(4), pages 1445-1472, October.
    2. Susan M. Rogers & James Rineer & Matthew D. Scruggs & William D. Wheaton & Phillip C. Cooley & Douglas J. Roberts & Diane K. Wagener, 2014. "A Geospatial Dynamic Microsimulation Model for Household Population Projections," International Journal of Microsimulation, International Microsimulation Association, vol. 7(2), pages 119-146.
    3. Andrew G. Atkeson & Karen A. Kopecky & Tao Zha, 2024. "Four Stylized Facts About Covid‐19," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 65(1), pages 3-42, February.
    4. Victor W. Chu & Raymond K. Wong & Chi-Hung Chi & Wei Zhou & Ivan Ho, 2017. "The design of a cloud-based tracker platform based on system-of-systems service architecture," Information Systems Frontiers, Springer, vol. 19(6), pages 1283-1299, December.
    5. Khan, Hasib & Ibrahim, Muhammad & Abdel-Aty, Abdel-Haleem & Khashan, M. Motawi & Khan, Farhat Ali & Khan, Aziz, 2021. "A fractional order Covid-19 epidemic model with Mittag-Leffler kernel," Chaos, Solitons & Fractals, Elsevier, vol. 148(C).
    6. Wouter Vermeer & Otto Koppius & Peter Vervest, 2018. "The Radiation-Transmission-Reception (RTR) model of propagation: Implications for the effectiveness of network interventions," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-21, December.
    7. Phillip Stroud & Sara Del Valle & Stephen Sydoriak & Jane Riese & Susan Mniszewski, 2007. "Spatial Dynamics of Pandemic Influenza in a Massive Artificial Society," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 10(4), pages 1-9.
    8. Caixia Wang & Huijie Li, 2022. "Public Compliance Matters in Evidence-Based Public Health Policy: Evidence from Evaluating Social Distancing in the First Wave of COVID-19," IJERPH, MDPI, vol. 19(7), pages 1-13, March.
    9. Krista Ruffini & Aaron Sojourner & Abigail Wozniak, 2021. "Who'S In And Who'S Out Under Workplace Covid Symptom Screening?," Journal of Policy Analysis and Management, John Wiley & Sons, Ltd., vol. 40(2), pages 614-641, March.
    10. Lin Ma & Gil Shapira & Damien de Walque & Quy‐Toan Do & Jed Friedman & Andrei A. Levchenko, 2022. "The Intergenerational Mortality Trade‐Off Of Covid‐19 Lockdown Policies," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 63(3), pages 1427-1468, August.
    11. Philipp Ager & Katherine Eriksson & Ezra Karger & Peter Nencka & Melissa A. Thomasson, 2024. "School Closures during the 1918 Flu Pandemic," The Review of Economics and Statistics, MIT Press, vol. 106(1), pages 266-276, January.
    12. repec:plo:pone00:0243699 is not listed on IDEAS
    13. repec:plo:pone00:0128070 is not listed on IDEAS
    14. Jérôme Adda, 2016. "Economic Activity and the Spread of Viral Diseases: Evidence from High Frequency Data," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 131(2), pages 891-941.
    15. Peter Caley & Niels G Becker & David J Philp, 2007. "The Waiting Time for Inter-Country Spread of Pandemic Influenza," PLOS ONE, Public Library of Science, vol. 2(1), pages 1-8, January.
    16. repec:plo:pone00:0001519 is not listed on IDEAS
    17. Brotherhood, Luiz & Jerbashian, Vahagn, 2023. "Firm behavior during an epidemic," Journal of Economic Dynamics and Control, Elsevier, vol. 147(C).
    18. Eva K. Lee & Ferdinand Pietz & Bernard Benecke & Jacquelyn Mason & Greg Burel, 2013. "Advancing Public Health and Medical Preparedness with Operations Research," Interfaces, INFORMS, vol. 43(1), pages 79-98, February.
    19. repec:plo:pone00:0024706 is not listed on IDEAS
    20. Martin S Eichenbaum & Sergio Rebelo & Mathias Trabandt, 2021. "The Macroeconomics of Epidemics [Economic activity and the spread of viral diseases: Evidence from high frequency data]," The Review of Financial Studies, Society for Financial Studies, vol. 34(11), pages 5149-5187.
    21. James H. Fowler & Seth J. Hill & Remy Levin & Nick Obradovich, 2020. "The effect of stay-at-home orders on COVID-19 cases and fatalities in the United States," Papers 2004.06098, arXiv.org, revised May 2020.
    22. Wallace, Matthew L. & Ràfols, Ismael, 2018. "Institutional shaping of research priorities: A case study on avian influenza," Research Policy, Elsevier, vol. 47(10), pages 1975-1989.
    23. Martin Eichenbaum & Miguel Godinho de Matos & Francisco Lima & Sergio Rebelo & Mathias Trabandt, 2024. "Expectations, Infections, and Economic Activity," Journal of Political Economy, University of Chicago Press, vol. 132(8), pages 2571-2611.
    24. Yasushi Iwamoto, 2021. "Welfare economics of managing an epidemic: an exposition," The Japanese Economic Review, Springer, vol. 72(4), pages 537-579, October.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0291871. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.