  Epidemic processes are common out-of-equilibrium phenomena of broad
interdisciplinary interest. Recently, dynamic message-passing (DMP) has been
proposed as an efficient algorithm for simulating epidemic models on networks,
and in particular for estimating the probability that a given node will become
infectious at a particular time. To date, DMP has been applied exclusively to
models with one-way state changes, as opposed to models like SIS
(susceptible-infectious-susceptible) and SIRS
(susceptible-infectious-recovered-susceptible) where nodes can return to
previously inhabited states. Because many real-world epidemics can exhibit such
recurrent dynamics, we propose a DMP algorithm for complex, recurrent epidemic
models on networks. Our approach takes correlations between neighboring nodes
into account while preventing causal signals from backtracking to their
immediate source, and thus avoids "echo chamber effects" where a pair of
adjacent nodes each amplify the probability that the other is infectious. We
demonstrate that this approach well approximates results obtained from Monte
Carlo simulation and that its accuracy is often superior to the pair
approximation (which also takes second-order correlations into account).
Moreover, our approach is more computationally efficient than the pair
approximation, especially for complex epidemic models: the number of variables
in our DMP approach grows as $2mk$ where $m$ is the number of edges and $k$ is
the number of states, as opposed to $mk^2$ for the pair approximation. We
suspect that the resulting reduction in computational effort, as well as the
conceptual simplicity of DMP, will make it a useful tool in epidemic modeling,
especially for inference tasks where there is a large parameter space to
explore.
