Damage Spreading and Criticality in Finite Random Dynamical Networks

We systematically study and compare damage spreading at the sparse percolation (SP) limit for random Boolean and threshold networks with perturbations that are independent of the network size $N$. This limit is relevant to information and damage propagation in many technological and natural networks. Using finite-size scaling, we identify a new characteristic connectivity $K_s$, at which the average number of damaged nodes $\overline{d}$, after a large number of dynamical updates, is independent of $N$. Based on marginal damage spreading, we determine the critical connectivity $K_c^{\mathrm{sparse}}(N)$ for finite $N$ at the SP limit and show that it systematically deviates from $K_c$, established by the annealed approximation, even for large system sizes. Our findings can potentially explain the results recently obtained for gene regulatory networks and have important implications for the evolution of dynamical networks that solve specific tasks.

Figure 1

Average Hamming distance (damage) $\overline{d}$ after 200 system updates, averaged over 10 000 randomly generated networks for each value of $\overline{K}$, with 100 different random initial conditions and one-bit perturbed neighbor configurations for each network. For both RBN and RTN, all curves for different $N$ approximately intersect in a characteristic point $K_s$.

Figure 2

Upper panels: $\overline{d}$ as a function of $N$, for different $\overline{K}$. (a) $\overline{K}$ takes values 2.6, 2.0, 1.87, 1.5, and 1.0 (from top to bottom), (b) $\overline{K}$ takes values 2.6, 1.85, 1.725, 1.5, and 1.0 (from top to bottom). Lower panel: Scaling exponents $\gamma (\overline{K})$ as a function of $\overline{K}$, as obtained from fits of Eq. (6) for RBN ($+$) and RTN ($\times$). The straight dashed and dotted lines mark the asymptotes as discussed in the text.

Figure 3

Upper panels: $\overline{d}(\overline{K})$ in semilog scale, as obtained from high-precision simulations near $K_c$ (ensemble size: 50 000 random networks with 100 random initial conditions for each data point, transient time: 5000 updates). Lines are fits of Eq. (8). Lower panels: Scaling exponents $\gamma$ derived from equating Eqs. (6, 8), with corresponding error bars. The intersection with $\gamma =0$ (dashed line) defines $K_s$.

Figure 4

The critical connectivity $K_c^{\mathrm{sparse}}(N)$ in the SP limit as a function of $N$, calculated from Eq. (12). Curves are power-law fits according to Eq. (13), straight dashed lines mark $K_c^{\mathrm{annealed}}$ and $K_s$ for RBN and RTN, respectively.