On the number of attractors in random Boolean networks

This is the first of two papers about the structure of Kauffman networks. In this paper we define the relevant elements of random networks of automata, following previous work by Flyvbjerg and Flyvbjerg and Kjaer, and we study numerically their probability distribution in the chaotic phase and on the critical line of the model. A simple approximate argument predicts that their number scales as sqrt(N) on the critical line, while it is linear with N in the chaotic phase and in...

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.

The deterministic dynamics of randomly connected neural networks are studied, where a state of binary neurons evolves according to a discreet-time synchronous update rule. We give a theoretical support that the overlap of systems' states between the current and a previous time develops in time according to a Markovian stochastic process in large networks. This Markovian process predicts how often a network revisits one of previously visited states, depending on the system siz...

We study the properties of the distance between attractors in Random Boolean Networks, a prominent model of genetic regulatory networks. We define three distance measures, upon which attractor distance matrices are constructed and their main statistic parameters are computed. The experimental analysis shows that ordered networks have a very clustered set of attractors, while chaotic networks' attractors are scattered; critical networks show, instead, a pattern with characteri...

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.

We evaluate the probability that a Boolean network returns to an attractor after perturbing h nodes. We find that the return probability as function of h can display a variety of different behaviours, which yields insights into the state-space structure. In addition to performing computer simulations, we derive analytical results for several types of Boolean networks, in particular for Random Boolean Networks. We also apply our method to networks that have been evolved for ro...

We investigate numerically and analytically the formation of the frozen core in critical random Boolean networks with biased functions. We demonstrate that a previously used efficient algorithm for obtaining the frozen core, which starts from the nodes with constant functions, fails when the number of inputs per node exceeds 4. We present computer simulation data for the process of formation of the frozen core and its robustness, and we show that several important features of...

Observing the internal state of the whole system using a small number of sensor nodes is important in analysis of complex networks. Here, we study the problem of determining the minimum number of sensor nodes to discriminate attractors under the assumption that each attractor has at most K noisy nodes. We present exact and approximation algorithms for this minimization problem. The effectiveness of the algorithms is also demonstrated by computational experiments using both sy...

We clarify the effect different sampling methods and weighting schemes have on the statistics of attractors in ensembles of random Boolean networks (RBNs). We directly measure cycle lengths of attractors and sizes of basins of attraction in RBNs using exact enumeration of the state space. In general, the distribution of attractor lengths differs markedly from that obtained by randomly choosing an initial state and following the dynamics to reach an attractor. Our results indi...

For years, we have been building models of gene regulatory networks, where recent advances in molecular biology shed some light on new structural and dynamical properties of such highly complex systems. In this work, we propose a novel timing of updates in Random and Scale-Free Boolean Networks, inspired by recent findings in molecular biology. This update sequence is neither fully synchronous nor asynchronous, but rather takes into account the sequence in which genes affect ...