Boolean Dynamics of Kauffman Models with a Scale-Free Network

In a series of articles published in 1986 Derrida, and his colleagues studied two mean field treatments (the quenched and the annealed) for \textit{NK}-Kauffman Networks. Their main results lead to a phase transition curve $ K_c \, 2 \, p_c \left( 1 - p_c \right) = 1 $ ($ 0 < p_c < 1 $) for the critical average connectivity $ K_c $ in terms of the bias $ p_c $ of extracting a "$1$" for the output of the automata. Values of $ K $ bigger than $ K_c $ correspond to the so-called...

We investigate Threshold Random Boolean Networks with $K = 2$ inputs per node, which are equivalent to Kauffman networks, with only part of the canalyzing functions as update functions. According to the simplest consideration these networks should be critical but it turns out that they show a rich variety of behaviors, including periodic and chaotic oscillations. The results are supported by analytical calculations and computer simulations.

Complexity theory as practiced by physicists and computational complexity theory as practiced by computer scientists both characterize how difficult it is to solve complex problems. Here it is shown that the parameters of a specific model can be adjusted so that the problem of finding its global energy minimum is extremely sensitive to small changes in the problem statement. This result has implications not only for studies of the physics of random systems but may also lead t...

We describe systems using Kauffman and similar networks. They are directed funct ioning networks consisting of finite number of nodes with finite number of discr ete states evaluated in synchronous mode of discrete time. In this paper we introduce the notion and phenomenon of `structural tendencies'. Along the way we expand Kauffman networks, which were a synonym of Boolean netw orks, to more than two signal variants and we find a phenomenon during network g rowth which we ...

Boolean networks have been the object of much attention, especially since S. Kauffman proposed them in the 1960's as models for gene regulatory networks. These systems are characterized by being defined on a Boolean state space and by simultaneous updating at discrete time steps. Of particular importance for biological applications are networks in which the indegree for each variable is bounded by a fixed constant, as was stressed by Kauffman in his original papers. An impo...

Boolean networks have been the object of much attention, especially since S. Kauffman proposed them in the 1960's as models for gene regulatory networks. These systems are characterized by being defined on a Boolean state space and by simultaneous updating at discrete time steps. Of particular importance for biological applications are networks in which the indegree for each variable is bounded by a fixed constant, as was stressed by Kauffman in his original papers. An impo...

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$. ...

In the context of growing networks, we introduce a simple dynamical model that unifies the generic features of real networks: scale-free distribution of degree and the small world effect. While the average shortest path length increases logartihmically as in random networks, the clustering coefficient assumes a large value independent of system size. We derive expressions for the clustering coefficient in two limiting cases: random (C ~ (ln N)^2 / N) and highly clustered (C =...

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...

We introduce a numerical method to study random Boolean networks with asynchronous stochas- tic update. Each node in the network of states starts with equal occupation probability and this probability distribution then evolves to a steady state. Nodes left with finite occupation probability determine the attractors and the sizes of their basins. As for synchronous update, the basin entropy grows with system size only for critical networks, where the distribution of attractor ...