Boolean Dynamics of Kauffman Models with a Scale-Free Network

We apply complex network analysis to the state spaces of random Boolean networks (RBNs). An RBN contains $N$ Boolean elements each with $K$ inputs. A directed state space network (SSN) is constructed by linking each dynamical state, represented as a node, to its temporal successor. We study the heterogeneity of an SSN at both local and global scales, as well as sample-to-sample fluctuations within an ensemble of SSNs. We use in-degrees of nodes as a local topological measure,...

We discuss basic features of emergent complexity in dynamical systems far from equilibrium by focusing on the network structure of their state space. We start by measuring the distributions of avalanche and transient times in Random Boolean Networks (RBNs) and in the \emph{Drosophila} polarity network by exact enumeration. A transient time is the duration of the transient from a starting state to an attractor. An avalanche is a special transient which starts as single Boolean...

We study the organization and dynamics of growing directed networks. These networks are built by adding nodes successively in such a way that each new node has $K$ directed links to the existing ones. The organization of a growing directed network is analyzed in terms of the number of ``descendants'' of each node in the network. We show that the distribution $P(S)$ of the size, $S$, of the descendant cluster is described generically by a power-law, $P(S) \sim S^{-\eta}$, wh...

Structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l, scales with the component size k as l ~ k^{1/2}. Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws ...

Scale-free (SF) networks and small world networks have been found to occur in very diverse contexts. It is this striking universality which makes one look for widely applicable mechanisms which lead to the formation of such networks. In this letter we propose a new mechanism for the construction of SF networks: Evolving networks as interaction networks of systems which are distinguished by their stability if perturbed out of equilibrium. Stability is measured by the largest r...

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

We investigate analytically and numerically the dynamical properties of critical Boolean networks with power-law in-degree distributions. When the exponent of the in-degree distribution is larger than 3, we obtain results equivalent to those obtained for networks with fixed in-degree, e.g., the number of the non-frozen nodes scales as $N^{2/3}$ with the system size $N$. When the exponent of the distribution is between 2 and 3, the number of the non-frozen nodes increases as $...

Synchronization problems in complex networks are very often studied by researchers due to its many applications to various fields such as neurobiology, e-commerce and completion of tasks. In particular, Scale Free networks with degree distribution $P(k)\sim k^{-\lambda}$, are widely used in research since they are ubiquitous in nature and other real systems. In this paper we focus on the surface relaxation growth model in Scale Free networks with $2.5< \lambda <3$, and study ...

Boolean networks are a popular modeling framework in computational biology to capture the dynamics of molecular networks, such as gene regulatory networks. It has been observed that many published models of such networks are defined by regulatory rules driving the dynamics that have certain so-called canalizing properties. In this paper, we investigate the dynamics of a random Boolean network with such properties using analytical methods and simulations. From our simulation...

In this paper, we show our discovery that state-transition networks in several chaotic dynamical systems are "scale-free networks," with a technique to understand a dynamical system as a whole, which we call the analysis for "Discretized-State Transition" (DST) networks; This scale-free nature is found universally in the logistic map, the sine map, the cubic map, the general symmetric map, the sine-circle map, the Gaussian map, and the delayed logistic map. Our findings prove...