Topology regulates pattern formation capacity of binary cellular automata on graphs

We study the effect of topology variation on the dynamic behavior of a system with local update rules. We implement one-dimensional binary cellular automata on graphs with various topologies by formulating two sets of degree-dependent rules, each containing a single parameter. We observe that changes in graph topology induce transitions between different dynamic domains (Wolfram classes) without a formal change in the update rule. Along with topological variations, we study the pattern formation capacities of regular, random, small-world and scale-free graphs. Pattern formation capacity is quantified in terms of two entropy measures, which for standard cellular automata allow a qualitative distinction between the four Wolfram classes. A mean-field model explains the dynamic behavior of random graphs. Implications for our understanding of information transport through complex, network-based systems are discussed.

• Publication year

  2005

• Venue

  Physica A-statistical Mechanics and Its Applications

• Publication date

  2005-02-21

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.physa.2005.02.019arXiv cond-mat/0502509
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Random graphs

  2006cited by this paper
• Dynamical patterns of epidemic outbreaks in complex heterogeneous networks.

  2004cited by this paper
• Hierarchy measures in complex networks.

  2003cited by this paper
• Boolean dynamics of networks with scale-free topology

  2003cited by this paper
• Network-induced nonequilibrium phase transition in the "game of Life".

  2003cited by this paper
• Quiescent string dominance parameter F and classification of one-dimensional cellular automata.

  2003influential reference
• The topology of the transcription regulatory network in the yeast

  2002cited by this paper
• Assortative mixing in networks.

  2002cited by this paper
• Lethality and centrality in protein networks

  2001cited by this paper
• Exploring complex networks

  2001cited by this paper
• The small world of metabolism

  2000cited by this paper
• Epidemic spreading in scale-free networks.

  2000cited by this paper
• The structure of scientific collaboration networks.

  2000cited by this paper
• The large-scale organization of metabolic networks

  2000cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• On the properties of small-world network models

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Computation at the edge of chaos: Phase transitions and emergent computation

  1990cited by this paper
• Statistical mechanics of cellular automata

  1983cited by this paper
• Universality and complexity in cellular automata

  1983cited by this paper
• Metabolic stability and epigenesis in randomly constructed genetic nets.

  1969cited by this paper

• Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method

  2025cites this paper
• Categories of important edges in dynamics on graphs

  2025cites this paper
• Essential metrics for Life on graphs

  2025cites this paper
• Exploring neighborhood variancy for rule search optimization in Life-like Network Automata

  2024cites this paper
• A comprehensive taxonomy of cellular automata

  2024cites this paper
• Predicting attractors from spectral properties of stylized gene regulatory networks.

  2023cites this paper
• A network classification method based on density time evolution patterns extracted from network automata

  2023cites this paper
• A Network Classification Method based on Density Time Evolution Patterns Extracted from Network Automata

  2022influential citation
• Reoccurring neural stem cell divisions in the adult zebrafish telencephalon are sufficient for the emergence of aggregated spatiotemporal patterns

  2020cites this paper
• Dynamics and Complexity of Computrons

  2020cites this paper
• The impact of alphabet size on pattern complexity of maxmin-ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega$$\

  2020cites this paper
• Information Theory in Computational Biology: Where We Stand Today

  2020cites this paper
• Random Expansion Method for the Generation of Complex Cellular Automata

  2020cites this paper
• Adaptive Network Automata Modelling of Complex Networks

  2020cites this paper
• Grundlagen konnektiver komplexer Systeme

  2020cites this paper
• Aggregated spatio-temporal division patterns emerge from reoccurring divisions of neural stem cells

  2020cites this paper
• Modelling the Impact of Transit Media on Information Spreading in an Urban Space Using Cellular Automata

  2019cites this paper
• Estimation of traffic flow changes using networks in networks approaches

  2019cites this paper
• Risk Assessments of Complex Infrastructure Systems Considering Spatial and Temporal Aspects

  2019cites this paper
• Complexity of Maxmin-$$\omega $$ Cellular Automata

  2018cites this paper
• The Complexity of Cellular Automata

  2018cites this paper
• Graph Cellular Automata with Relation-Based Neighbourhoods of Cells for Complex Systems Modelling: A Case of Traffic Simulation

  2017cites this paper
• The role of the interaction network in the emergence of diversity of behavior

  2017cites this paper
• Maxmin-ω : A Simple Deterministic Asynchronous Cellular Automaton Scheme

  2016cites this paper
• Network Analysis Using Spatio-Temporal Patterns

  2016cites this paper
• Dynamics on complex networks: application to abstract micro-economical models

  2014cites this paper
• An Efficient Algorithm for the Detection of Eden

  2013cites this paper
• Maxmin-plus models of asynchronous computation

  2012influential citation
• Cellular Automata on Graphs: Topological Properties of ER Graphs Evolved towards Low-Entropy Dynamics

  2012influential citation
• Building Blocks of Self-Sustained Activity in a Simple Deterministic Model of Excitable Neural Networks

  2012cites this paper
• Dynamic Spread of Social Behavior in Boolean Networks

  2011cites this paper
• Network Dynamics as an Interface between Modeling and Experiment in Systems Biology

  2010cites this paper
• Incorporating Graph Automata into Plant Growth Simulation with Nutrients Transport

  2010cites this paper
• Virtual EP: a simulator of multi-agents-based virtual plant growth in response to environmental heterogeneity

  2010cites this paper
• Interplay between Topology and Dynamics in Excitation Patterns on Hierarchical Graphs

  2009cites this paper
• Determining the Properties of Gene Regulatory Networks from Expression Data

  2009cites this paper
• Dynamical behavior and influence of stochastic noise on certain generalized Boolean networks

  2008cites this paper
• Outer-totalistic cellular automata on graphs

  2008cites this paper
• Network Entropy Based on Topology Configuration and Its Computation to Random Networks

  2008cites this paper
• Linking Structure and Function of Complex Cortical Networks

  2008cites this paper
• Network Automata: Coupling Structure and Function in Dynamic Networks

  2007cites this paper
• The stabilizing effect of noise on the dynamics of a Boolean network

  2007cites this paper
• Performance and Robustness of Cellular Automata Computation on Irregular Networks

  2007cites this paper
• Generalized Automata Networks

  2006influential citation
• Complex Networks: from Graph Theory to Biology

  2006cites this paper
• Creation of a Digital Corpus of Bulgarian Dialects

  2006cites this paper
• Regularizing capacity of metabolic networks.

  2006cites this paper
• 1. Cover Sheet Title: Boolean Approach for the Estimation of the Spatial Spread of H5N1 Avian Influenza between Poultry Flocks in the United States

  2006cites this paper
• Dynamics of three-state excitable units on Poisson vs. power-law random networks

  2006cites this paper
• Similar impact of topological and dynamic noise on complex patterns

  2005cites this paper
• Time evolution of the rule 150 cellular automaton activity from a Fibonacci iteration

  2004cites this paper
• Interplay between topology and dynamics in excitation patterns on hierarchical graphs

  year unknowncites this paper
• International Journal "information Technologies and Knowledge" Vol.2 / 2008 Self-organizing Map and Cellular Automata Combined Technique for Advanced Mesh Generation in Urban and Architectural Design

  year unknowncites this paper