Number and length of attractors in a critical Kauffman model with connectivity one

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.

We show that the mean number of attractors in a critical Boolean network under asynchronous stochastic update grows like a power law and that the mean size of the attractors increases as a stretched exponential with the system size. This is in strong contrast to the synchronous case, where the number of attractors grows faster than any power law.

The Kauffman model of genetic computation highlights the importance of criticality at the border of order and chaos. But our understanding of its behavior is incomplete, and much of what we do know relies on heuristic arguments. To better understand the model and obtain more rigorous insights, we show that there are fundamental links between the critical Kauffman model and aspects of number theory. Using these connections, we prove that the number of attractors and the mean a...

The Kauffman model is the archetypal model of genetic computation. It highlights the importance of criticality, at which many biological systems seem poised. In a series of advances, researchers have honed in on how the number of attractors in the critical regime grows with network size. But a definitive answer has proved elusive. We prove that, for the critical Kauffman model with connectivity one, the number of attractors grows at least, and at most, as $(2/\!\sqrt{e})^N$. ...

We study the Boolean dynamics of the "quenched" Kauffman models with a directed scale-free network, comparing with that of the original directed random Kauffman networks and that of the directed exponential-fluctuation networks. We have numerically investigated the distributions of the state cycle lengths and its changes as the network size $N$ and the average degree $<k>$ of nodes increase. In the relatively small network ($N \sim 150$), the median, the mean value and the st...

Kauffman net is a dynamical system of logical variables receiving two random inputs and each randomly assigned a boolean function. We show that the attractor and transient lengths exhibit scaleless behavior with power-law distributions over up to ten orders of magnitude. Our results provide evidence for the existence of the "edge of chaos" as a distinct phase between the ordered and chaotic regimes analogous to a critical point in statistical mechanics. The power-law distribu...

The critical Kauffman model with connectivity one is the simplest class of critical Boolean networks. Nevertheless, it exhibits intricate behavior at the boundary of order and chaos. We introduce a formalism for expressing the dynamics of multiple loops as a product of the dynamics of individual loops. Using it, we prove that the number of attractors scales as $2^m$, where $m$ is the number of nodes in loops - as fast as possible, and much faster than previously believed.

We derive mostly analytically the scaling behavior of the number of nonfrozen and relevant nodes in critical Kauffman networks (with two inputs per node) in the thermodynamic limit. By defining and analyzing a stochastic process that determines the frozen core we can prove that the mean number of nonfrozen nodes scales with the network size N as N^{2/3}, with only N^{1/3} nonfrozen nodes having two nonfrozen inputs. We also show the probability distributions for the numbers o...

The evaluation of the number of attractors in Kauffman networks by Samuelsson and Troein is generalized to critical networks with one input per node and to networks with two inputs per node and different probability distributions for update functions. A connection is made between the terms occurring in the calculation and between the more graphic concepts of frozen, nonfrozen and relevant nodes, and relevant components. Based on this understanding, a phenomenological argument...

We derive analytically the scaling behavior in the thermodynamic limit of the number of nonfrozen and relevant nodes in the most general class of critical Kauffman networks for any number of inputs per node, and for any choice of the probability distribution for the Boolean functions. By defining and analyzing a stochastic process that determines the frozen core we can prove that the mean number of nonfrozen nodes in any critical network with more than one input per node scal...