  Models of epidemics over networks have become popular, as they describe the
impact of individual behavior on infection spread. However, they come with high
computational complexity, which constitutes a problem in case large-scale
scenarios are considered. This paper presents a discrete-time multi-agent SIR
(Susceptible, Infected, Recovered) model that extends known results in
literature. Based on that, using the novel notion of Contagion Graph, it
proposes a graphbased method derived from Dijkstra's algorithm that allows to
decrease the computational complexity of a simulation. The Contagion Graph can
be also employed as an approximation scheme describing the "mean behavior" of
an epidemic over a network and requiring low computational power. Theoretical
findings are confirmed by randomized large-scale simulation.
