Scalable parallel and distributed simulation of an epidemic on a graph

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. 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. 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 simulating more advanced epidemic processes and graph dynamics in other fields. Author summaryModeling and simulation are two essential components in many decision-making processes. Many real-world phenomena can be modeled by a spreading process on a graph, such as the gossip protocol in distributed computing, the word-of-mouth effect in marketing, and a contagious disease that spreads among a population. It is not always possible to study these problems analytically, making computer-based simulations the only tool to make predictions about the system under study. Depending on the scale of the system, such simulations can be computationally expensive, especially when a large range of parameters are to be tested. We propose in this article an algorithm to leverage parallel or distributed computing hardware for discrete event simulations and use a simple susceptible-infected-susceptible epidemic to illustrate the key idea of the algorithm. This algorithm allows one to make trade-offs between scalability and accuracy of the simulation. We believe that this algorithm will find wide applications in simulating graph dynamics.