Dynamical criticality: overview and open questions
---
paper_title: Computation at the edge of Chaos: phase transitions and emergent computation

paper_content:

Computations are dynamical systems. The formal study of dynamical systems has revealed a spectrum of behaviors ranging from fixed-point dynamics to fully developed chaos. How does computation--especially universal computation--fit into this spectrum of dynamical behaviors? ::: This thesis addresses the question via the study of Cellular Automata (CA). CA are discrete space/time dynamical systems which (a) exhibit the full spectrum of dynamical behaviors, and (b) are known to support universal computation. Therefore, if we can locate the CA which support computation in the full spectrum of CA dynamics, we may learn a great deal about the general relationship between computation and dynamics. ::: We find that, with an appropriate parameterization of the space of CA, we can order CA dynamical behaviors from fixed-point, through periodic, to chaotic behavior. We also find that there exists a phase-transition in this sequence, located between the periodic and the chaotic rules. The dynamics in the vicinity of this phase-transition are the most complex exhibited anywhere in the spectrum, both qualitatively and quantitatively. These "complex" rules exhibit many of the properties deemed necessary to support computation, and therefore we are able to identify computation with a phase-transition in the space of CA. We are also able to explain the existence of--and relationships between--previously suggested classes of CA behavior (such as the four Wolfram classes) in terms of this phase-transition in the space of CA. ::: The results reported here suggest a general relationship between computation and phase-transitions, especially second-order phase-transitions. When viewed from this perspective, one is able to explain a great deal of the phenomenology of computation, such as the existence of complexity classes, computability classes, and the Halting problem. This view also leads to some new suggestions about the nature and origin of such complex natural phenomena as Life and Intelligence.
---
paper_title: The Theory of critical phenomena

paper_content:

Here is a much-needed basic text that covers a vital area in physics for beginning graduate students.
---
paper_title: Information geometry and phase transitions

paper_content:

The introduction of a metric onto the space of parameters in models in statistical mechanics and beyond gives an alternative perspective on their phase structure. In such a geometrisation, the scalar curvature, R, plays a central role. A non-interacting model has a flat geometry (R=0), while R diverges at the critical point of an interacting one. Here, the information geometry is studied for a number of solvable statistical–mechanical models.
---
paper_title: A universal law of the characteristic return time near thresholds

paper_content:

Dramatic changes at thresholds in multiple stable ecosystems may be irreversible if caused by man. The characteristic return time to an equilibrium increases when a threshold is approached. A universal law for this increase is found, which may be used to forecast the position of a threshold by extrapolation of empirical data. Harvesting experiments on populations are proposed that can be used to verify the method. Preliminary harvesting experiments on rotifer populations display a good agreement with the theory.
---
paper_title: Paths to self-organized criticality

paper_content:

We present a pedagogical introduction to self-organized criticality (SOC), unraveling its connections with nonequilibrium phase transitions. There are several paths from a conventional critical point to SOC. They begin with an absorbing-state phase transition (directed percolation is a familiar example), and impose supervision or driving on the system; two commonly used methods are extremal dynamics, and driving at a rate approaching zero. We illustrate this in sandpiles, where SOC is a consequence of slow driving in a system exhibiting an absorbing-state phase transition with a conserved density. Other paths to SOC, in driven interfaces, the Bak-Sneppen model, and self-organized directed percolation, are also examined. We review the status of experimental realizations of SOC in light of these observations.
---
paper_title: Self-Organized Critical Random Boolean Networks

paper_content:

Centro de Astrobiolog´ia (CAB) INTA-CSIC, Ctra. de Ajalvir km. 4, 28850 Torrej´on de Ardoz, Madrid, Spain(February 1, 2008)Standard Random Boolean Networks display an order-disorder phase transition. We add tothe standard Random Boolean Networks a disconnection rule which couples the control and orderparameters. By this way, the system is driven to the critical line transition. Under the inﬂuence ofperturbations the system point out self-organized critical behavior. Several numerical simulationshave been done and compared with a proposed analytical treatment.
---
paper_title: Relating Fisher information to order parameters

paper_content:

We study phase transitions and relevant order parameters via statistical estimation theory using the Fisher information matrix. The assumptions that we make limit our analysis to order parameters representable as a negative derivative of thermodynamic potential over some thermodynamic variable. Nevertheless, the resulting representation is sufficiently general and explicitly relates elements of the Fisher information matrix to the rate of change in the corresponding order parameters. The obtained relationships allow us to identify, in particular, second-order phase transitions via divergences of individual elements of the Fisher information matrix. A computational study of random Boolean networks supports the derived relationships, illustrating that Fisher information of the magnetization bias (that is, activity level) is peaked in finite-size networks at the critical points, and the maxima increase with the network size. The framework presented here reveals the basic thermodynamic reasons behind similar empirical observations reported previously. The study highlights the generality of Fisher information as a measure that can be applied to a broad range of systems, particularly those where the determination of order parameters is cumbersome.
---
paper_title: Information dynamics at the edge of chaos: Measures, examples, and principles

paper_content:

We survey state-of-the-art methods of information dynamics and briefly discuss some of the popular measures, exemplifying their use in different contexts, including cellular automata, swarming behavior, modular robotics, and random Boolean networks. Several possible principles that generalize the patterns observed in the examples are also suggested. These principles are aimed at providing thermodynamic interpretations of critical phenomena exhibited by many complex Artificial Life systems.
---
paper_title: Fisher Information at the Edge of Chaos in Random Boolean Networks

paper_content:

We study the order-chaos phase transition in random Boolean networks (RBNs), which have been used as models of gene regulatory networks. In particular we seek to characterize the phase diagram in information-theoretic terms, focusing on the effect of the control parameters (activity level and connectivity). Fisher information, which measures how much system dynamics can reveal about the control parameters, offers a natural interpretation of the phase diagram in RBNs. We report that this measure is maximized near the order-chaos phase transitions in RBNs, since this is the region where the system is most sensitive to its parameters. Furthermore, we use this study of RBNs to clarify the relationship between Shannon and Fisher information measures.
---
paper_title: Foundations and formalizations of self-organization

paper_content:

In view of the various streams and directions of the field of self-organization, it is beyond the present introductory chapter to review all the currents of research in the field. Rather, the aim of the present section is to address some of the points judged as most relevant and to provide a discussion of suitable candidate formalisms for the treatment of self-organization. In the author’s opinion, discussing formalisms is not just a vain exercise, but allows one to isolate the essence of the notion one wishes to develop. Thus even if one disagrees with the path taken (as is common in the case of not yet universally agreed upon formal notions), starting from operational formalisms helps to serve as a compass guiding one towards notions suitable for one’s purposes. This is the philosophy of the present chapter. The chapter is structured as follows: in Sect. 2.2, we will present several central conceptual issues relevant in the context of self-organization. Some historical remarks about related relevant work are then done in Sect. 2.3. To illustrate the setting, a brief overview over some classical examples for self-organizing processes is given in Sect. 2.4. In Sects. 2.5 and 2.6, introduces the two main information-theoretic concepts of self-organization that the present chapter aims to discuss. One concept, based on the ϵ-machine formalism by Crutchfield and Shalizi, introduces self-organization as an increase of (statistical) complexity with time. The other concept will suggest measuring self-organization as an increase of mutual correlations (measured by multiinformation) between different components of a system. In Sect. 2.7, finally, important properties of these two measures as well as their distinctive characteristics (namely their power to identify temporal versus compositional self-organization) will be discussed, before Sect. 2.8 gives some conclusive remarks.
---
paper_title: Algorithmic Mapping from Criticality to Self Organized

