Contagion models on networks can be used to describe the spread of information, rumours, opinions, and (more topically) diseases through a population. In the simplest contagion models, each node represents an individual that can be in one of a number of states (e.g. Susceptible, Infected, or Recovered), and the states of the nodes evolve according to specified rules. Even with simple Markovian models of transmission and recovery, it can be difficult to compute the dynamics of contagion on large networks: running simulations can be slow, and the system of master equations is typically too large to be tractable.
One approach to approximating contagion dynamics is to assume that each node state is independent of the neighbouring node states; this leads to a system of ODEs for the node state probabilities (the “first-order approximation”) that always overestimates the speed of infection spread. This approach can be made more sophisticated by introducing pair approximations or higher-order moment closures, but this dramatically increases the size of the system and slows computations. In this talk, I will present some alternative node-based approximations for contagion dynamics. The first of these is exact on trees but will always underestimate the speed of infection spread on a network with loops. I will show how this can be combined with the classic first-order node-based approximation to obtain a node-based approximation that has similar accuracy to the pair approximation, but which is considerably faster to solve.