Life on graphs

Life-like rules on networks

Conway's Game of Life counts a cell's live neighbours and answers differently depending on the cell's own state: a dead cell with exactly three live neighbours is born, a live cell with two or three survives, everything else dies or stays dead. Rules of that shape are called outer-totalistic: what happens depends on your own state and on the total of your neighbours, not on which ones. On a grid every cell has eight neighbours, so "exactly three" is a clear instruction. On a network, where one node has two neighbours and the next has twenty, it is not.

The fix, worked out in the paper (code on GitHub), is to count the share rather than the number: ρ, the density of live nodes among a node's neighbours, a number between 0 and 1. Cut the unit interval into r equal pieces and let the rule say, for each piece, whether a dead node is born there and whether a live node survives there. A rule is then a pair of sets of intervals, born B and survive S:

ϕ(s, ρ) = 1 if s = 0 and ρ ∈ ⋃B; 1 if s = 1 and ρ ∈ ⋃S; 0 otherwise.

With r = 9 on a grid of eight neighbours the nine intervals match the nine possible counts 0 to 8 exactly, and Life is back: B = {R₃}, S = {R₂, R₃}. We call the whole family Life-like network automata. There are 2^2r rules for each resolution r, so 262,144 at r = 9.

Two details make this the right definition and not merely a convenient one. First, r must be odd, so that one interval sits in the middle, symmetric around ρ = ½. Second, the intervals are half-open in a mirrored way: below the middle each one includes its left end, [i/r, (i+1)/r[; above the middle each includes its right end, ]i/r, (i+1)/r]; and the middle one is closed at both ends. The dots on the axis of the diagram mark which side each boundary belongs to. This is what makes swapping every on and off a symmetry of the family, as it is for cellular automata: a dead node seeing density ρ becomes a live node seeing 1 − ρ, and that must land in the mirror-image interval, boundaries included. On a network with small degrees a density lands exactly on a boundary all the time, so without the mirroring the symmetry would break.

A rule is written ϕ^r_β,σ, with β the born set read as a binary number, intervali worth 2ⁱ, and σ the same for the survive set. Life is ϕ⁹_8,12: born 2³ = 8, survive 2² + 2³ = 12. Because of the symmetry every rule has an equivalent one that does the same thing with the colours swapped, and some rules are their own equivalent; the readout under the diagram says which. Click any cell of the diagram to change the rule, or type β and σ.

Under the diagram is the mean-field curve for a node of degree k: if a share ρ of all nodes is on and there is no further structure, what share do we expect after one tick? Sum over the possible counts q of live neighbours, each weighted by the binomial share of neighbourhoods that produce it, and the answer follows from the diagram alone. The dashed lines through the diagram show which densities q/k a node of degree k can see, and the circles how common each is. The curve's value at ρ = ½, marked in blue, is the Hamming weight, the share of all inputs that yield a live node. Where the curve crosses the diagonal the density would stay put; where it crosses the anti-diagonal it would flip to its complement. That is all we need to go hunting for a rule.

Things to try. Slide the degree from 4 to 12 with HighLife selected and watch the mean-field curve move while the diagram stays put: which intervals a node can reach depends on its degree, and so does its behaviour, which is the whole point of doing this on networks. Pick the firing squad rule and see a curve that crosses the anti-diagonal at ½ and nowhere else. Set r to 3 and the family shrinks to a handful of threshold rules, one of them rule 150, the parity rule that counts a node's own state too.

The firing squad

The firing squad synchronisation problem: from a random start, get every node to switch on and off in step, all on, all off, all on, for ever. Each node sees only its neighbours; nobody sees the whole. It is a classic for cellular automata, where a line of cells needs at least five states per cell to be solved exactly. With two states and an arbitrary network the honest question is how often a rule manages it.