paper_content:

Probabilistic cellular automata are prototypes of non equilibrium critical phenomena. This class of models includes among others the directed percolation problem (Domany Kinzel model) and the dynamical Ising model. The critical properties of these models are usually obtained by fine-tuning one or more control parameters, as for instance the temperature. We present a method for the parallel evolution of the model for all the values of the control parameter, although its implementation is in general limited to a fixed number of values. This algorithm facilitates the sketching of phase diagrams and can be useful in deriving the critical properties of the model. Since the criticality here emerges from the asymptotic distribution of some quantities, without tuning of parameters, our method is a mapping from a probabilistic cellular automaton with critical behavior to a self organized critical model with the same critical properties.
---
paper_title: The Information Dynamics of Phase Transitions in Random Boolean Networks

paper_content:

Random Boolean Networks (RBNs) are discrete dynamical systems which have been used to model Gene Regulatory Networks. We investigate the well-known phase transition between ordered and chaotic behavior in RBNs from the perspective of the distributed computation conducted by their nodes. We use a recently published framework to characterize the distributed computation in terms of its underlying information dynamics: information storage, information transfer and information modification. We find maximizations in information storage and coherent information transfer on either side of the critical point, allowing us to explain the phase transition in RBNs in terms of the intrinsic distributed computations they are undertaking.
---
paper_title: Biological Information as Set-Based Complexity

paper_content:

The significant and meaningful fraction of all the potential information residing in the molecules and structures of living systems is unknown. Sets of random molecular sequences or identically repeated sequences, for example, would be expected to contribute little or no useful information to a cell. This issue of quantitation of information is important since the ebb and flow of biologically significant information is essential to our quantitative understanding of biological function and evolution. Motivated specifically by these problems of biological information, a class of measures is proposed to quantify the contextual nature of the information in sets of objects, based on Kolmogorov's intrinsic complexity. Such measures discount both random and redundant information and are inherent in that they do not require a defined state space to quantify the information. The maximization of this new measure, which can be formulated in terms of the universal information distance, appears to have several useful and interesting properties, some of which we illustrate with examples.
---
paper_title: Elements of Information Theory

paper_content:

Preface to the Second Edition. Preface to the First Edition. Acknowledgments for the Second Edition. Acknowledgments for the First Edition. 1. Introduction and Preview. 1.1 Preview of the Book. 2. Entropy, Relative Entropy, and Mutual Information. 2.1 Entropy. 2.2 Joint Entropy and Conditional Entropy. 2.3 Relative Entropy and Mutual Information. 2.4 Relationship Between Entropy and Mutual Information. 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information. 2.6 Jensen's Inequality and Its Consequences. 2.7 Log Sum Inequality and Its Applications. 2.8 Data-Processing Inequality. 2.9 Sufficient Statistics. 2.10 Fano's Inequality. Summary. Problems. Historical Notes. 3. Asymptotic Equipartition Property. 3.1 Asymptotic Equipartition Property Theorem. 3.2 Consequences of the AEP: Data Compression. 3.3 High-Probability Sets and the Typical Set. Summary. Problems. Historical Notes. 4. Entropy Rates of a Stochastic Process. 4.1 Markov Chains. 4.2 Entropy Rate. 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph. 4.4 Second Law of Thermodynamics. 4.5 Functions of Markov Chains. Summary. Problems. Historical Notes. 5. Data Compression. 5.1 Examples of Codes. 5.2 Kraft Inequality. 5.3 Optimal Codes. 5.4 Bounds on the Optimal Code Length. 5.5 Kraft Inequality for Uniquely Decodable Codes. 5.6 Huffman Codes. 5.7 Some Comments on Huffman Codes. 5.8 Optimality of Huffman Codes. 5.9 Shannon-Fano-Elias Coding. 5.10 Competitive Optimality of the Shannon Code. 5.11 Generation of Discrete Distributions from Fair Coins. Summary. Problems. Historical Notes. 6. Gambling and Data Compression. 6.1 The Horse Race. 6.2 Gambling and Side Information. 6.3 Dependent Horse Races and Entropy Rate. 6.4 The Entropy of English. 6.5 Data Compression and Gambling. 6.6 Gambling Estimate of the Entropy of English. Summary. Problems. Historical Notes. 7. Channel Capacity. 7.1 Examples of Channel Capacity. 7.2 Symmetric Channels. 7.3 Properties of Channel Capacity. 7.4 Preview of the Channel Coding Theorem. 7.5 Definitions. 7.6 Jointly Typical Sequences. 7.7 Channel Coding Theorem. 7.8 Zero-Error Codes. 7.9 Fano's Inequality and the Converse to the Coding Theorem. 7.10 Equality in the Converse to the Channel Coding Theorem. 7.11 Hamming Codes. 7.12 Feedback Capacity. 7.13 Source-Channel Separation Theorem. Summary. Problems. Historical Notes. 8. Differential Entropy. 8.1 Definitions. 8.2 AEP for Continuous Random Variables. 8.3 Relation of Differential Entropy to Discrete Entropy. 8.4 Joint and Conditional Differential Entropy. 8.5 Relative Entropy and Mutual Information. 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information. Summary. Problems. Historical Notes. 9. Gaussian Channel. 9.1 Gaussian Channel: Definitions. 9.2 Converse to the Coding Theorem for Gaussian Channels. 9.3 Bandlimited Channels. 9.4 Parallel Gaussian Channels. 9.5 Channels with Colored Gaussian Noise. 9.6 Gaussian Channels with Feedback. Summary. Problems. Historical Notes. 10. Rate Distortion Theory. 10.1 Quantization. 10.2 Definitions. 10.3 Calculation of the Rate Distortion Function. 10.4 Converse to the Rate Distortion Theorem. 10.5 Achievability of the Rate Distortion Function. 10.6 Strongly Typical Sequences and Rate Distortion. 10.7 Characterization of the Rate Distortion Function. 10.8 Computation of Channel Capacity and the Rate Distortion Function. Summary. Problems. Historical Notes. 11. Information Theory and Statistics. 11.1 Method of Types. 11.2 Law of Large Numbers. 11.3 Universal Source Coding. 11.4 Large Deviation Theory. 11.5 Examples of Sanov's Theorem. 11.6 Conditional Limit Theorem. 11.7 Hypothesis Testing. 11.8 Chernoff-Stein Lemma. 11.9 Chernoff Information. 11.10 Fisher Information and the Cram-er-Rao Inequality. Summary. Problems. Historical Notes. 12. Maximum Entropy. 12.1 Maximum Entropy Distributions. 12.2 Examples. 12.3 Anomalous Maximum Entropy Problem. 12.4 Spectrum Estimation. 12.5 Entropy Rates of a Gaussian Process. 12.6 Burg's Maximum Entropy Theorem. Summary. Problems. Historical Notes. 13. Universal Source Coding. 13.1 Universal Codes and Channel Capacity. 13.2 Universal Coding for Binary Sequences. 13.3 Arithmetic Coding. 13.4 Lempel-Ziv Coding. 13.5 Optimality of Lempel-Ziv Algorithms. Compression. Summary. Problems. Historical Notes. 14. Kolmogorov Complexity. 14.1 Models of Computation. 14.2 Kolmogorov Complexity: Definitions and Examples. 14.3 Kolmogorov Complexity and Entropy. 14.4 Kolmogorov Complexity of Integers. 14.5 Algorithmically Random and Incompressible Sequences. 14.6 Universal Probability. 14.7 Kolmogorov complexity. 14.9 Universal Gambling. 14.10 Occam's Razor. 14.11 Kolmogorov Complexity and Universal Probability. 14.12 Kolmogorov Sufficient Statistic. 14.13 Minimum Description Length Principle. Summary. Problems. Historical Notes. 15. Network Information Theory. 15.1 Gaussian Multiple-User Channels. 15.2 Jointly Typical Sequences. 15.3 Multiple-Access Channel. 15.4 Encoding of Correlated Sources. 15.5 Duality Between Slepian-Wolf Encoding and Multiple-Access Channels. 15.6 Broadcast Channel. 15.7 Relay Channel. 15.8 Source Coding with Side Information. 15.9 Rate Distortion with Side Information. 15.10 General Multiterminal Networks. Summary. Problems. Historical Notes. 16. Information Theory and Portfolio Theory. 16.1 The Stock Market: Some Definitions. 16.2 Kuhn-Tucker Characterization of the Log-Optimal Portfolio. 16.3 Asymptotic Optimality of the Log-Optimal Portfolio. 16.4 Side Information and the Growth Rate. 16.5 Investment in Stationary Markets. 16.6 Competitive Optimality of the Log-Optimal Portfolio. 16.7 Universal Portfolios. 16.8 Shannon-McMillan-Breiman Theorem (General AEP). Summary. Problems. Historical Notes. 17. Inequalities in Information Theory. 17.1 Basic Inequalities of Information Theory. 17.2 Differential Entropy. 17.3 Bounds on Entropy and Relative Entropy. 17.4 Inequalities for Types. 17.5 Combinatorial Bounds on Entropy. 17.6 Entropy Rates of Subsets. 17.7 Entropy and Fisher Information. 17.8 Entropy Power Inequality and Brunn-Minkowski Inequality. 17.9 Inequalities for Determinants. 17.10 Inequalities for Ratios of Determinants. Summary. Problems. Historical Notes. Bibliography. List of Symbols. Index.
---
paper_title: Real-Time Computation at the Edge of Chaos in Recurrent Neural Networks

