{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:35:23Z","timestamp":1756571723877,"version":"3.40.5"},"reference-count":60,"publisher":"Public Library of Science (PLoS)","issue":"9","license":[{"start":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T00:00:00Z","timestamp":1695945600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.plosone.org"],"crossmark-restriction":false},"short-container-title":["PLoS ONE"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1371\/journal.pone.0291871","type":"journal-article","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T17:26:18Z","timestamp":1696008378000},"page":"e0291871","update-policy":"https:\/\/doi.org\/10.1371\/journal.pone.corrections_policy","source":"Crossref","is-referenced-by-count":1,"title":["Scalable parallel and distributed simulation of an epidemic on a graph"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3879-8700","authenticated-orcid":true,"given":"Guohao","family":"Dou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"340","published-online":{"date-parts":[[2023,9,29]]},"reference":[{"key":"pone.0291871.ref001","first-page":"77482","article-title":"Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand. Imperial College COVID-19 Response Team","volume":"20","author":"NM Ferguson","year":"2020","journal-title":"Imperial College COVID-19 Response Team"},{"issue":"7101","key":"pone.0291871.ref002","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1038\/nature04795","article-title":"Strategies for mitigating an influenza pandemic","volume":"442","author":"NM Ferguson","year":"2006","journal-title":"Nature"},{"issue":"10","key":"pone.0291871.ref003","doi-asserted-by":"crossref","first-page":"108701","DOI":"10.1103\/PhysRevLett.110.108701","article-title":"Non-Markovian infection spread dramatically alters the susceptible-infected-susceptible epidemic threshold in networks","volume":"110","author":"P Van Mieghem","year":"2013","journal-title":"Physical review letters"},{"issue":"4","key":"pone.0291871.ref004","doi-asserted-by":"crossref","first-page":"042108","DOI":"10.1103\/PhysRevE.90.042108","article-title":"Simulating non-Markovian stochastic processes","volume":"90","author":"M Bogun\u00e1","year":"2014","journal-title":"Physical Review E"},{"issue":"2","key":"pone.0291871.ref005","doi-asserted-by":"crossref","first-page":"022813","DOI":"10.1103\/PhysRevE.88.022813","article-title":"Slow epidemic extinction in populations with heterogeneous infection rates","volume":"88","author":"C Buono","year":"2013","journal-title":"Physical Review E"},{"issue":"3","key":"pone.0291871.ref006","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1109\/TNSE.2017.2709786","article-title":"SIS epidemic spreading with heterogeneous infection rates","volume":"4","author":"B Qu","year":"2017","journal-title":"IEEE Transactions on Network Science and Engineering"},{"key":"pone.0291871.ref007","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","article-title":"Networks beyond pairwise interactions: structure and dynamics","volume":"874","author":"F Battiston","year":"2020","journal-title":"Physics Reports"},{"issue":"20","key":"pone.0291871.ref008","doi-asserted-by":"crossref","first-page":"208701","DOI":"10.1103\/PhysRevLett.96.208701","article-title":"Epidemic dynamics on an adaptive network","volume":"96","author":"T Gross","year":"2006","journal-title":"Physical review letters"},{"issue":"20","key":"pone.0291871.ref009","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1098\/rsif.2007.1229","article-title":"Adaptive coevolutionary networks: a review","volume":"5","author":"T Gross","year":"2008","journal-title":"Journal of the Royal Society Interface"},{"issue":"10","key":"pone.0291871.ref010","doi-asserted-by":"crossref","first-page":"e1004579","DOI":"10.1371\/journal.pcbi.1004579","article-title":"Temporal Gillespie algorithm: fast simulation of contagion processes on time-varying networks","volume":"11","author":"CL Vestergaard","year":"2015","journal-title":"PLoS computational biology"},{"key":"pone.0291871.ref011","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2019.07.001","article-title":"Coevolution spreading in complex networks","volume":"820","author":"W Wang","year":"2019","journal-title":"Physics Reports"},{"issue":"4","key":"pone.0291871.ref012","doi-asserted-by":"crossref","first-page":"041125","DOI":"10.1103\/PhysRevE.86.041125","article-title":"Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical results","volume":"86","author":"SC Ferreira","year":"2012","journal-title":"Physical Review E"},{"issue":"4","key":"pone.0291871.ref013","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0021-9991(76)90041-3","article-title":"A general method for numerically simulating the stochastic time evolution of coupled chemical reactions","volume":"22","author":"DT Gillespie","year":"1976","journal-title":"Journal of computational physics"},{"issue":"9","key":"pone.0291871.ref014","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1021\/jp993732q","article-title":"Efficient exact stochastic simulation of chemical systems with many species and many channels","volume":"104","author":"MA Gibson","year":"2000","journal-title":"The journal of physical chemistry A"},{"issue":"2","key":"pone.0291871.ref015","doi-asserted-by":"crossref","first-page":"026116","DOI":"10.1103\/PhysRevE.86.026116","article-title":"Susceptible-infected-susceptible model: A comparison of N-intertwined and heterogeneous mean-field approximations","volume":"86","author":"C Li","year":"2012","journal-title":"Physical Review E"},{"issue":"2210","key":"pone.0291871.ref016","doi-asserted-by":"crossref","first-page":"20170695","DOI":"10.1098\/rspa.2017.0695","article-title":"Pairwise approximation for SIR-type network epidemics with non-Markovian recovery","volume":"474","author":"G R\u00f6st","year":"2018","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences"},{"issue":"5","key":"pone.0291871.ref017","doi-asserted-by":"crossref","first-page":"052125","DOI":"10.1103\/PhysRevE.94.052125","article-title":"Limitations of discrete-time approaches to continuous-time contagion dynamics","volume":"94","author":"PG Fennell","year":"2016","journal-title":"Physical Review E"},{"key":"pone.0291871.ref018","doi-asserted-by":"crossref","unstructured":"Fujimoto R. Parallel and distributed simulation. In: 2015 Winter Simulation Conference (WSC). IEEE; 2015. p. 45\u201359.","DOI":"10.1109\/WSC.2015.7408152"},{"key":"pone.0291871.ref019","unstructured":"Bryant RE. Simulation of Packet Communication Architecture Computer Systems. MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE; 1977."},{"issue":"3","key":"pone.0291871.ref020","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1145\/3916.3988","article-title":"Virtual time","volume":"7","author":"DR Jefferson","year":"1985","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"},{"issue":"7","key":"pone.0291871.ref021","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1177\/0037549711413001","article-title":"Discrete event modeling and massively parallel execution of epidemic outbreak phenomena","volume":"88","author":"KS Perumalla","year":"2012","journal-title":"Simulation"},{"issue":"1-2","key":"pone.0291871.ref022","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0025-5564(02)00122-0","article-title":"Daniel Bernoulli\u2019s epidemiological model revisited","volume":"180","author":"K Dietz","year":"2002","journal-title":"Mathematical biosciences"},{"issue":"772","key":"pone.0291871.ref023","first-page":"700","article-title":"A contribution to the mathematical theory of epidemics","volume":"115","author":"WO Kermack","year":"1927","journal-title":"Proceedings of the royal society of london Series A, Containing papers of a mathematical and physical character"},{"key":"pone.0291871.ref024","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-540-78911-6_2","article-title":"Compartmental models in epidemiology","author":"F Brauer","year":"2008","journal-title":"Mathematical epidemiology"},{"issue":"12","key":"pone.0291871.ref025","doi-asserted-by":"crossref","first-page":"201878","DOI":"10.1098\/rsos.201878","article-title":"SI epidemic model applied to COVID-19 data in mainland China","volume":"7","author":"J Demongeot","year":"2020","journal-title":"Royal Society Open Science"},{"key":"pone.0291871.ref026","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-319-50806-1","volume-title":"Mathematics of epidemics on networks","author":"IZ Kiss","year":"2017"},{"key":"pone.0291871.ref027","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1016\/j.procs.2013.05.389","article-title":"Parallel programming approaches for an agent-based simulation of concurrent pandemic and seasonal influenza outbreaks","volume":"18","author":"M Soto-Ferrari","year":"2013","journal-title":"Procedia computer science"},{"key":"pone.0291871.ref028","doi-asserted-by":"crossref","unstructured":"Bhatele A, Yeom JS, Jain N, Kuhlman CJ, Livnat Y, Bisset KR, et al. Massively parallel simulations of spread of infectious diseases over realistic social networks. In: 2017 17th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). IEEE; 2017. p. 689\u2013694.","DOI":"10.1109\/CCGRID.2017.141"},{"issue":"2","key":"pone.0291871.ref029","doi-asserted-by":"crossref","DOI":"10.1145\/3589296","article-title":"Generalizing Bulk-Synchronous Parallel Processing for Data Science: From Data to Threads and Agent-Based Simulations","volume":"1","author":"Z Tian","year":"2023","journal-title":"Proc ACM Manag Data"},{"key":"pone.0291871.ref030","doi-asserted-by":"crossref","unstructured":"Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, et al. Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data; 2010. p. 135\u2013146.","DOI":"10.1145\/1807167.1807184"},{"issue":"12","key":"pone.0291871.ref031","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.14778\/2732977.2732980","article-title":"An experimental comparison of pregel-like graph processing systems","volume":"7","author":"M Han","year":"2014","journal-title":"Proceedings of the VLDB Endowment"},{"key":"pone.0291871.ref032","unstructured":"Karypis G, Kumar V. METIS\u2014Serial Graph Partitioning and Fill-reducing Matrix Ordering;. Available from: https:\/\/github.com\/KarypisLab\/METIS."},{"issue":"3-5","key":"pone.0291871.ref033","doi-asserted-by":"crossref","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community Detection in Graphs","volume":"486","author":"S Fortunato","year":"2009","journal-title":"Physics Reports"},{"key":"pone.0291871.ref034","article-title":"CC-GA: A Clustering Coefficient based Genetic Algorithm for Detecting Communities in Social Networks","author":"A Said","year":"2017","journal-title":"Applied Soft Computing"},{"key":"pone.0291871.ref035","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.aiopen.2021.01.001","article-title":"Graph neural networks: A review of methods and applications","volume":"1","author":"J Zhou","year":"2020","journal-title":"AI Open"},{"key":"pone.0291871.ref036","doi-asserted-by":"crossref","unstructured":"Ju W, Fang Z, Gu Y, Liu Z, Long Q, Qiao Z, et al. A Comprehensive Survey on Deep Graph Representation Learning; 2023.","DOI":"10.1016\/j.neunet.2024.106207"},{"key":"pone.0291871.ref037","doi-asserted-by":"crossref","unstructured":"Kjolstad FB, Snir M. Ghost cell pattern. In: Proceedings of the 2010 Workshop on Parallel Programming Patterns; 2010. p. 1\u20139.","DOI":"10.1145\/1953611.1953615"},{"volume-title":"Using MPI: portable parallel programming with the message-passing interface","year":"1999","author":"W Gropp","key":"pone.0291871.ref038"},{"key":"pone.0291871.ref039","doi-asserted-by":"crossref","DOI":"10.1201\/9781482273991","volume-title":"Mathematical aspects of numerical solution of hyperbolic systems","author":"AG Kulikovskii","year":"2000"},{"volume-title":"Handbook of numerical methods for hyperbolic problems: applied and modern issues","year":"2017","author":"R Abgrall","key":"pone.0291871.ref040"},{"issue":"2","key":"pone.0291871.ref041","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1002\/fld.4262","article-title":"An improved ghost-cell immersed boundary method for compressible flow simulations","volume":"83","author":"C Chi","year":"2017","journal-title":"International Journal for Numerical Methods in Fluids"},{"key":"pone.0291871.ref042","doi-asserted-by":"crossref","unstructured":"Hoefler T, Lumsdaine A. Message progression in parallel computing-to thread or not to thread? In: 2008 IEEE International Conference on Cluster Computing. IEEE; 2008. p. 213\u2013222.","DOI":"10.1109\/CLUSTR.2008.4663774"},{"issue":"8","key":"pone.0291871.ref043","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","article-title":"A bridging model for parallel computation","volume":"33","author":"LG Valiant","year":"1990","journal-title":"Communications of the ACM"},{"key":"pone.0291871.ref044","doi-asserted-by":"crossref","unstructured":"Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM. Distributed graphlab: A framework for machine learning in the cloud. arXiv preprint arXiv:12046078. 2012;.","DOI":"10.14778\/2212351.2212354"},{"issue":"3","key":"pone.0291871.ref045","doi-asserted-by":"crossref","first-page":"38009","DOI":"10.1209\/0295-5075\/89\/38009","article-title":"Discrete-time Markov chain approach to contact-based disease spreading in complex networks","volume":"89","author":"S G\u00f3mez","year":"2010","journal-title":"EPL (Europhysics Letters)"},{"key":"pone.0291871.ref046","article-title":"Epidemics and immunization in scale-free networks","volume-title":"Handbook of Graphs and Networks","author":"R Pastor-Satorras","year":"2003"},{"issue":"4","key":"pone.0291871.ref047","doi-asserted-by":"crossref","first-page":"48003","DOI":"10.1209\/0295-5075\/103\/48003","article-title":"Pair quenched mean-field theory for the susceptible-infected-susceptible model on complex networks","volume":"103","author":"AS Mata","year":"2013","journal-title":"EPL (Europhysics Letters)"},{"key":"pone.0291871.ref048","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks.","author":"M Newman","year":"2018"},{"issue":"1","key":"pone.0291871.ref049","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-020-62523-9","article-title":"Estimating degree\u2013degree correlation and network cores from the connectivity of high\u2013degree nodes in complex networks","volume":"10","author":"R Mondrag\u00f3n","year":"2020","journal-title":"Scientific reports"},{"key":"pone.0291871.ref050","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/978-3-540-44943-0_8","volume-title":"Statistical mechanics of complex networks","author":"M Bogu\u00e1","year":"2003"},{"key":"pone.0291871.ref051","unstructured":"Karypis G, Kumar V. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota Conservancy. 1997;."},{"issue":"14","key":"pone.0291871.ref052","doi-asserted-by":"crossref","first-page":"3200","DOI":"10.1103\/PhysRevLett.86.3200","article-title":"Epidemic spreading in scale-free networks","volume":"86","author":"R Pastor-Satorras","year":"2001","journal-title":"Physical review letters"},{"issue":"2","key":"pone.0291871.ref053","doi-asserted-by":"crossref","first-page":"024308","DOI":"10.1103\/PhysRevE.105.024308","article-title":"Dynamics of epidemics from cavity master equations: Susceptible-infectious-susceptible models","volume":"105","author":"E Ortega","year":"2022","journal-title":"Physical Review E"},{"issue":"3","key":"pone.0291871.ref054","doi-asserted-by":"crossref","first-page":"036603","DOI":"10.1088\/1361-6633\/aa5398","article-title":"Unification of theoretical approaches for epidemic spreading on complex networks","volume":"80","author":"W Wang","year":"2017","journal-title":"Reports on Progress in Physics"},{"key":"pone.0291871.ref055","unstructured":"Wang Y, Chakrabarti D, Wang C, Faloutsos C. Epidemic spreading in real networks: An eigenvalue viewpoint. In: 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings. IEEE; 2003. p. 25\u201334."},{"key":"pone.0291871.ref056","unstructured":"Team M. MPICH\u2014a high performance and widely portable implementation of the Message Passing Interface (MPI) standard;. Available from: https:\/\/www.mpich.org\/."},{"key":"pone.0291871.ref057","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-1-4612-0619-4_7","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"1998"},{"issue":"2","key":"pone.0291871.ref058","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: First steps","volume":"5","author":"PW Holland","year":"1983","journal-title":"Social networks"},{"key":"pone.0291871.ref059","unstructured":"Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection; 2014. http:\/\/snap.stanford.edu\/data."},{"issue":"1","key":"pone.0291871.ref060","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"G Karypis","year":"1998","journal-title":"SIAM Journal on scientific Computing"}],"container-title":["PLOS ONE"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0291871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T17:22:58Z","timestamp":1730222578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0291871"}},"subtitle":[],"editor":[{"given":"Wei","family":"Ju","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,9,29]]},"references-count":60,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2023,9,29]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pone.0291871","relation":{},"ISSN":["1932-6203"],"issn-type":[{"type":"electronic","value":"1932-6203"}],"subject":[],"published":{"date-parts":[[2023,9,29]]}}}