Graph Cellular Automata: The Game of Life on a Network

Almost everyone who studied Computer Science has at some point seen Conway's Game of Life. You start with a grid of cells, each either 'alive' or 'dead', and you apply a very simple set of rules:

• a cell dies (of isolation) if it has less than two living neighbours
• a cell survives if it has two or three living neighbours;
• a cell dies (of overcrowding) if it has more than three living neighbours
• a dead cell springs to life if it has exactly three living neighbours.

That's it.

It doesn't sound like this could lead to anything interesting, but from these basic rules, a whole world of complex structures erupts: with oscillatig patterns that keep going back and forth, self-replicating structures, and even patterns capable of forming computers that can run entire pieces of software!

What has fascinated many mathematicians and computer scientists, is how complex behaviour can emerge from a very simple set of rules. The rules here are super simple. But the complexity emerges from the interaction between the rules and the structure on the grid.

From Lattice to Network

The standard Game of Life lives on a regular two-dimensional lattice. Every cell has a fixed number of eight neighbours. But in the real world, many systems like social networks, the internet, or a collection of AI agents, organise themselves on a network, there the number of neighbours can irregularly connected, densely connected in some places, sparse in other places, and constantly changing.

Can we generalise Conway's Game of Life so that instead of a regular grid, we place cells on the nodes inside a network, where each node can have a different number of neighbours. The update rule maps each cell and its neighbours to the next state. The concept is the same as Conway's Life, but now running on a network that can be connected however we choose: a small-world network, a scale-free hub-and-spoke graph, a lattice with a few long-range shortcuts.

In addition to the rules that determine when a cell changes between dead and alive, we can include extra ruels that defines how the connection between the nodes change. We then get a graph that rewires itself as the system runs. The graph's structure changes as part of the dynamics.

The most well-studied extension of Conway's Game of Life in this direction is called an adaptive network, where two sets of rewiring rules have been studied:

• Active (alive) nodes lose links over time; frozen (dead) nodes acquire new ones.
• Nodes with correlated activity connect to each other; nodes with de-correlated activity disconnect.

[ example of the 2d lattice changing ]

Critical Networks

Rules that are too restrictive produce a dead, frozen network. Rules that are too permissive produce an explosion of activity with no stable structure. The most interesting dynamics live precisely at the boundary.

Stuart Kauffman studied a closely related class of systems in the late 1960s (under the name Random Boolean Networks). His core finding: there is a phase transition between an ordered regime (where almost all perturbations die out and the network freezes into a fixed pattern) and a chaotic regime (where perturbations cascade and amplify indefinitely). Between these two regimes lies the critical point — what Kauffman called the edge of chaos.

Rules that are right at the egde between being too restrictive and too permissive, drive the network automatically towards this criticality — regardless of where you started, the system finds the edge of chaos on its own by repeatedly by applying these rules and restructuring its own connectivity.

This is what complexity researchers sometimes call self-organised criticality,

The Topology Is Part of the Rule

There is a result from the literature on GCAs that I find quietly remarkable. The same birth/survival parameters that produce completely static, boring behaviour on a regular grid can produce rich, class-IV complexity on a scale-free network — and vice versa. You can shift an automaton between Wolfram's complexity classes simply by changing the underlying graph topology, with no change whatsoever to the formal update rule.

This is the key insight that justifies spending time on GCAs: your network structure is part of your rule set, whether you intended it to be or not.

This should sound familiar to anyone who has thought carefully about multi-agent AI systems. The way your agents are wired together — which agents can communicate with which, how information flows through your system, which agents act as hubs and which as leaves — is not an implementation detail. It is a design decision that determines the qualitative character of your system's dynamics, just as much as the prompts and tool descriptions you give each agent.

Kauffman's Edge of Chaos