paper_content:

Depending on the connectivity, recurrent networks of simple computational units can show very different types of dynamics, ranging from totally ordered to chaotic. We analyze how the type of dynamics (ordered or chaotic) exhibited by randomly connected networks of threshold gates driven by a time-varying input signal depends on the parameters describing the distribution of the connectivity matrix. In particular, we calculate the critical boundary in parameter space where the transition from ordered to chaotic dynamics takes place. Employing a recently developed framework for analyzing real-time computations, we show that only near the critical boundary can such networks perform complex computations on time series. Hence, this result strongly supports conjectures that dynamical systems that are capable of doing complex computational tasks should operate near the edge of chaos, that is, the transition from ordered to chaotic dynamics.
---
paper_title: Basin Entropy in Boolean Network Ensembles

paper_content:

The information processing capacity of a complex dynamical system is reflected in the partitioning of its state space into disjoint basins of attraction, with state trajectories in each basin flowing towards their corresponding attractor. We introduce a novel network parameter, the basin entropy, as a measure of the complexity of information that such a system is capable of storing. By studying ensembles of random Boolean networks, we find that the basin entropy scales with system size only in critical regimes, suggesting that the informationally optimal partition of the state space is achieved when the system is operating at the critical boundary between the ordered and disordered phases.
---
paper_title: Criticality and Parallelism in Combinatorial Optimization

paper_content:

Local search methods constitute one of the most successful approaches to solving large-scale combinatorial optimization problems. The objective of this thesis is to investigate the effects of parallelizing such methods. It will be demonstrated that as parallelism is increased, optimization performance initially improves, but then abruptly degrades to no better than random search beyond a certain point. This transition is surprisingly sharp and will be shown to share many of the characteristics of thermodynamic phase transitions. Its existence will be demonstrated for a family of generalized spin-glass models and the traveling salesman problem. Techniques from statistical mechanics are used to make the correspondence between the physics of phase transitions and the performance of parallelized optimizing systems more precise, demonstrating strong connections between these seemingly unrelated fields. Finite-size scaling is used to characterize size-dependent effects near the transition, and analytical insight is obtained through a mean-field approximation. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
---
paper_title: Metabolic stability and epigenesis in randomly constructed genetic nets

paper_content:

Abstract Proto-organisms probably were randomly aggregated nets of chemical reactions. The hypothesis that contemporary organisms are also randomly constructed molecular automata is examined by modeling the gene as a binary (on-off) device and studying the behavior of large, randomly constructed nets of these binary “genes”. The results suggest that, if each “gene” is directly affected by two or three other “genes”, then such random nets: behave with great order and stability; undergo behavior cycles whose length predicts cell replication time as a function of the number of genes per cell; possess different modes of behavior whose number per net predicts roughly the number of cell types in an organism as a function of its number of genes; and under the stimulus of noise are capable of differentiating directly from any mode of behavior to at most a few other modes of behavior. Cellular differentation is modeled as a Markov chain among the modes of behavior of a genetic net. The possibility of a general theory of metabolic behavior is suggested.
---
paper_title: Fisher Information at the Edge of Chaos in Random Boolean Networks

paper_content:

We study the order-chaos phase transition in random Boolean networks (RBNs), which have been used as models of gene regulatory networks. In particular we seek to characterize the phase diagram in information-theoretic terms, focusing on the effect of the control parameters (activity level and connectivity). Fisher information, which measures how much system dynamics can reveal about the control parameters, offers a natural interpretation of the phase diagram in RBNs. We report that this measure is maximized near the order-chaos phase transitions in RBNs, since this is the region where the system is most sensitive to its parameters. Furthermore, we use this study of RBNs to clarify the relationship between Shannon and Fisher information measures.
---
paper_title: Dynamics, computation, and "the edge of chaos:" A re-examination

paper_content:

In this paper we review previous work and present new work concerning the relationship be tween dynamical systems theory and computation In particular we review work by Langton and Packard on the relationship between dynamical behavior and computational capability in cellular automata CAs We present results from an experiment similar to the one described by Packard which was cited as evidence for the hypothesis that rules capable of performing complex computations are most likely to be found at a phase tran sition between ordered and chaotic behavioral regimes for CAs the edge of chaos Our experiment produced very di erent results from the original experiment and we suggest that the interpretation of the original results is not correct We conclude by discussing general issues related to dynamics computation and the edge of chaos in cellular automata
---
paper_title: Algorithmic Mapping from Criticality to Self Organized

paper_content:

Probabilistic cellular automata are prototypes of non equilibrium critical phenomena. This class of models includes among others the directed percolation problem (Domany Kinzel model) and the dynamical Ising model. The critical properties of these models are usually obtained by fine-tuning one or more control parameters, as for instance the temperature. We present a method for the parallel evolution of the model for all the values of the control parameter, although its implementation is in general limited to a fixed number of values. This algorithm facilitates the sketching of phase diagrams and can be useful in deriving the critical properties of the model. Since the criticality here emerges from the asymptotic distribution of some quantities, without tuning of parameters, our method is a mapping from a probabilistic cellular automaton with critical behavior to a self organized critical model with the same critical properties.
---
paper_title: The EvCA project: A brief history

