Scalable parallel and distributed simulation of an epidemic on a graph

Guohao Dou

PLOS ONE, 2023, vol. 18, issue 9, 1-34

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.

Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0291871 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 91871&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0291871

DOI: 10.1371/journal.pone.0291871

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().