The usual route is a genetic algorithm: breed rules, keep the winners, and accept a solution you cannot explain. The paper goes bottom-up instead and asks what the mean-field curve of a good solver must look like. Two conditions. The rule must be its own equivalent, since the goal looks the same with the colours swapped. And the curve must lie above the anti-diagonal 1 − ρ to the left of ½ and below it to the right, so that ½ is an unstable balance: every tick then pushes the density further from ½ while flipping it. At degree 8 and r = 9 that leaves 27 candidates out of 262,144, and running those settles on one, ϕ⁹_23,47: born in R₀, R₁, R₂ and R₄, survive in R₀ to R₃ and R₅. Its steep curve sends the density to 0 or 1 within a few ticks, and its high sensitivity to single flips keeps it from freezing in a patchy state.

On the paper's networks, 900 nodes with 3,600 links, rewired from a lattice of eight neighbours, it synchronises 84% of random starts, and up to 93% when the rewiring probability is near 0.32. Two things surprised us. Mean degree 7 fails far more often than 8 or 9. And a fully rewired network does worse than a small world: some shortcuts help, all shortcuts do not. The figure below reproduces the setting at any size up to the paper's: pick a topology, a start, a rule, and press play. The trace shows the share of nodes that are on; a solved run ends in a square wave between 0 and 1, and the run pauses itself once the verdict is in. The trials button repeats the experiment on twenty fresh networks and starts with the same settings.

Things to try. Set the rewiring to 0 for the bare lattice: the squad mostly fails, stuck with islands that flash out of step. Slide it up and watch the success rate climb, then fall again past 0.8. Switch to four neighbours, or to the random and scale-free families, where the degree varies far more. Move the start share towards 0 or 1 and the job gets easier, as it should. Then change the rule with a single click on the diagram and run the trials again: the criteria are strict, and most neighbouring rules do nothing of the kind.

The majority

The majority problem, also called density classification: from a random start, decide whether more nodes were on or off, and have every node settle on the answer. Again nobody sees the whole. And again the mean-field curve says what a solver must look like: instead of flipping the density each tick we want to freeze it, so 0 and 1 must be stable and ½ unstable, which is the firing squad's curve turned upside down. Complementing both sets does exactly that, (B, S) → (B^c, S^c), and turns ϕ⁹_23,47 into ϕ⁹_488,464: a node is born when its neighbourhood is mostly on and survives unless it is mostly off.

The paper only remarks on this, with a warning: the rules it produces often get the answer wrong. The figure shows why. The race to a homogeneous state is quick but local, so a network where 45% of the nodes are on can freeze on the wrong answer in one region and export it. What the rule does reliably is steer the network to some homogeneous state, and which one it picks turns out to say something about the network itself, which is where my more recent work takes it.

Things to try. Start at 40% on and at 60% on, and check the verdict. Then move the start share towards 50% and run twenty trials at each step: the success rate drops to a coin toss well before the majority is thin. Compare the lattice with the random network, and the rule with the plain majority vote you can build by hand, born and survive both filled from ½ upwards.

Defects

The other half of the paper's toolkit is sensitivity: what a single flipped node does. Run the same automaton twice from starts that differ in one node and count, at every tick, the nodes where the two runs disagree. That share is the defect density δ, drawn in blue under the network; the origin wears a thick ring and every node that currently differs a thin one. A rule that damps perturbations lets the rings die out; a chaotic one spreads them over the whole network and keeps them there. On the rule diagram that is the difference between smooth born and survive sets and jagged ones, and the paper turns it into a number, the Boolean sensitivity, that predicts δ well.

The example here is the Morley rule, ϕ⁹_328,52, which the paper uses because its behaviour depends so visibly on the setting: on the lattice it converges gradually, on a small world suddenly, and on a random network sometimes not at all, and both the start share and the rewiring show sharp transitions in between. A single rule, and its phenotype is a property of the network as much as of the rule.

Things to try. Morley on the bare lattice at 50% on, then at 25% and 75%. Add rewiring and look for the point where the defect stops healing. Then switch to the firing squad rule: one flip shifts the moment the squad fires, so for a while the two runs disagree everywhere, and then agree again once both have synchronised, or never, if only one of them did.

Keys once a figure has focus: space plays and pauses, → or PageDown steps, ← or PageUp undoes a tick, r resets to the starting state, f toggles fullscreen. The address bar follows the settings of every figure, so a set-up can be linked.