paper_content:

This article presents a brief history of the Evolving Cellular Automata (EvCA) project. In the EvCA project, a genetic algorithm was used to evolve cellular automata to perform certain (nontrivial) computational tasks, in an effort to gain more insight into the question: “How does evolution produce sophisticated emergent computation in systems composed of simple components limited to local interactions?” Next to providing many interesting results and useful insights, the EvCA project seems to have spawned a whole research area of its own. Here, a brief overview is given of how it all started, developed, and inspired further work. © 2013 Wiley Periodicals, Inc. Complexity 18: 15–19, 2013
---
paper_title: Information at the edge of chaos in fluid neural networks

paper_content:

Abstract Fluid neural networks, defined as neural nets of mobile elements with random activation, are studied by means of several approaches. They are proposed as a theoretical framework for a wide class of systems as insect societies, collectives of robots or the immune system. The critical properties of this model are also analysed, showing the existence of a critical boundary in parameter space where maximum information transfer occurs. In this sense, this boundary is in fact an example of the “edge of chaos” in systems like those described in our approach. Recent experiments with ant colonies seem to confirm our result.
---
paper_title: Computation at the edge of Chaos: phase transitions and emergent computation

paper_content:

Computations are dynamical systems. The formal study of dynamical systems has revealed a spectrum of behaviors ranging from fixed-point dynamics to fully developed chaos. How does computation--especially universal computation--fit into this spectrum of dynamical behaviors? ::: This thesis addresses the question via the study of Cellular Automata (CA). CA are discrete space/time dynamical systems which (a) exhibit the full spectrum of dynamical behaviors, and (b) are known to support universal computation. Therefore, if we can locate the CA which support computation in the full spectrum of CA dynamics, we may learn a great deal about the general relationship between computation and dynamics. ::: We find that, with an appropriate parameterization of the space of CA, we can order CA dynamical behaviors from fixed-point, through periodic, to chaotic behavior. We also find that there exists a phase-transition in this sequence, located between the periodic and the chaotic rules. The dynamics in the vicinity of this phase-transition are the most complex exhibited anywhere in the spectrum, both qualitatively and quantitatively. These "complex" rules exhibit many of the properties deemed necessary to support computation, and therefore we are able to identify computation with a phase-transition in the space of CA. We are also able to explain the existence of--and relationships between--previously suggested classes of CA behavior (such as the four Wolfram classes) in terms of this phase-transition in the space of CA. ::: The results reported here suggest a general relationship between computation and phase-transitions, especially second-order phase-transitions. When viewed from this perspective, one is able to explain a great deal of the phenomenology of computation, such as the existence of complexity classes, computability classes, and the Halting problem. This view also leads to some new suggestions about the nature and origin of such complex natural phenomena as Life and Intelligence.
---
paper_title: On the Complexity of Finite Sequences

paper_content:

A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria.
---
paper_title: Are Cells Really Operating at the Edge of Chaos

paper_content:

It has been suggested that the cells of living organisms are functioning in a near chaotic regime called critical, which offers a trade-off between stability and evolvability. Abstract models for regulatory networks such as Kauffman’s Random Boolean Networks certainly point in that direction. In this work, we applied the essence of these models to investigate the dynamical behavior of two real-life genetic regulatory networks, deduced in two different organisms. Moreover, a novel, more biologically accurate, way individual genes respond to activation signaling is investigated. We perform numerical simulation and successfully identify contexts in which our model’s response can be interpreted as critical, thus most biologically plausible. We also discover that results are comparable in both studied organisms.
---
paper_title: Perturbation avalanches and criticality in gene regulatory networks.

paper_content:

Boolean networks are simplified models of gene regulatory networks. We derive an approximation of the size distribution of perturbation avalanches in Boolean networks based on known results in the theory of branching processes. We show numerically that the approximation works well for different kinds of Boolean networks. It has been suggested that gene regulatory networks may be dynamically critical. To study this, as an application of the presented theory we present a novel method for estimating an order parameter from microarray data. According to the available data and our method, we find that gene regulatory networks appear to be stable and reside near the phase transition between order and chaos.
---
paper_title: Eukaryotic cells are dynamically ordered or critical but not chaotic

paper_content:

Two important theoretical approaches have been developed to generically characterize the relationship between the structure and function of large genetic networks: The continuous approach, based on reaction-kinetics differential equations, and the Boolean approach, based on difference equations and discrete logical rules. These two approaches do not always coincide in their predictions for the same system. Nonetheless, both of them predict that the highly nonlinear dynamics exhibited by genetic regulatory systems can be characterized into two broad regimes, to wit, an ordered regime where the system is robust against perturbations, and a chaotic regime where the system is extremely sensitive to perturbations. It has been a plausible and long-standing hypothesis that genomic regulatory networks of real cells operate in the ordered regime or at the border between order and chaos. This hypothesis is indirectly supported by the robustness and stability observed in the phenotypic traits of living organisms under genetic perturbations. However, there has been no systematic study to determine whether the gene-expression patterns of real cells are compatible with the dynamically ordered regimes predicted by theoretical models. Using the Boolean approach, here we show what we believe to be the first direct evidence that the underlying genetic network of HeLa cells appears to operate either in the ordered regime or at the border between order and chaos but does not appear to be chaotic.
---
paper_title: Why a simple model of genetic regulatory networks describes the distribution of avalanches in gene expression data.

paper_content:

In a previous study it was shown that a simple random Boolean network model, with two input connections per node, can describe with a good approximation (with the exception of the smallest avalanches) the distribution of perturbations in gene expression levels induced by the knock-out of single genes in Saccharomyces cerevisiae. Here we address the reason why such a simple model actually works: we present a theoretical study of the distribution of avalanches and show that, in the case of a Poissonian distribution of outgoing links, their distribution is determined by the value of the Derrida exponent. This explains why the simulations based on the simple model have been effective, in spite of the unrealistic hypothesis about the number of input connections per node. Moreover, we consider here the problem of the choice of an optimal threshold for binarizing continuous data, and we show that tuning its value provides an even better agreement between model and data, valuable also in the important case of the smallest avalanches. Finally, we also discuss the choice of an optimal value of the Derrida parameter in order to match the experimental distributions: our results indicate a value slightly below the critical value 1.
---
paper_title: Genetic network models and statistical properties of gene expression data in knock-out experiments

paper_content:

It is shown here how gene knock-out experiments can be simulated in Random Boolean Networks (RBN), which are well-known simplified models of genetic networks. The results of the simulations are presented and compared with those of actual experiments in S. cerevisiae. RBN with two incoming links per node have been considered, and the Boolean functions have been chosen at random among the set of so-called canalizing functions. ::: ::: Genes are knocked-out (i.e. silenced) one at a time, and the variations in the expression levels of the other genes, with respect to the unperturbed case, are considered. Two important variables are defined: (i) avalanches, which measure the size of the perturbation generated by knocking out a single gene, and (ii) susceptibilities, which measure how often the expression of a given gene is modified in these experiments. ::: ::: A remarkable observation is that the distributions of avalanches and susceptibilities are very robust, i.e. they are very similar in different random networks; this should be contrasted with the distribution of other variables that show a high variance in RBN. ::: ::: Moreover, the distribution of avalanches and susceptibilities of the RBN models are close to those observed in actual experiments performed with S. cerevisiae, where the changes in gene expression levels have been recorded with DNA microarrays. ::: ::: These findings suggest that these distributions might be “generic” properties, common to a wide range of genetic models and real genetic networks. The importance of such generic properties is discussed.
---
paper_title: Being Critical of Criticality in the Brain

