Superpolynomial growth in the number of attractors in Kauffman networks

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.     

Kauffman networks with threshold functions

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 analytical results are supported by computer simulations.     

The phase diagram of random Boolean networks with nested canalizing functions

We obtain the phase diagram of random Boolean networks with nested canalizing functions. Using the annealed approximation, we obtain the evolution of the number b _t of nodes with value one, and the network sensitivity λ, and compare with numerical simulations of quenched networks. We find that, contrary to what was reported by Kauffman et al. [Proc. Natl. Acad. Sci. 101, 17102 (2004)], these networks have a rich phase diagram, were both the “chaotic" and frozen phases are present, as well as an oscillatory regime of the value of b _t . We argue that the presence of only the frozen phase in the work of Kauffman et al. was due simply to the specific parametrization used, and is not an inherent feature of this class of functions. However, these networks are significantly more stable than the variant where all possible Boolean functions are allowed.     

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

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 power law with network size. We derive these results by generating the networks through a growth process and by calculating lower bounds.     

Percolation and spreading of damage in a simplified Kauffman model

A simplified version of the Kauffman cellular automaton is introduced. As in the usual Kauffman model, there is a transition between a frozen phase and a chaotic phase where damage may spread. We associate the onset of chaos in this model with a percolation transition of certain rules occurring in the model. It seems to be in a different universality class from the usual Kauffman cellular automaton.     

Numerical and Theoretical Studies of Noise Effects in the Kauffman Model

In this work we analyze the stochastic dynamics of the Kauffman model evolving under the influence of noise. By considering the average crossing time between two distinct trajectories, we show that different Kauffman models exhibit a similar kind of behavior, even when the structure of their basins of attraction is quite different. This can be considered as a robust property of these models. We present numerical results for the full range of noise level and obtain approximate analytic expressions for the above crossing time as a function of the noise in the limit cases of small and large noise levels.     

String Theory and the Kauffman Polynomial

We propose a new, precise integrality conjecture for the colored Kauffman polynomial of knots and links inspired by large N dualities and the structure of topological string theory on orientifolds. According to this conjecture, the natural knot invariant in an unoriented theory involves both the colored Kauffman polynomial and the colored HOMFLY polynomial for composite representations, i.e. it involves the full HOMFLY skein of the annulus. The conjecture sheds new light on the relationship between the Kauffman and the HOMFLY polynomials, and it implies for example Rudolph’s theorem. We provide various non-trivial tests of the conjecture and we sketch the string theory arguments that lead to it.     

Modelling one-dimensional driven diffusive systems by the Zero-Range Process

In order to characterize networks in the scale-free network class we study the frequency of cycles of length h that indicate the ordering of network structure and the multiplicity of paths connecting two nodes. In particular we focus on the scaling of the number of cycles with the system size in off-equilibrium scale-free networks. We observe that each off-equilibrium network model is characterized by a particular scaling in general not equal to the scaling found in equilibrium scale-free networks. We claim that this anomalous scaling can occur in real systems and we report the case of the Internet at the Autonomous System Level.Received: 15 January 2004, Published online: 14 May 2004PACS: 89.75.-k Complex systems - 89.75.Hc Networks and genealogical trees     

Two variable link polynomials from quantum supergroups

New two variable link polynomials are constructed corresponding to a one-parameter family of representations of the quantum supergroup U _q [gl(2 | 1)]. Their connection with the Kauffman polynomials is also investigated.     

Damage spreading in a gradient

We propose a new method of analyzing the frozen-chaotic transition in a cellular automaton by propagating damage in a gradient. We obtain estimations forp _c and for the critical exponents for the Kauffman model and the mixture of OR and XOR rules.     

Inhomogenous Kauffman models at the borderline between order and chaos

We study a generalized Kauffman model where the interactions are no longer chosen according to a uniform probability distribution. It is shown that already slight deviations from the uniform distribution can drive the system into the chaotic phase, whereas the orginal model remains strictly in the ordered phase.     

Thermodynamics and topology of disordered systems: Statistics of the random knot diagrams on finite lattices

The statistical properties of random lattice knots, the topology of which is determined by the algebraic topological Jones-Kauffman invariants, was studied by analytical and numerical methods. The Kauffman polynomial invariant of a random knot diagram was represented by a partition function of the Potts model with a random configuration of ferro-and antiferromagnetic bonds, which allowed the probability distribution of the random dense knots on a flat square lattice over topological classes to be studied. A topological class is characterized by the highest power of the Kauffman polynomial invariant and interpreted as the free energy of a q-component Potts spin system for q→∞. It is shown that the highest power of the Kauffman invariant correlates with the minimum energy of the corresponding Potts spin system. The probability of the lattice knot distribution over topological classes was studied by the method of transfer matrices, depending on the type of local junctions and the size of the flat knot diagram. The results obtained are compared to the probability distribution of the minimum energy of a Potts system with random ferro-and antiferromagnetic bonds.     

