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.