ID: 0711.2426

Circuits, Attractors and Reachability in Mixed-K Kauffman Networks

November 15, 2007

View on ArXiv
K. A. Hawick, H. A. James, C. J. Scogings
Condensed Matter
Disordered Systems and Neura...

The growth in number and nature of dynamical attractors in Kauffman NK network models are still not well understood properties of these important random boolean networks. Structural circuits in the underpinning graph give insights into the number and length distribution of attractors in the NK model. We use a fast direct circuit enumeration algorithm to study the NK model and determine the growth behaviour of structural circuits. This leads to an explanation and lower bound on the growth properties and the number of attractor loops and a possible K-relationship for circuit number growth with network size N. We also introduce a mixed-K model that allows us to explore <K> between pairs of integer K values in Kauffman-like systems. We find that the circuits' behaviour is a useful metric in identifying phase transitional behaviour around the critical connectivity in that model too. We identify an intermediate phase transition in circuit growth behaviour at K_S approximately 1.5, that is distinct from both the percolation transition at K_P = 1 and the Kauffman transition at K_C = 2. We relate this transition to mutual node reachability within the giant component of nodes.

Similar papers 1

The Number of Attractors in Kauffman Networks

November 1, 2002

90% Match
B. Samuelsson, C. Troein
Disordered Systems and Neura...
Statistical Mechanics

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.

Find SimilarView on arXiv

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

October 22, 2004

88% Match
Barbara Drossel, Tamara Mihaljev, Florian Greil
Disordered Systems and Neura...
Statistical Mechanics

The Kauffman model describes a system of randomly connected nodes with dynamics based on Boolean update functions. Though it is a simple model, it exhibits very complex behavior for "critical" parameter values at the boundary between a frozen and a disordered phase, and is therefore used for studies of real network problems. We prove here that the mean number and mean length of attractors in critical random Boolean networks with connectivity one both increase faster than any ...

Find SimilarView on arXiv

Boolean Dynamics of Kauffman Models with a Scale-Free Network

October 17, 2005

87% Match
Kazumoto Iguchi, Shuichi Kinoshita, Hiroaki S. Yamada
Disordered Systems and Neura...

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

Find SimilarView on arXiv

The Modular Structure of Kauffman Networks

August 28, 1997

86% Match
U. Bastolla, G. Parisi
Disordered Systems and Neura...

This is the second paper of a series of two about the structural properties that influence the asymptotic dynamics of Random Boolean Networks. Here we study the functionally independent clusters in which the relevant elements, introduced and studied in our first paper, are subdivided. We show that the phase transition in Random Boolean Networks can also be described as a percolation transition. The statistical properties of the clusters of relevant elements (that we call modu...

Find SimilarView on arXiv

Power-law Distributions in the Kauffman Net

October 27, 1995

86% Match
Amartya Bhattacharjya, Shoudan Liang
Condensed Matter

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

Find SimilarView on arXiv

Boolean Dynamics with Random Couplings

April 26, 2002

86% Match
Leo Kadanoff, Susan Coppersmith, Maximino Aldana
Adaptation and Self-Organizi...
Cellular Automata and Lattic...

This paper reviews a class of generic dissipative dynamical systems called N-K models. In these models, the dynamics of N elements, defined as Boolean variables, develop step by step, clocked by a discrete time variable. Each of the N Boolean elements at a given time is given a value which depends upon K elements in the previous time step. We review the work of many authors on the behavior of the models, looking particularly at the structure and lengths of their cycles, the...

Find SimilarView on arXiv

On the number of attractors in random Boolean networks

March 21, 2005

85% Match
Barbara Drossel
Statistical Mechanics
Disordered Systems and Neura...

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

Find SimilarView on arXiv

Stability of the Kauffman Model

July 2, 2001

85% Match
S. Bilke, F. Sjunnesson
Statistical Mechanics
Disordered Systems and Neura...

Random Boolean networks, the Kauffman model, are revisited by means of a novel decimation algorithm, which reduces the networks to their dynamical cores. The average size of the removed part, the stable core, grows approximately linearly with N, the number of nodes in the original networks. We show that this can be understood as the percolation of the stability signal in the network. The stability of the dynamical core is investigated and it is shown that this core lacks the ...

Find SimilarView on arXiv

Random sampling vs. exact enumeration of attractors in random Boolean networks

April 24, 2009

84% Match
Andrew Berdahl, Amer Shreim, Vishal Sood, ... , Davidsen Joern
Statistical Mechanics
Disordered Systems and Neura...

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

Find SimilarView on arXiv
T. M. A. Fink, F. C. Sheldon
Molecular Networks
Disordered Systems and Neura...

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