Outer-totalistic cellular automata on graphs

Abstract

We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics.

5 pages, 4 figures, 1 table. To appear in Physics Letters A

References in corpus (15)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Specificity and stability in topology of protein networks
• The Yeast Cell-Cycle Network Is Robustly Designed
• Boolean network model predicts cell cycle sequence of fission yeast
• Number and length of attractors in a critical Kauffman model with connectivity one
• Hierarchy Measures in Complex Networks
• Emergence of Complex Dynamics in a Simple Model of Signaling Networks
• Coarse-graining of cellular automata, emergence, and the predictability of complex systems
• Topology regulates pattern formation capacity of binary cellular automata on graphs
• The properties of attractors of canalyzing random Boolean networks
• Similar impact of topological and dynamic noise on complex patterns
• $1/f^{\alpha }$ spectra in elementary cellular automata and fractal signals
• The Regularizing Capacity of Metabolic Networks

Cited by in corpus (10)

• A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications
• Network Automata: Coupling structure and function in real-world networks
• A Comprehensive Taxonomy of Cellular Automata
• Dynamic Networks of Finite State Machines
• Dynamical Phase Transitions in Graph Cellular Automata
• Quenches in the Sherrington-Kirkpatrick model
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Topological determinants of self-sustained activity in a simple model of excitable dynamics on graphs
• Predicting attractors from spectral properties of stylized gene regulatory networks
• Essential metrics for Life on graphs