Message-passing solution of epidemic recurrent-state dynamics

Dynamics of network epidemic models can be solved exactly on tree graphs using Dynamic Message-Passing (DMP) approach for unidirectional dynamics, where for each node transition from an inactive status to active status is irreversible. An example of unidirectional dynamics is given by the celebrated Susceptible-Infected-Recovered model. However, many processes are more adequately described by models where a re-infection of nodes is possible, as it happens in the Susceptible-Infected-Susceptible model. We develop a novel hierarchy of DMP algorithms for enabling a practical solution of models with recurrent-state dynamics. We do this by exploiting the sparsity of time trajectories in the number of status changes, where dynamics with a given number of flips can be mapped to unidirectional dynamics with multiple statuses. The resulting algorithm predicts marginal probabilities of activation on tree-like networks for models with a finite number of flips. As a result, our approach is efficient for processes with slow-switching dynamics.