Graph Theory and the Evolution of Autocatalytic Networks
Abstract
Description
We give a self-contained introduction to the theory of directed graphs, leading up to the relationship between the Perron-Frobenius eigenvectors of a graph and its autocatalytic sets. Then we discuss a particular dynamical system on a fixed but arbitrary graph, that describes the population dynamics of species whose interactions are determined by the graph. The attractors of this dynamical system are described as a function of graph topology. Finally we consider a dynamical system in which the graph of interactions of the species coevolves with the populations of the species. We show that this system exhibits complex dynamics including self-organization of the network by autocatalytic sets, growth of complexity and structure, and collapse of the network followed by recoveries. We argue that a graph theoretic classification of perturbations of the network is helpful in predicting the future impact of a perturbation over short and medium time scales.
46 pages, 15 figures, to appear in "Handbook of Graphs and Networks", eds, S. Bornholdt and H. G. Schuster, John Wiley and VCH publishers
46 pages, 15 figures, to appear in "Handbook of Graphs and Networks", eds, S. Bornholdt and H. G. Schuster, John Wiley and VCH publishers