  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.