paper_content:

Relatively recent work has reported that networks of neurons can produce avalanches of activity whose sizes follow a power law distribution. This suggests that these networks may be operating near a critical point, poised between a phase where activity rapidly dies out and a phase where activity is amplified over time. The hypothesis that the electrical activity of neural networks in the brain is critical is potentially important, as many simulations suggest that information processing functions would be optimized at the critical point. This hypothesis, however, is still controversial. Here we will explain the concept of criticality and review the substantial objections to the criticality hypothesis raised by skeptics. Points and counter points are presented in dialog form.
---
paper_title: Reinventing the sacred: A new view of science, reason and religion.

paper_content:

The article reviews the book "Reinventing the Sacred: A New View of Science, Reason and Religion" by Stuart A. Kauffman.
---
paper_title: EXTENDED CRITICAL SITUATIONS: THE PHYSICAL SINGULARITY OF LIFE PHENOMENA

paper_content:

In this paper, we propose to consider living systems as "coherent critical structures," though extended in space and time, their unity being ensured through global causal relations between levels of organization (integration/regulation). This may be seen as a further contribution to the large amount of work already done on the theme of self-organized criticality. More precisely, our main physical paradigm is provided by the analysis of "phase transitions," as this peculiar form of critical state presents interesting aspect of emergence: the formation of extended correlation lengths and coherence structures, the divergence of some observables with respect to the control parameter(s), etc…. However, the "coherent critical structures" which are the main focus of our work cannot be reduced to existing physical approaches, since phase transitions, in physics, are treated as "singular events," corresponding to a specific well-defined value of the control parameter. Whereas our claim is that in the case of living systems, these coherent critical structures are "extended" and organized in such a way that they persist in space and time. The relation of this concept to the theory of autopoiesis, as well as to various forms of teleonomy, often present in biological analyses, will be also discussed.
---
paper_title: Gene expression dynamics in the macrophage exhibit criticality

paper_content:

Cells are dynamical systems of biomolecular interactions that process information from their environment to mount diverse yet specific responses. A key property of many self-organized systems is that of criticality: a state of a system in which, on average, perturbations are neither dampened nor amplified, but are propagated over long temporal or spatial scales. Criticality enables the coordination of complex macroscopic behaviors that strike an optimal balance between stability and adaptability. It has long been hypothesized that biological systems are critical. Here, we address this hypothesis experimentally for system-wide gene expression dynamics in the macrophage. To this end, we have developed a method, based on algorithmic information theory, to assess macrophage criticality, and we have validated the method on networks with known properties. Using global gene expression data from macrophages stimulated with a variety of Toll-like receptor agonists, we found that macrophage dynamics are indeed critical, providing the most compelling evidence to date for this general principle of dynamics in biological systems.
---
paper_title: The criticality hypothesis: how local cortical networks might optimize information processing

paper_content:

Early theoretical and simulation work independently undertaken by Packard, Langton and Kauffman suggested that adaptability and computational power would be optimized in systems at the 'edge of chaos', at a critical point in a phase transition between total randomness and boring order. This provocative hypothesis has received much attention, but biological experiments supporting it have been relatively few. Here, we review recent experiments on networks of cortical neurons, showing that they appear to be operating near the critical point. Simulation studies capture the main features of these data and suggest that criticality may allow cortical networks to optimize information processing. These simulations lead to predictions that could be tested in the near future, possibly providing further experimental evidence for the criticality hypothesis.
---
paper_title: Living on the edge of chaos: minimally nonlinear models of genetic regulatory dynamics

paper_content:

Linearized catalytic reaction equations (modelling, for example, the dynamics of genetic regulatory networks), under the constraint that expression levels, i.e. molecular concentrations of nucleic material, are positive, exhibit non-trivial dynamical properties, which depend on the average connectivity of the reaction network. In these systems, an inflation of the edge of chaos and multi-stability have been demonstrated to exist. The positivity constraint introduces a nonlinearity, which makes chaotic dynamics possible. Despite the simplicity of such minimally nonlinear systems, their basic properties allow us to understand the fundamental dynamical properties of complex biological reaction networks. We analyse the Lyapunov spectrum, determine the probability of finding stationary oscillating solutions, demonstrate the effect of the nonlinearity on the effective in- and out-degree of the active interaction network, and study how the frequency distributions of oscillatory modes of such a system depend on the average connectivity.
---
paper_title: Universal critical dynamics in high resolution neuronal avalanche data

paper_content:

The tasks of neural computation are remarkably diverse. To function optimally, neuronal networks have been hypothesized to operate near a nonequilibrium critical point. However, experimental evidence for critical dynamics has been inconclusive. Here, we show that the dynamics of cultured cortical networks are critical. We analyze neuronal network data collected at the individual neuron level using the framework of nonequilibrium phase transitions. Among the most striking predictions confirmed is that the mean temporal profiles of avalanches of widely varying durations are quantitatively described by a single universal scaling function. We also show that the data have three additional features predicted by critical phenomena: approximate power law distributions of avalanche sizes and durations, samples in subcritical and supercritical phases, and scaling laws between anomalous exponents.
---
paper_title: Information propagation within the Genetic Network of Saccharomyces cerevisiae

paper_content:

BackgroundA gene network's capacity to process information, so as to bind past events to future actions, depends on its structure and logic. From previous and new microarray measurements in Saccharomyces cerevisiae following gene deletions and overexpressions, we identify a core gene regulatory network (GRN) of functional interactions between 328 genes and the transfer functions of each gene. Inferred connections are verified by gene enrichment.ResultsWe find that this core network has a generalized clustering coefficient that is much higher than chance. The inferred Boolean transfer functions have a mean p-bias of 0.41, and thus similar amounts of activation and repression interactions. However, the distribution of p-biases differs significantly from what is expected by chance that, along with the high mean connectivity, is found to cause the core GRN of S. cerevisiae's to have an overall sensitivity similar to critical Boolean networks. In agreement, we find that the amount of information propagated between nodes in finite time series is much higher in the inferred core GRN of S. cerevisiae than what is expected by chance.ConclusionsWe suggest that S. cerevisiae is likely to have evolved a core GRN with enhanced information propagation among its genes.
---
paper_title: Are biological systems poised at criticality?

paper_content:

Many of life’s most fascinating phenomena emerge from interactions among many elements—many amino acids determine the structure of a single protein, many genes determine the fate of a cell, many neurons are involved in shaping our thoughts and memories. Physicists have long hoped that these collective behaviors could be described using the ideas and methods of statistical mechanics. In the past few years, new, larger scale experiments have made it possible to construct statistical mechanics models of biological systems directly from real data. We review the surprising successes of this “inverse” approach, using examples from families of proteins, networks of neurons, and flocks of birds. Remarkably, in all these cases the models that emerge from the data are poised near a very special point in their parameter space—a critical point. This suggests there may be some deeper theoretical principle behind the behavior of these diverse systems.
---
paper_title: The similarity metric

paper_content:

A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new "normalized information distance," based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric . This theory forms the foundation for a new practical tool. To evidence generality and robustness, we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.
---
paper_title: Critical Dynamics in Genetic Regulatory Networks: Examples from Four Kingdoms

