Emergent Criticality through Adaptive Information Processing in Boolean Networks

We study information processing in populations of Boolean networks with evolving connectivity and systematically explore the interplay between the learning capability, robustness, the network topology, and the task complexity. We solve a long-standing open question and find computationally that, for large system sizes $N$, adaptive information processing drives the networks to a critical connectivity $K_c=2$. For finite size networks, the connectivity approaches the critical value with a power law of the system size $N$. We show that network learning and generalization are optimized near criticality, given that the task complexity and the amount of information provided surpass threshold values. Both random and evolved networks exhibit maximal topological diversity near $K_c$. We hypothesize that this diversity supports efficient exploration and robustness of solutions. Also reflected in our observation is that the variance of the fitness values is maximal in critical network populations. Finally, we discuss implications of our results for determining the optimal topology of adaptive dynamical networks that solve computational tasks.

Figure 1

Convergence of the average network connectivity as a function of the GA generations $t_g$. The FA task with $T=4$ and $N=100$. The curves are averaged over 30 evolutionary runs (red), only the 22 best (green), and the 15 best (light blue) populations, respectively. Inset: Scatter plot correlating average $⟨K⟩(t_g)$ and average generalization $⟨G⟩(t_g)$ of a successful population (black) and a suboptimal population (purple).

Figure 2

Finite size scaling of $⟨K⟩$ as a function of $N$ for the three tasks, EO (black), FA (blue), R85 (magenta), and the training sample size $T=4$ (a) and $T=8$ (b). Points represent the data of the evolved networks; lines represent the fits. The finite size scaling for $⟨K⟩$ shows that it scales with a power law as a function of the system size $N$. The dashed lines represent the power-law fit of the form $a*x^b+c$. We favor the data for larger $N$ by weighting the data according to $N/N_{\max }$, where $N_{\max }=500$. The insets show $K_c-c$ as a function of $N$ on a log-log scale.

Figure 3

The conditional probability that evolving populations, where the best mutant reaches maximum fitness (i.e., $f_{\mathrm{best}}=f_{\max }=1$), have average connectivity $⟨K⟩$ shows a sharp peak near $K_c$ (black curve); the same is found for maximum generalization (light blue). Inset: The diversity of evolving populations, quantified in terms of the standard deviation $\sigma (f)$ of fitness distributions, has a maximum near $K_c=2$. All data were sampled over the best 22 out of 30 populations for the full-adder task with $T=4$ and $N=100$.

Figure 4

Near $K_c$, the topology of the network shows maximal variance. The insets show the standard deviation of the topological measures for initial Erdös-Rényi networks (magenta), the evolved networks (black), and the exponential random graphs (blue). The solid lines represent the topological measures in random networks. The dotted line represents the same measure in RBNs.