Scalable parallel and distributed simulation of an epidemic on a graph

Area of Science:

• Computational epidemiology
• Network science
• Parallel computing

Background:

• Simulating Markovian SIS epidemics with pairwise interactions on graphs is computationally intensive.
• Existing simulation methods are predominantly sequential, limiting scalability.
• Compartmental models are widely used but often lack efficient parallel solutions.

Purpose of the Study:

• To develop a parallel algorithm for simulating Markovian SIS epidemics on undirected graphs.
• To enable trade-offs between statistical accuracy and computational parallelism.
• To provide a scalable simulation framework for complex network dynamics.

Main Methods:

• Algorithm design for distributed memory systems with limited bandwidth.
• Analysis of algorithmic complexity and the induced dynamical system.
• Experimental validation of scalability and statistical faithfulness.

Main Results:

• The proposed algorithm allows for parallel simulation of SIS epidemics.
• Graph partitioning, especially on community-structured graphs, enhances scalability and faithfulness.
• The algorithm demonstrates significant scalability for large-scale simulations.

Conclusions:

• The developed algorithm offers a scalable approach to epidemic simulation, overcoming limitations of sequential methods.
• This work provides a foundation for advanced epidemic modeling and graph dynamics research.
• Effective graph partitioning is crucial for optimizing parallel simulation performance.