Comment on a genetic application of square-lattice Kauffman models

Biological genes are argued to have an infinite range of interaction, in agreement with the original Kauffman model and in disagreement with recent modifications which put them on a lattice with nearest neighbor interaction.     

Self-similarity of complex networks and hidden metric spaces

We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e., cycles of length three, plays a crucial role in this framework as a topological reflection of the triangle inequality in the hidden geometry. We prove that a class of hidden variable models with underlying metric spaces are able to accurately reproduce the self-similarity properties that we measured in the real networks. Our findings indicate that hidden geometries underlying these real networks are a plausible explanation for their observed topologies and, in particular, for their self-similarity with respect to the degree-based renormalization.     

Responses of Hodgkin-Huxley Neuronal Systems to Spike-Train Inputs

We investigate responses of the Hodgkin-Huxley globally neuronal systems to periodic spike-train inputs. The firing activities of the neuronal networks show different rhythmic patterns for different parameters. These rhyth- mic patterns can be used to explain cycles of firing in real brain. These activity patterns, average activity and coherence measure are affected by two quantities such as the percentage of excitatory couplings and stimulus intensity, in which the percentage of excitatory couplings is more important than stimulus intensity since the transition phenomenon of average activity comes about.     

Kauffman knot polynomials in classical abelian Chern-Simons field theory

Kauffman knot polynomial invariants are discovered in classical abelian Chern-Simons field theory. A topological invariant t^I(L) is constructed for a link L, where I is the abelian Chern-Simons action and t a formal constant. For oriented knotted vortex lines, t^I satisfies the skein relations of the Kauffman R-polynomial; for un-oriented knotted lines, t^I satisfies the skein relations of the Kauffman bracket polynomial. As an example the bracket polynomials of trefoil knots are computed, and the Jones polynomial is constructed from the bracket polynomial.     

Effects of experimental imperfections on a spin counting experiment

Spin counting NMR is an experimental technique that allows a determination of the size and time evolution of networks of dipolar coupled nuclear spins. This work reports on an average Hamiltonian treatment of two spin counting sequences and compares the efficiency of the two cycles in the presence of flip errors, RF inhomogeneity, phase transients, phase errors, and offset interactions commonly present in NMR experiments. Simulations on small quantum systems performed using the two cycles reveal the effects of pulse imperfections on the resulting multiple quantum spectra, in qualitative agreement with the average Hamiltonian calculations. Experimental results on adamantane are presented, demonstrating differences in the two sequences in the presence of pulse errors.     

Structure of cycles and local ordering in complex networks

We study the properties of quantities aimed at the characterization of grid-like ordering in complex networks. These quantities are based on the global and local behavior of cycles of order four, which are the minimal structures able to identify rectangular clustering. The analysis of data from real networks reveals the ubiquitous presence of a statistically high level of grid-like ordering that is non-trivially correlated with the local degree properties. These observations provide new insights on the hierarchical structure of complex networks.Received: 6 November 2003, Published online: 17 February 2004PACS: 89.75.-k Complex systems - 89.75.Fb Structures and organization in complex systems     

Combinatorial explosion in model gene networks

The explosive growth in knowledge of the genome of humans and other organisms leaves open the question of how the functioning of genes in interacting networks is coordinated for orderly activity. One approach to this problem is to study mathematical properties of abstract network models that capture the logical structures of gene networks. The principal issue is to understand how particular patterns of activity can result from particular network structures, and what types of behavior are possible. We study idealized models in which the logical structure of the network is explicitly represented by Boolean functions that can be represented by directed graphs on n-cubes, but which are continuous in time and described by differential equations, rather than being updated synchronously via a discrete clock. The equations are piecewise linear, which allows significant analysis and facilitates rapid integration along trajectories. We first give a combinatorial solution to the question of how many distinct logical structures exist for n-dimensional networks, showing that the number increases very rapidly with n. We then outline analytic methods that can be used to establish the existence, stability and periods of periodic orbits corresponding to particular cycles on the n-cube. We use these methods to confirm the existence of limit cycles discovered in a sample of a million randomly generated structures of networks of 4 genes. Even with only 4 genes, at least several hundred different patterns of stable periodic behavior are possible, many of them surprisingly complex. We discuss ways of further classifying these periodic behaviors, showing that small mutations (reversal of one or a few edges on the n-cube) need not destroy the stability of a limit cycle. Although these networks are very simple as models of gene networks, their mathematical transparency reveals relationships between structure and behavior, they suggest that the possibilities for orderly dynamics in such networks are extremely rich and they offer novel ways to think about how mutations can alter dynamics. (c) 2000 American Institute of Physics.