Superpolynomial Growth in the Number of Attractors in Kauffman Networks

The Kauffman model describes a particularly simple class of random Boolean networks. Despite the simplicity of the model, it exhibits complex behavior and has been suggested as a model for real world network problems. We introduce a novel approach to analyzing attractors in random Boolean networks, and applying it to Kauffman networks we prove that the average number of attractors grows faster than any power law with system size.

Figure 1

The number of $L$-cycles as functions of the network size for $2\le L\le 6$. The numbers in the figure indicate $L$. Dotted lines are used for values obtained by Monte Carlo summation, with errors comparable to the linewidth. The asymptotes for $N\le 8$ have been included as dashed lines. Their slopes are ${\gamma }_2={\gamma }_3=\frac{1}{3}$, ${\gamma }_4={\gamma }_5=1$, ${\gamma }_6=\frac{7}{3}$, ${\gamma }_7=3$, and ${\gamma }_8=\frac{19}{3}$.

Figure 2

The number of observed attractors (a) and 2-cycles (b) per network as functions of $N$ for different numbers of trajectories $\tau$: 100 (circles), ${10}^3$ (squares), ${10}^4$ (diamonds), and ${10}^5$ (triangles). In (a), the dashed lines have slopes 0.5, 1, and 2. In (b), the solid line shows $⟨C_2{⟩}_N$, the true number of 2-cycles. In the high end of (b), $1\sigma$ corresponds to roughly $20\%$.