Complex Network Analysis of State Spaces for Random Boolean Networks

Abstract

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, and the path diversity [Phys. Rev. Lett. 98, 198701 (2007)] of an SSN as a global topological measure. RBNs with $2\le K\le 5$ exhibit non-trivial fluctuations at both local and global scales, while K=2 exhibits the largest sample-to-sample, possibly non-self-averaging, fluctuations. We interpret the observed ``multi scale'' fluctuations in the SSNs as indicative of the criticality and complexity of K=2 RBNs. ``Garden of Eden'' (GoE) states are nodes on an SSN that have in-degree zero. While in-degrees of non-GoE nodes for $K>1$ SSNs can assume any integer value between 0 and $2^N$, for K=1 all the non-GoE nodes in an SSN have the same in-degree which is always a power of two.

References in corpus (9)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Scale free networks of earthquakes and aftershocks
• Number and length of attractors in a critical Kauffman model with connectivity one
• Complexity Through Nonextensivity
• Earthquake recurrence as a record breaking process
• On the number of attractors in random Boolean networks
• Network Analysis of the State Space of Discrete Dynamical Systems
• On the Finite Size Scaling in Disordered Systems

Cited by in corpus (3)

• State Concentration Exponent as a Measure of Quickness in Kauffman-type Networks
• Random sampling vs. exact enumeration of attractors in random Boolean networks
• Avalanches, branching ratios, and clustering of attractors in Random Boolean Networks and in the segment polarity network of \emph{Drosophila}