Gabor Timar (Leeds) – Approximation of non-recurrent dynamics on networks

Non-recurrent dynamics - processes in which a system goes through a sequence of states while never returning to a previous state - encompasses a range of important problems, perhaps most notably the spreading of epidemics. We consider a system in which individuals go through a set of states as a consequence of interactions with their neighbours on an underlying network substrate. Predicting the evolution of such processes on a general network is an exponentially difficult problem. On certain classes of networks, however, very precise approximations can be given in the form of message-passing equations, which make use of the fact that non-recurrent dynamics can, in principle, be solved exactly on trees. Here we offer an intuitive interpretation of the message-passing approximation, discuss its connection to the non-backtracking matrix of the given network substrate and explore when (and how) this approximation is expected to fail.