Exhaustive percolation on random networks

We consider propagation models that describe the spreading of an attribute, called “damage,” through the nodes of a random network. In some systems, the average fraction of nodes that remain undamaged vanishes in the large system limit, a phenomenon we refer to as exhaustive percolation. We derive scaling law exponents and exact results for the distribution of the number of undamaged nodes, valid for a broad class of random networks at the exhaustive percolation transition and in the exhaustive percolation regime. This class includes processes that determine the set of frozen nodes in random Boolean networks with in-degree distributions that decay sufficiently rapidly with the number of inputs. Connections between our calculational methods and previous studies of percolation beginning from a single initial node are also pointed out. Central to our approach is the observation that key aspects of damage spreading on a random network are fully characterized by a single function, specifying the probability that a given node will be damaged as a function of the fraction of damaged nodes. In addition to our analytical investigations of random networks, we present a numerical example of exhaustive percolation on a directed lattice.

Figure 1

An example of UBA on a lattice, displaying undamaged nodes (dots), initially damaged nodes (filled circles), and nodes damaged during the avalanche (empty circles). Each node has either an OR rule or an AND rule with inputs from its neighbors in the row immediately above the node. The probability for a node to be initially damaged is $\rho =1∕8$ and the probability for obtaining an OR rule is $r=0.3$. Periodic boundary conditions are used and the first row and column are repeated in gray after the last row and column to illustrate the periodic boundary conditions.

Figure 2

The average fraction of undamaged nodes for UBA on a lattice of the type shown in Fig. 1, as a function of the selection probability $p$ for OR rules and the probability $\rho =1∕8$ for initial damage. The lattice has periodic boundary conditions and covers a square that has a side of $10$, ${10}^2$, ${10}^3$, and ${10}^4$ lattice points, respectively, with steeper curves for larger systems. The statistical uncertainty in the estimated mean is less than the linewidth.

Figure 3

Phase diagram for EP on random digraphs, where damage spreads along each directed link with probability $p$ and a node is guaranteed to get damaged in the special case that all of its inputs are connected to damaged nodes. All nodes with zero inputs are initially damaged, and the other nodes are initially damaged with probability $\rho$. The gray area bounded by a solid line shows the region where EP occurs for $\rho =0$ and the dashed lines show the EP transition when $\rho$ has the values $1∕4$, $1∕2$, and $3∕4$, respectively.

Figure 4

The functions (a) $g\left(x\right)\equiv 1-q(1-x)$ and (b) $G\left(x\right)\equiv Q(1-x)$ for three two-inputs rule distributions. All three distributions have $p_0=1∕8$ and $p_2=1$, whereas $p_1$ takes the values $7∕16$, $1∕2$, and $9∕16$. The case that has $p_1=1∕2$ (marked with $=$) is critical with respect to EP and corresponds to the propagation of frozen node values in the original Kauffman model. The other cases $p_1=7∕16$ $(<)$ and $p_1=9∕16$ $(>)$ are subcritical and supercritical, respectively. The dashed line in (a) shows the identity function $x\mapsto x$.

Figure 5

The probability density distribution $N{P}_{\mathrm{n},N}\left(n\right)$ with respect to the fraction of nodes $(n∕N)$ involved in an avalanche. The rule distributions have the same $g\left(x\right)$ as displayed in Fig. 4, showing rule distributions that are $(<)$ subcritical, $(=)$ critical, and $(>)$ supercritical with respect to EP. The displayed networks sizes $N$ are 10 (large dots), 100 (small dots), ${10}^3$ (bold line), ${10}^4$, ${10}^5$, and ${10}^6$ (gradually thinner lines).

Figure 6

A numeric comparison between analytic calculations (black lines) and explicit reductions of random Boolean networks (gray lines). For both cases, the probability density distribution $N{P}_{\mathrm{n},N}\left(n\right)$ is displayed as a function of $n∕N$. The rule distributions have the same $g\left(x\right)$ as displayed in Figs. 4, 5, showing rule distributions that are $(<)$ subcritical, $(=)$ critical, and $(>)$ supercritical with respect to EP. The UBA rule distributions are realized in random Boolean networks by rule distributions with the following respective selection probabilities: $1∕8$, $1∕4$, $5∕8-p_{\mathrm{r}}$, and $p_{\mathrm{r}}$ for a constant rule, a rule that depends on exactly one input, a canalizing rule that depends on two inputs, and a two-input reversible rule. The values of $p_{\mathrm{r}}$ are $(<)$ 0, $(=)$ 1/8, and $(>)$ 1/4. For each rule distribution, ${10}^6$ networks were tested.

Figure 7

Rescaled versions of the probability distributions displayed in Fig. 5. (a) The probability density for the critical case, with respect to the rescaled number of undamaged nodes, $\tilde{u}\equiv ({\alpha }_2∕N{)}^{2∕3}u=u∕(4N^{2∕3})$; (b) the probability distribution $P_{u,N}\left(u\right)$ for the supercritical case without rescaling. The displayed networks sizes $N$ are 10 (large dots), 100 (small dots), ${10}^3$ (bold line), ${10}^4$, ${10}^5$, and ${10}^6$ (gradually thinner lines). The analytically derived asymptotes are shown as dashed lines. In (b), the distributions for networks of sizes ${10}^4$, ${10}^5$, and ${10}^6$ are not plotted because they are indistinguishable from the asymptotic curve.