FastSIR Algorithm: A Fast Algorithm for simulation of epidemic spread in large networks by using SIR compartment model
arXiv:1202.1639 · doi:10.1016/j.ins.2013.03.036
Abstract
The epidemic spreading on arbitrary complex networks is studied in SIR (Susceptible Infected Recovered) compartment model. We propose our implementation of a Naive SIR algorithm for epidemic simulation spreading on networks that uses data structures efficiently to reduce running time. The Naive SIR algorithm models full epidemic dynamics and can be easily upgraded to parallel version. We also propose novel algorithm for epidemic simulation spreading on networks called the FastSIR algorithm that has better average case running time than the Naive SIR algorithm. The FastSIR algorithm uses novel approach to reduce average case running time by constant factor by using probability distributions of the number of infected nodes. Moreover, the FastSIR algorithm does not follow epidemic dynamics in time, but still captures all infection transfers. Furthermore, we also propose an efficient recursive method for calculating probability distributions of the number of infected nodes. Average case running time of both algorithms has also been derived and experimental analysis was made on five different empirical complex networks.
arXiv comment8 figures
References in corpus (16)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Epidemic spreading in scale-free networks
- The structure of scientific collaboration networks
- The diameter of the world wide web
- Network robustness and fragility: Percolation on random graphs
- Critical phenomena in complex networks
- The Web of Human Sexual Contacts
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Prediction and predictability of global epidemics: the role of the airline transportation network
- Modeling the Worldwide Spread of Pandemic Influenza: Baseline Case and Containment Interventions
- Thresholds for epidemic spreading in networks
- Epidemic spreading on interconnected networks
- Second look at the spread of epidemics on networks
- Phase diagram of epidemic spreading - unimodal vs. bimodal probability distributions