paper_content:

The coordinated expression of the different genes in an organism is essential to sustain functionality under the random external perturbations to which the organism might be subjected. To cope with such external variability, the global dynamics of the genetic network must possess two central properties. (a) It must be robust enough as to guarantee stability under a broad range of external conditions, and (b) it must be flexible enough to recognize and integrate specific external signals that may help the organism to change and adapt to different environments. This compromise between robustness and adaptability has been observed in dynamical systems operating at the brink of a phase transition between order and chaos. Such systems are termed critical. Thus, criticality, a precise, measurable, and well characterized property of dynamical systems, makes it possible for robustness and adaptability to coexist in living organisms. In this work we investigate the dynamical properties of the gene transcription networks reported for S. cerevisiae, E. coli, and B. subtilis, as well as the network of segment polarity genes of D. melanogaster, and the network of flower development of A. thaliana. We use hundreds of microarray experiments to infer the nature of the regulatory interactions among genes, and implement these data into the Boolean models of the genetic networks. Our results show that, to the best of the current experimental data available, the five networks under study indeed operate close to criticality. The generality of this result suggests that criticality at the genetic level might constitute a fundamental evolutionary mechanism that generates the great diversity of dynamically robust living forms that we observe around us.
---
paper_title: Emergent complex neural dynamics

paper_content:

A large repertoire of spatiotemporal activity patterns in the brain is the basis for adaptive behaviour. Understanding the mechanism by which the brain's hundred billion neurons and hundred trillion synapses manage to produce such a range of cortical configurations in a flexible manner remains a fundamental problem in neuroscience. One plausible solution is the involvement of universal mechanisms of emergent complex phenomena evident in dynamical systems poised near a critical point of a second-order phase transition. We review recent theoretical and empirical results supporting the notion that the brain is naturally poised near criticality, as well as its implications for better understanding of the brain.
---
paper_title: Brain complexity born out of criticality

paper_content:

In this essay we elaborate on recent evidence demonstrating the presence of a second order phase transition in human brain dynamics and discuss its consequences for theoretical approaches to brain function. We review early evidence of criticality in brain dynamics at different spatial and temporal scales, and we stress how it was necessary to unify concepts and analysis techniques across scales to introduce the adequate order and control parameters which define the transition. A discussion on the relation between structural vs. dynamical complexity exposes future steps to understand the dynamics of the connectome (structure) from which emerges the cognitome (function).
---
paper_title: Continuous network models of gene expression in knock-out experiments : A preliminary study

paper_content:

In this work we simulate gene knock-out experiments in networks in which variable domains are continuous and variables can vary continuously in time. This model is more realistic than other well-known switching networks such as Boolean Networks. We show that continuous networks can reproduce the results obtained by Random Boolean Networks (RBN). Nevertheless, they do not reproduce the whole range of activation values of actual experimental data. The reasons for this behavior very close to that of RBN could be found in the specific parameter setting chosen and lines for further investigation are discussed.
---
paper_title: Dynamically Critical Systems and Power-Law Distributions: Avalanches Revisited

paper_content:

In this paper we show that a well-known model of genetic regulatory networks, namely that of Random Boolean Networks (RBNs), allows one to study in depth the relationship between two important properties of complex systems, i.e. dynamical criticality and power-law distributions. The study is based upon an analysis of the response of a RBN to permanent perturbations, that may lead to avalanches of changes in activation levels, whose statistical properties are determined by the same parameter that characterizes the dynamical state of the network (ordered, critical or disordered). Under suitable approximations, in the case of large sparse random networks an analytical expression for the probability density of avalanches of different sizes is proposed, and it is shown that for not-too-small avalanches of critical systems it may be approximated by a power law. In the case of small networks the above-mentioned formula does not maintain its validity, because of the phenomenon of self-interference of avalanches, which is also explored by numerical simulations.
---
paper_title: Critical Networks Exhibit Maximal Information Diversity in Structure-Dynamics Relationships

paper_content:

Network structure strongly constrains the range of dynamic behaviors available to a complex system. These system dynamics can be classified based on their response to perturbations over time into two distinct regimes, ordered or chaotic, separated by a critical phase transition. Numerous studies have shown that the most complex dynamics arise near the critical regime. Here we use an information theoretic approach to study structure-dynamics relationships within a unified framework and show that these relationships are most diverse in the critical regime.
---
paper_title: Evolution of Random Networks

paper_content:

We investigate extremal dynamics on random networks. In the quenched case, after a transient time the dynamics is localized in the largest cluster. The activity in the largest cluster is nonergodic, with hot spots of activity typically centered around nodes with a high coordination number. The nonergodicity of the activity opens for models of evolving networks, which can self-organize into fractal geometries. [S0031-9007(98)07126-9]
---
paper_title: Emergent Criticality Through Adaptive Information Processing in Boolean Networks

paper_content:

We study information processing in populations of Boolean networks with evolving connectivity and systematically explore the interplay between the learning capability, robustness, the network topology, and the task complexity. We solve a long-standing open question and find computationally that, for large system sizes $N$, adaptive information processing drives the networks to a critical connectivity $K_{c}=2$. For finite size networks, the connectivity approaches the critical value with a power-law of the system size $N$. We show that network learning and generalization are optimized near criticality, given task complexity and the amount of information provided threshold values. Both random and evolved networks exhibit maximal topological diversity near $K_{c}$. We hypothesize that this supports efficient exploration and robustness of solutions. Also reflected in our observation is that the variance of the values is maximal in critical network populations. Finally, we discuss implications of our results for determining the optimal topology of adaptive dynamical networks that solve computational tasks.
---
paper_title: Dynamical regimes and learning properties of evolved Boolean networks

paper_content:

Boolean networks (BNs) have been mainly considered as genetic regulatory network models and are the subject of notable works in complex systems biology literature. Nevertheless, in spite of their similarities with neural networks, their potential as learning systems has not yet been fully investigated and exploited. In this work, we show that by employing metaheuristic methods we can train BNs to deal with two notable tasks, namely, the problem of controlling the BN's trajectory to match a set of requirements and the density classification problem. These tasks represent two important categories of problems in machine learning. The former is an example of the problems in which a dynamical system has to be designed such that its dynamics satisfies given requirements. The latter one is a representative task in classification. We also analyse the performance of the optimisation techniques as a function of the characteristics of the networks and the objective function and we show that the learning process could influence and be influenced by the BNs' dynamical condition.
---
paper_title: Analysis of attractor distances in Random Boolean Networks

paper_content:

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 characteristics of both ordered and chaotic networks.
---
paper_title: Antichaos and adaptation.

paper_content:

M athematical discoveries are in­ viting changes in biologists' thinking about the origins of order in evolution. All living things are highly ordered systems: they have intri­ cate structures that are maintained and even duplicated through a precise bal­ let of chemical and behavioral activi­ ties. Since Darwin, biologists have seen natural selection as virtually the sole source of that order. But Darwin could not have suspected the existence of self-organization, a re­ cently discovered, innate property of some complex systems. It is possible that biological order reflects in part a spontaneous order on which selection has acted. Selection has molded, but was not compelled to invent, the na­ tive coherence of ontogeny, or biologi­ cal development. Indeed, the capacity to evolve and adapt may itself be an achievement of evolution. The studies supporting these conclu­ sions remain tentative and incomplete. Nevertheless, on the basis of mathe­ matical models for biological systems that exhibit self-organization,. one can make predictions that are consistent with the observed properties of organ­ isms. We may have begun to understand evolution as the marriage of selection and self-organization. To understand how self-organization
---
paper_title: Topological Evolution of Dynamical Networks: Global Criticality from Local Dynamics