There is a further result that has significant practical implications: on a homogeneous random graph, you need to carefully tune your rule parameters to sit at this critical boundary. Get the parameters slightly wrong and you fall into the ordered or chaotic phase. But on a scale-free graph — one with a few highly-connected hub nodes surrounded by a sparser periphery, following a power-law degree distribution — the topology itself acts as a stabiliser. A much wider range of rule parameters produces interesting, critical-like behaviour. The hubs create a kind of structural memory that resists both total freezing and total chaos.

If this sounds like an argument for why you should think carefully about the degree distribution of your multi-agent system before worrying about prompt engineering, that is because it is.

What the Physics Tells Us About AI Agent Networks

Behrens, Hudcová, and Zdeborová published a paper in Physical Review E in 2024 that brought asymptotically exact analytical results to the dynamics of GCAs on random graphs. The headline finding: there are sharp dynamical phase transitions in terms of convergence speed and the types of attractors the system reaches. Under some conditions, the network converges rapidly to consensus — a single opinion propagating everywhere. Under other conditions, two or more opinions coexist almost indefinitely, neither winning out.

What does this tell us about a network of AI agents — or, for that matter, a network of humans?

First, it tells us that the convergence behaviour of your system is not primarily a function of what individual agents believe or how they reason. It is a function of how the different nodes in the network are connected. A star topology (one central hub connected to many peripheral nodes) will behave very differently from a small-world graph (mostly local connections with a few long-range shortcuts) even if every individual node runs identical logic. If you want your agent network to reach consensus quickly on factual questions but preserve diversity of opinion on open-ended ones, the structure of who talks to whom is the lever you should be reaching for first.

Second, the existence of sharp phase transitions means that small changes in network structure can produce qualitatively different collective behaviour. There is no smooth interpolation between a system that reaches consensus and one that sustains indefinite disagreement. This is a warning against the intuition that you can incrementally tune your way to the behaviour you want. Sometimes the system tips.

Third, and perhaps most interestingly for AI safety: the adaptive rewiring results suggest that if you give your agents the ability to selectively form and drop connections based on correlated or de-correlated activity, the resulting network will evolve toward a critical point on its own. This is powerful for robustness and adaptive computation — but it also means you are building a system that self-organises toward maximum sensitivity to perturbations.

Graph Neural Cellular Automata and the Machine Learning Bridge

There is a parallel development on the machine learning side that deserves mention. The relationship between Convolutional Neural Networks and standard grid CAs has a direct analogue for graphs: Graph Neural Networks and Graph Cellular Automata sit in exactly the same relationship to each other.

Graph Neural Cellular Automata (GNCA) use GNNs to learn the transition rule rather than hand-specifying it. Instead of asking what rule produces a given behaviour, you ask what rule a network can discover by gradient descent to reproduce a target behaviour. This opens up the possibility of using GCAs to simulate evolutionary games on complex social networks — for instance, Rock-Paper-Scissors dynamics, where the question of which strategy survives depends entirely on the topology of the network and whose strategies each player can observe.

The practical implication for agent networks: rather than hand-designing coordination protocols, you could in principle let the agents learn, through interaction, what local rules of connection and communication produce the collective behaviour you are targeting. This is still mostly research, but it points in a direction that feels important.

Why This Matters

I have been interested in Graph Cellular Automata partly because they are mathematically beautiful and partly because I think they provide a useful conceptual framework for thinking about the networks of AI agents that are rapidly becoming the dominant form of AI deployment.

We tend to think about multi-agent systems in terms of the agents themselves: their capabilities, their prompts, their tools, their context windows. But the GCA literature is a reminder that the structure of the network they live in is at least as important as any of those individual properties. The same agents, wired differently, will produce qualitatively different collective behaviour — and that behaviour can shift discontinuously as the graph structure crosses a phase boundary.

As we build increasingly large and complex networks of AI agents, the question of how to design and monitor the network topology is going to become as important as the question of how to design the individual agents. The physics of GCAs is, I think, one of the more useful bodies of theory we have for thinking about that problem.