Large deviations of cascade processes on graphs

Simple models of irreversible dynamical processes such as bootstrap percolation have been successfully applied to describe cascade processes in a large variety of different contexts. However, the problem of analyzing nontypical trajectories, which can be crucial for the understanding of out-of-equilibrium phenomena, is still considered to be intractable in most cases. Here we introduce an efficient method to find and analyze optimized trajectories of cascade processes. We show that for a wide class of irreversible dynamical rules, this problem can be solved efficiently on large-scale systems.

Figure 1

An example of the relation between the progressive models and directed acyclic graphs (DAGs). A graph of six vertices undergoes a LTM with two seeds (vertices marked in red). The weights on all edges are equal to 1 and the threshold is equal to 2 for every node. The result of the dynamics is the DAG on the right. The directions of the edges in the DAG represent the causal relations behind node activations.

Figure 2

Plot of ${\rho }_T$ vs ${\rho }_0$ obtained by solving the time-dependent equations (2) and (3) and the bootstrap percolation equations (4) and (5) on regular random graphs of degree $K=3$ (a) and $K=4$ (b), for threshold $\theta =2$. On increasing the duration $T=5,10,20,50,100$ of the dynamics, the curves obtained using (4) and (5) get closer to the solution (from right to left) of the corresponding bootstrap percolation equations. The insets highlight the regions close to the activation transitions.

Figure 3

Dual factor graph representation for the spread optimization problem. (a) Original graph. (b) Naive factor graph formulation, including small loops. (c) Dual factor graph formulation, with variables nodes $(t_i,t_j)$ and $(t_i,t_k)$ and factor nodes ${\Psi }_i,{\Psi }_j,{\Psi }_k$. The factor ${\Psi }_i$ must ensure, additionally to the dynamical constraint for vertex $i$, that $t_i$ components of $(t_i,t_j)$ and $(t_i,t_k)$ coincide.

Figure 4

(a) Parametric plot of ${\rho }_T$ vs ${\rho }_0$ obtained by solving the belief-propagation equations in the single-link approximation on regular random graphs of degree $K=3$, for threshold $\theta =2$, duration $T=20$, and $\epsilon =0,0.1,0.4,1$. The vertical arrow indicates the minimum density of seeds (${\rho }_0\approx 0.253$) necessary for the total activation obtained by the max-sum algorithm on finite graphs of size $\left|V\right|=10000$. (b) Curves ${\rho }_T\left(\mu \right)$ for $\epsilon =0$ (black dashed line) and $0.4$ (red full line). The latter are obtained by following the upper and lower branches of the solution across the transition. (c) Activation time probability $P\left(t\right)$ obtained by computing the total BP marginals in a dynamics of duration $T=100$, for $\epsilon =0.4$ and different values of $\mu$.

Figure 5

(b) Phase diagram as a function of $\epsilon$ and $\mu$ for $T=20$ in random regular graphs of degree $K=3$ and thresholds $\theta =2$. The curves are obtained in the single-link approximation using a damping procedure to improve the convergence. Black crosses indicate the location of the thermodynamic phase transition (crossing of the free-energy branches) between a full spread (F.S.) and a low spread (L.S.) phase. The upper and lower curves ${\ell }_1$ and ${\ell }_2$ in the same plot indicate the spinodal lines, obtained for increasing values of the damping factor $\alpha$ from 0 to 0.9. (c) shows the hysteresis phenomenon observed in the density of activated nodes ${\rho }_T$ as a function of the chemical potential $\mu$ for $\epsilon =0.4$. The same phenomenon for $\epsilon =0.75$ is shown in (a), where we see that the lack of convergence for $\alpha =0$ is cured by improving the damping to $\alpha =0.9$.

Figure 6

Convergence time (number of iterations) of BP equations for $K=3$, $\theta =2$ in the single-link approximation at $\epsilon =0.4$ as a function of $\mu$ and damping factor $\alpha =0.9$. Different symbols and colors correspond to different values $T$ of the length of the dynamics. At each value of $T$ we reported two different curves (open and full symbols) corresponding to experiments performed increasing or decreasing the values of $\mu$ (in this way following the two branches of solutions).

Figure 7

Convergence time of the BP equations as a function of $T$ for different values of $\mu$ in random regular graphs with $K=3$, $\theta =2$, and $\epsilon =0.4$.

Figure 8

Entropy per site $S/N$ of the solutions of the full spread problem on regular random graphs of degree $K=3$ and threshold $\theta =2$, for $N=30,50,100,\infty$ vs seed density ${\rho }_0$. For each $N$ the upper line corresponds to the normalized binomial distribution (i.e., per site entropy of seeds in the absence of optimization) and the lower one to the entropy per site of fully spreading seeds. Inset: Probability $P$ of randomly selecting a fully spreading set of seeds for the same set of parameters.

Figure 9

(a) Parametric plot of ${\rho }_T$ vs ${\rho }_0$ obtained by solving (11) in the single-link approximation on regular random graphs of degree $K=4$, for threshold $\theta =2$, duration $T=20$, and $\epsilon =0,0.2,0.5$. No improvement with respect to the random case ($\epsilon =0$) is obtained by performing optimization ($\epsilon =0.2,0.5$). The vertical arrow indicates the minimum density of seeds (${\rho }_0\approx 0.094$) necessary for the total activation obtained by the max-sum algorithm on finite graphs of size $\left|V\right|=10000$. (b) Curves ${\rho }_T\left(\mu \right)$ for $\epsilon =0$ (black dashed line) and $0.5$ (red full line). For $\epsilon =0.5$ the BP equations do not converge in a region of values of $\mu$ close to the discontinuous transition. (c) Activation time probability $P\left(t\right)$ obtained by computing the total BP marginals in a dynamics of duration $T=100$, for $\epsilon =0$ and different values of $\mu$ (for $\epsilon =0.5$ we obtain exactly the same behavior).

Figure 10

Convergence time (number of iterations) of BP equations for $K=4$, $\theta =2$ in the single-link approximation at $\epsilon =0.5$ as a function of $\mu$ for different values of $T$.

Figure 11

(b) Phase diagram as a function of $\epsilon$ and $\mu$ for $T=20$ in random regular graphs of degree $K=4$ and thresholds $\theta =2$. Full spread (F.S.) and low spread (L.S.) regions are marked. The curves represent the lines at which BP stops converging in the single-link approximation. The damping procedure (results for $\alpha =0.9$) does not improve the convergence. The inset highlights the behavior for very small values of $\epsilon$. (c) In this region we can still observe the BP equations converging at some nonzero $\epsilon$. (a) The behavior of the density of activated nodes ${\rho }_T$ as a function of the chemical potential $\mu$ for larger values of $\epsilon$ where the BP equations stop converging in a finite interval of values of $\mu$ (shaded area).

Figure 12

(a) Parametric plot of ${\rho }_T$ vs ${\rho }_0$ obtained by solving the BP equations in the single-link approximation on Erdős-Rényi random graphs of average degree $z=5$ (minimum degree $k_{\min }=1$ and maximum degree $k_{\max }=16$), with thresholds ${\theta }_i=\lfloor (k_i+1)/2\rfloor$, duration $T=20$, and $\epsilon =0,0.2$. (b) Curves ${\rho }_T\left(\mu \right)$ for $\epsilon =0$ (black dashed line) and $0.4$ (red full lines). (c) Activation time probability $P\left(t\right)$ obtained by computing the total BP marginals in a dynamics of duration $T=20$, for $\epsilon =0$ (black circles and diamonds) and $0.2$ (red squares and triangles) and different values of $\mu =0.8,1.0$.