paper_content:

We evolve network topology of an asymmetrically connected threshold network by a simple local rewiring rule: quiet nodes grow links, active nodes lose links. This leads to convergence of the average connectivity of the network towards the critical value K(c) = 2 in the limit of large system size N. How this principle could generate self-organization in natural complex systems is discussed for two examples: neural networks and regulatory networks in the genome.
---
paper_title: Information-based fitness and the emergence of criticality in living systems

paper_content:

Empirical evidence suggesting that living systems might operate in the vicinity of critical points, at the borderline between order and disorder, has proliferated in recent years, with examples ranging from spontaneous brain activity to flock dynamics. However, a well-founded theory for understanding how and why interacting living systems could dynamically tune themselves to be poised in the vicinity of a critical point is lacking. Here we use tools from statistical mechanics and information theory to show that complex adaptive or evolutionary systems can be much more efficient in coping with diverse heterogeneous environmental conditions when operating at criticality. Analytical as well as computational evolutionary and adaptive models vividly illustrate that a community of such systems dynamically self-tunes close to a critical state as the complexity of the environment increases while they remain noncritical for simple and predictable environments. A more robust convergence to criticality emerges in coevolutionary and coadaptive setups in which individuals aim to represent other agents in the community with fidelity, thereby creating a collective critical ensemble and providing the best possible tradeoff between accuracy and flexibility. Our approach provides a parsimonious and general mechanism for the emergence of critical-like behavior in living systems needing to cope with complex environments or trying to efficiently coordinate themselves as an ensemble.
---
paper_title: Emergent Criticality from Co-evolution in Random Boolean Networks

paper_content:

The coevolution of network topology and dynamics is studied in an evolutionary Boolean network model that is a simple model of a gene regulatory network. We find that a critical state emerges spontaneously resulting from the interplay between topology and dynamics during the evolution. The final evolved state is shown to be independent of initial conditions. The network appears to be driven to a random Boolean network with uniform in-degree of 2 in the large-network limit. However, for biologically realized network sizes, significant finite-size effects are observed including a broad in-degree distribution and an average in-degree connections between 2 and 3. These results may be important for explaining the properties of gene regulatory networks.
---
paper_title: Adaptive automata based on Darwinian selection

paper_content:

Abstract The principle of natural selection is general, and it is natural to assess its implications for achieving automata with desired dynamical or structural properties. The following issues arise: 1) Appropriate definition of the analogue of “genotype” and “phenotype”. 2) Definition of the ensemble of “possible” automata in which mutational search for desired properties is occurring. 3) Kinematic properties of the “fitness landscape” in the ensemble governing the statistical features of connected walks through fitter variants. 4) Optimal mutation selection strategies given a particular fitness landscape. We assess these questions in two ensembles of automata under selection for one attractor which matches a predetermined “target pattern”. The results are: 1) The continuity of desired dynamical properties differs in the two ensembles. 2) When the best automaton seeds each generation, selection follows a characteristic curve, and asymptotes at automata which approach but fail to achieve the desired attractors. 3) Designation of a subset of the variables as hidden from fitness estimation as part of the target pattern does not improve approach to the target pattern. We discuss limitations in the capacity of mutation selection procedures, and approaches to overcoming them.
---
paper_title: Criticality Is an Emergent Property of Genetic Networks that Exhibit Evolvability

paper_content:

Accumulating experimental evidence suggests that the gene regulatory networks of living organisms operate in the critical phase, namely, at the transition between ordered and chaotic dynamics. Such critical dynamics of the network permits the coexistence of robustness and flexibility which are necessary to ensure homeostatic stability (of a given phenotype) while allowing for switching between multiple phenotypes (network states) as occurs in development and in response to environmental change. However, the mechanisms through which genetic networks evolve such critical behavior have remained elusive. Here we present an evolutionary model in which criticality naturally emerges from the need to balance between the two essential components of evolvability: phenotype conservation and phenotype innovation under mutations. We simulated the Darwinian evolution of random Boolean networks that mutate gene regulatory interactions and grow by gene duplication. The mutating networks were subjected to selection for networks that both (i) preserve all the already acquired phenotypes (dynamical attractor states) and (ii) generate new ones. Our results show that this interplay between extending the phenotypic landscape (innovation) while conserving the existing phenotypes (conservation) suffices to cause the evolution of all the networks in a population towards criticality. Furthermore, the networks produced by this evolutionary process exhibit structures with hubs (global regulators) similar to the observed topology of real gene regulatory networks. Thus, dynamical criticality and certain elementary topological properties of gene regulatory networks can emerge as a byproduct of the evolvability of the phenotypic landscape.
---
paper_title: Punctuated equilibrium and criticality in a simple model of evolution.

paper_content:

A simple and robust model of biological evolution of an ecology of interacting species is introduced. The model self-organizes into a critical steady state with intermittent coevolutionary avalanches of all sizes; i.e., it exhibits punctuated equilibrium'' behavior. This collaborative evolution is much faster than non-cooperative scenarios since no large and coordinated, and hence prohibitively unlikely, mutations are involved.
---
paper_title: Robustness and evolvability in genetic regulatory networks.

paper_content:

Living organisms are robust to a great variety of genetic changes. Gene regulation networks and metabolic pathways self-organize and reaccommodate to make the organism perform with stability and reliability under many point mutations, gene duplications and gene deletions. At the same time, living organisms are evolvable, which means that these kind of genetic perturbations can eventually make the organism acquire new functions and adapt to new environments. It is still an open problem to determine how robustness and evolvability blend together at the genetic level to produce stable organisms that yet can change and evolve. Here we address this problem by studying the robustness and evolvability of the attractor landscape of genetic regulatory network models under the process of gene duplication followed by divergence. We show that an intrinsic property of this kind of networks is that, after the divergence of the parent and duplicate genes, with a high probability the previous phenotypes, encoded in the attractor landscape of the network, are preserved and new ones might appear. The above is true in a variety of network topologies and even for the case of extreme divergence in which the duplicate gene bears almost no relation with its parent. Our results indicate that networks operating close to the so-called "critical regime" exhibit the maximum robustness and evolvability simultaneously.
---
paper_title: The Minimal Complexity of Adapting Agents Increases with Fitness

paper_content:

What is the relationship between the complexity and the fitness of evolved organisms, whether natural or artificial? It has been asserted, primarily based on empirical data, that the complexity of plants and animals increases as their fitness within a particular environment increases via evolution by natural selection. We simulate the evolution of the brains of simple organisms living in a planar maze that they have to traverse as rapidly as possible. Their connectome evolves over 10,000s of generations. We evaluate their circuit complexity, using four information-theoretical measures, including one that emphasizes the extent to which any network is an irreducible entity. We find that their minimal complexity increases with their fitness.
---
paper_title: On the Robustness of the Detection of Relevant Sets in Complex Dynamical Systems

paper_content:

The identification of system’s parts that rule its dynamics and the understanding of its dynamical organisation is a paramount objective in the analysis of complex systems. In previous work we have proposed the Dynamical Cluster Index method, which is based on information-theoretical measures. This method makes it possible to identify the components of a complex system that are relevant for its dynamics as well as their relation in terms of information flow. Complex systems’ organisation is often characterised by intertwined components. The detection of such dynamical structures is a prerequisite for inferring the hierarchical organisation of the system. The method relies on a ranking based on a statistical index, which depends on a reference system (the homogeneous system) generated according to a parametrised sampling procedure. In this paper we address the issue of assessing the robustness of the method against the homogeneous system generation model. The results show that the method is robust and can be reliably applied to the analysis of data from complex system dynamics in general settings, without requiring particular hypotheses.
---
paper_title: Dynamical regimes and learning properties of evolved Boolean networks

paper_content:

Boolean networks (BNs) have been mainly considered as genetic regulatory network models and are the subject of notable works in complex systems biology literature. Nevertheless, in spite of their similarities with neural networks, their potential as learning systems has not yet been fully investigated and exploited. In this work, we show that by employing metaheuristic methods we can train BNs to deal with two notable tasks, namely, the problem of controlling the BN's trajectory to match a set of requirements and the density classification problem. These tasks represent two important categories of problems in machine learning. The former is an example of the problems in which a dynamical system has to be designed such that its dynamics satisfies given requirements. The latter one is a representative task in classification. We also analyse the performance of the optimisation techniques as a function of the characteristics of the networks and the objective function and we show that the learning process could influence and be influenced by the BNs' dynamical condition.
---
paper_title: Exploring the organisation of complex systems through the dynamical interactions among their relevant subsets

paper_content:

Complex systems often show forms of organisation where a clear-cut hierarchy of levels with a well-defined direction of information flow cannot be found. In this paper we propose an information-theoretic method aimed at identifying the dynamically relevant parts of a system along with their relationships, interpreting in such a way the system’s dynamical organisation. The analysis is quite general and can be applied to many dynamical systems. We show here its application to two relevant biological examples, the case of mammalian cell cycle network and of Mitogen Activated Protein Kinase (MAPK) cascade. The result of our analysis shows that the elements of the mammalian cell cycle network act as a single compact group, whereas the MAPK system can be decomposed into two dynamically distinct parts, with asymmetric information flows.
---
paper_title: Information-based fitness and the emergence of criticality in living systems

paper_content:

Empirical evidence suggesting that living systems might operate in the vicinity of critical points, at the borderline between order and disorder, has proliferated in recent years, with examples ranging from spontaneous brain activity to flock dynamics. However, a well-founded theory for understanding how and why interacting living systems could dynamically tune themselves to be poised in the vicinity of a critical point is lacking. Here we use tools from statistical mechanics and information theory to show that complex adaptive or evolutionary systems can be much more efficient in coping with diverse heterogeneous environmental conditions when operating at criticality. Analytical as well as computational evolutionary and adaptive models vividly illustrate that a community of such systems dynamically self-tunes close to a critical state as the complexity of the environment increases while they remain noncritical for simple and predictable environments. A more robust convergence to criticality emerges in coevolutionary and coadaptive setups in which individuals aim to represent other agents in the community with fidelity, thereby creating a collective critical ensemble and providing the best possible tradeoff between accuracy and flexibility. Our approach provides a parsimonious and general mechanism for the emergence of critical-like behavior in living systems needing to cope with complex environments or trying to efficiently coordinate themselves as an ensemble.
---
paper_title: Activities and Sensitivities in Boolean Network Models

paper_content:

We study how the notions of importance of variables in Boolean functions as well as the sensitivities of the functions to changes in these variables impact the dynamical behavior of Boolean networks. The activity of a variable captures its influence on the output of the function and is a measure of that variable's importance. The average sensitivity of a Boolean function captures the smoothness of the function and is related to its internal homogeneity. In a random Boolean network, we show that the expected average sensitivity determines the well-known critical transition curve. We also discuss canalizing functions and the fact that the canalizing variables enjoy higher importance, as measured by their activities, than the noncanalizing variables. Finally, we demonstrate the important role of the average sensitivity in determining the dynamical behavior of a Boolean network.
---
paper_title: The Search for Candidate Relevant Subsets of Variables in Complex Systems

paper_content:

We describe a method to identify relevant subsets of variables, useful to understand the organization of a dynamical system. The variables belonging to a relevant subset should have a strong integration with the other variables of the same relevant subset, and a much weaker interaction with the other system variables. On this basis, extending previous work on neural networks, an information-theoretic measure, the dynamical cluster index, is introduced in order to identify good candidate relevant subsets. The method does not require any previous knowledge of the relationships among the system variables, but relies on observations of their values over time. We show its usefulness in several application domains, including: i random Boolean networks, where the whole network is made of different subnetworks with different topological relationships independent or interacting subnetworks; ii leader-follower dynamics, subject to noise and fluctuations; iii catalytic reaction networks in a flow reactor; iv the MAPK signaling pathway in eukaryotes. The validity of the method has been tested in cases where the data are generated by a known dynamical model and the dynamical cluster index is applied in order to uncover significant aspects of its organization; however, it is important that it can also be applied to time series coming from field data without any reference to a model. Given that it is based on relative frequencies of sets of values, the method could be applied also to cases where the data are not ordered in time. Several indications to improve the scope and effectiveness of the dynamical cluster index to analyze the organization of complex systems are finally given.
---
paper_title: Integrated information increases with fitness in the evolution of animats

paper_content:

One of the hallmarks of biological organisms is their ability to integrate disparate information sources to optimize their behavior in complex environments. How this capability can be quantified and related to the functional complexity of an organism remains a challenging problem, in particular since organismal functional complexity is not well-defined. We present here several candidate measures that quantify information and integration, and study their dependence on fitness as an artificial agent ("animat") evolves over thousands of generations to solve a navigation task in a simple, simulated environment. We compare the ability of these measures to predict high fitness with more conventional information-theoretic processing measures. As the animat adapts by increasing its "fit" to the world, information integration and processing increase commensurately along the evolutionary line of descent. We suggest that the correlation of fitness with information integration and with processing measures implies that high fitness requires both information processing as well as integration, but that information integration may be a better measure when the task requires memory. A correlation of measures of information integration (but also information processing) and fitness strongly suggests that these measures reflect the functional complexity of the animat, and that such measures can be used to quantify functional complexity even in the absence of fitness data.
---

Title: Dynamical Criticality: Overview and Open Questions

Section 1: Introduction
Description 1: Summarize the conjecture regarding dynamical criticality, its significance in living systems, the main results supporting the hypothesis, and the structure of the paper.

Section 2: Criticality and phase transitions
Description 2: Provide preliminary notions on phase transitions and critical phenomena, discussing their properties, significance, and the concept of self-organized criticality (SOC).

Section 3: Computation at the edge of chaos
Description 3: Illustrate the main works and theoretical support for the hypothesis that systems at the phase transition achieve the highest level of computational capability.

Section 4: Critical living systems
Description 4: Discuss the evidence suggesting that biological cells and other biological systems operate in critical regimes and the conjecture that this condition is achieved during evolution for advantages in robustness and adaptability.

Section 5: Discussion
Description 5: Address important issues and open questions about the criticality hypothesis, including different definitions of critical systems, conditions favoring critical systems, and implications for artificial systems.

Section 6: Conclusion
Description 6: Summarize the overview provided in the paper, the significance of dynamical criticality in natural and computational systems, and outline the open questions and future work directions.