Dynamic message-passing approach for kinetic spin models with reversible dynamics

A method to approximately close the dynamic cavity equations for synchronous reversible dynamics on a locally treelike topology is presented. The method builds on (a) a graph expansion to eliminate loops from the normalizations of each step in the dynamics and (b) an assumption that a set of auxilary probability distributions on histories of pairs of spins mainly have dependencies that are local in time. The closure is then effectuated by projecting these probability distributions on $n$-step Markov processes. The method is shown in detail on the level of ordinary Markov processes $\left(n=1\right)$ and outlined for higher-order approximations $\left(n>1\right)$. Numerical validations of the technique are provided for the reconstruction of the transient and equilibrium dynamics of the kinetic Ising model on a random graph with arbitrary connectivity symmetry.

Figure 1

Original graph topologically treelike shown in a factor graph representation in which loops emerge naturally in time when dynamics is considered. Circles illustrate spin variables and squares interactions among them. More specifically, black squares indicate the interaction between one spin and one of its neighbors, i.e., ${\varphi }_{ij}[{\sigma }_i\left(t\right),{\sigma }_j\left(t-1\right)]$, whereas colored squares show the interaction among neighbors of a given spin, i.e., ${\varphi }_j\left[{\left\{{\sigma }_j(t-1)\right\}}_{j\in \partial i}\right]$.

Figure 2

Auxiliary graph obtained from the original one shown in Fig. 1 where the time loops have been removed with a standard procedure. The new variable nodes contain the spin history of two variables which were neighbors in the original graph and factor nodes contain the interactions needed to generate and pass this history, i.e., $\tilde{\mathrm{\Phi }}={\delta }_{X_i^{\left(i{j}_1\right)},\cdots ,X_i}{\prod }_{s=1}^t{w}_i\left({\sigma }_i^s\right|{\sigma }_i^{s-1},{\left\{{\sigma }_j^{s-1}\right\}}_{j\in \partial i})P_0({\sigma }_i,{\left\{{\sigma }_j\right\}}_{j\in \partial i})$. Observe that the $\delta$ function is already summed over in the main text.

Figure 3

Comparison between dynamic message passing algorithm (solid lines) and Monte Carlo simulations (dashed lines) for the evolution of the magnetization $m\left(t\right)$ in an Erdös-Rényi network of $N=5000$ nodes and average connectivity $c=3$. Different colors represent different initial magnetizations $m\left(0\right)$, from the largest (upper line) to the smallest (lower line) according to the legend. (a) Fully asymmetric networks at high temperatures. [(b) and (c)] Partially asymmetric network $\left(\epsilon =0.5\right)$ respectively at high and low temperatures. [(d) and (e)] Fully symmetric network respectively at high and low temperatures. In MC simulations $m\left(t\right)$ is averaged over 5000 samples.

Figure 4

Comparison among the dynamic message passing algorithm (solid lines with $•$ dots), the one-time approximation (solid lines with $⧫$ dots), and the Monte Carlo simulations (solid lines) for the evolution of the magnetization $m\left(t\right)$ in an in an Erdös-Rényi network of $N=5000$ nodes and average connectivity $c=3$. [(a)–(c)] Fully symmetric network at high and low temperatures. [(d) and (e)] Partially symmetric networks with different connectivity symmetry at high and low temperatures. In the MC simulations $m\left(t\right)$ is averaged over 5000 samples.