Dynamical Phase Transitions in Graph Cellular Automata
arXiv:2310.15894 · doi:10.1103/PhysRevE.109.044312
Abstract
Discrete dynamical systems can exhibit complex behaviour from the iterative application of straightforward local rules. A famous example are cellular automata whose global dynamics are notoriously challenging to analyze. To address this, we relax the regular connectivity grid of cellular automata to a random graph, which gives the class of graph cellular automata. Using the dynamical cavity method (DCM) and its backtracking version (BDCM), we show that this relaxation allows us to derive asymptotically exact analytical results on the global dynamics of these systems on sparse random graphs. Concretely, we showcase the results on a specific subclass of graph cellular automata with ``conforming non-conformist'' update rules, which exhibit dynamics akin to opinion formation. Such rules update a node's state according to the majority within their own neighbourhood. In cases where the majority leads only by a small margin over the minority, nodes may exhibit non-conformist behaviour. Instead of following the majority, they either maintain their own state, switch it, or follow the minority. For configurations with different initial biases towards one state we identify sharp dynamical phase transitions in terms of the convergence speed and attractor types. From the perspective of opinion dynamics this answers when consensus will emerge and when two opinions coexist almost indefinitely.
arXiv comment15 pages
References in corpus (19)
- Statistical physics of social dynamics
- A message passing approach for general epidemic models
- Contrarian Deterministic Effect: the "Hung Elections Scenario"
- Optimizing spread dynamics on graphs by message passing
- Dynamic message-passing equations for models with unidirectional dynamics
- Large deviations of cascade processes on graphs
- Majority dynamics on trees and the dynamic cavity method
- Outer-totalistic cellular automata on graphs
- The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
- A message-passing approach for threshold models of behavior in networks
- Threshold -voter model
- Dynamic mean-field and cavity methods for diluted Ising systems
- Homogeneous symmetrical threshold model with nonconformity: independence vs. anticonformity
- Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
- Inference of kinetic Ising model on sparse graphs
- Phase transition in the majority rule model with the nonconformist agents
- On the number of limit cycles in diluted neural networks
- A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
- Backtracking Dynamical Cavity Method
Cited by in corpus (6)
- Dynamical Mean-Field Theory of Complex Systems on Sparse Directed Networks
- Quenches in the Sherrington-Kirkpatrick model
- Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
- Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
- Essential metrics for Life on graphs
- Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem