Exact analytical solution of irreversible binary dynamics on networks

In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), and nodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfy a predetermined condition. We introduce a set of recursive equations to compute the probability of reaching any final state, given an initial state, and a specification of the transition probability function of each node. Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, we also introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves the equations as efficiently as possible in exponential time.

Figure 1

Example of a breath-first exploration of all configurations. The configurations are explored by rows, i.e., by the number of discovered (active) nodes. Nodes are labeled as discovered (blue) or undiscovered (white). Blue arrows indicate possible transitions.

Figure 2

(a) Size distribution of the active components under different dynamic processes: bond percolation, site percolation, and the Watts threshold model. Symbols are the results of ${10}^7$ Monte Carlo simulations, and curves show the exact probability given by our approach [Eq. (6)]. (b) Exact mean size [Eq. (7)] of the final active component for bond and site percolations as a function of the occupation probability $p$. The graph has $N=20$ and 54 directed edges.

Figure 3

Individual response function and activation probabilities. The colors of the nodes are used to show their activation probability, summed over all possible outcomes. Square nodes can make a spontaneous transition [with response function $F_s(p,q)$, see Eq. (9)], while round nodes need active precursors to make a transition [they have the response function $F_w(p,\tau )$, see Eq. (8)]. The parameters of the spontaneously activating nodes are $p=0.4$ and $q=0.3$ for nodes 1, 5, and 11 and $p=0.6$ and $q=0.1$ for nodes 0, 6, and 9. The parameters of the threshold nodes are $p=0.6$ and $\tau =2$ for node 2, 4, 8, and 12 and $p=0.7$ and $\tau =1$ for nodes 3, 7, and 10.

Figure 4

Complete distribution $\mathcal{Q}$ for the every possible configurations of the network, using the dynamics described in Fig. 3. Configurations are grouped together according to the number of active nodes (from 0 to 12) and then ordered with ascending probabilities. Since node 8 is always inactive, the completely active configuration (13 active nodes) has a zero probability and, consequently, is not shown. Gray lines are placed where the number of active nodes increases.

Figure 5

Worst-case complexity of a brute-force solution of the Eqs. (4), and of the accelerated solution Eq. (5b). The complexity is assumed to be proportional to the number of $Q(\mathit{l};{\mathit{A}}_{\mathit{u}})$ required to obtain a solution. The worst case corresponds to an arbitrary dynamics with spontaneous activation on a complete graph of $N$ nodes.