School of Computer and Communication Sciences, EPFL, Lausanne, Vaud, Switzerland.
PLoS One. 2023 Sep 29;18(9):e0291871. doi: 10.1371/journal.pone.0291871. eCollection 2023.
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.
我们提出了一种算法，用于在固定无向图上模拟具有同质性速率和成对相互作用的马尔可夫 SIS 传染病，假设使用分布式内存模型的并行编程和有限的带宽。这种设置可以表示具有房室模型的广泛类别的模拟任务。现有的此类任务解决方案本质上是顺序的。我们提供了一种创新的解决方案，使得在统计保真度和并行性之间进行权衡成为可能。我们以附录中的伪代码形式提供了该算法的实现。此外，我们还分析了它的算法复杂度及其诱导的动力系统。最后，我们设计了实验来展示其可扩展性和真实性。在我们的实验中，我们发现允许良好分区方案的图结构，例如具有明显社区结构的图，以及正确应用图分区方法，可以提高可扩展性和真实性。我们相信这个算法提供了一种扩展的方法，使研究人员能够以前所未有的规模运行模拟任务。此外，我们相信这个算法为其他领域更高级的传染病模拟和图动力学的扩展奠定了坚实的基础。
