Kauffman NK Networks

Random Boolean networks that model how complex systems — from gene regulatory networks to brains — can spontaneously self-organize into ordered behaviour without central control.

"Life exists at the edge of chaos." — Stuart Kauffman

1. What Are Kauffman Networks?

In 1969, biologist and complexity theorist Stuart Kauffman asked a profound question: how do the roughly 25,000 genes in a human cell coordinate to produce ~200 distinct cell types, reliably and stably, without any central controller telling them what to do?

His answer was a mathematical model called the NK Boolean network (also written N-K model). It strips biology down to its bare minimum:

Despite the randomness in setup, these networks exhibit remarkably predictable collective behaviour depending on the single parameter K.

NK means

N = number of nodes  ·  K = number of inputs per node

2. Nodes, States, and Boolean Rules

The Node

Each node stores a single bit: 0 (inactive, blue in the explorer) or 1 (active, orange). At each time step every node reads the current states of its K input nodes and looks up its new state in a truth table.

The Truth Table

A node with K inputs has 2K possible input combinations. Its rule assigns a random output (0 or 1) to each combination. This table is fixed for the lifetime of the network — only the states change.

Example: node i with K = 2, inputs from nodes 3 and 7:

Input combo Node 3 Node 7 Output (next state of i)
0001
1100
2010
3111

This particular function happens to be XNOR. In a random network each of the 22K possible Boolean functions is equally likely to be assigned. For K = 2 that is 24 = 16 possible functions per node.

Lookup Index

The explorer (and the Go program) compute the table index by treating the K input states as a binary number: 

idx = input[0]·2⁰ + input[1]·2¹ + ... + input[K-1]·2^(K-1)
next_state[i] = rule[i][idx]
Key point

The wiring and rules are chosen randomly once and then frozen. The only thing that changes over time is the vector of node states.

3. How the Network Evolves

Synchronous Update

At each discrete time step, every node computes its new state from the current states of its inputs, and all nodes flip simultaneously. This is called synchronous (or parallel) update. 

for each node i:
    idx = 0
    for j, input_node in inputs[i]:
        if state[input_node] == 1:
            idx |= (1 << j)
    new_state[i] = rule[i][idx]

state = new_state          # all update at once

State Space

The complete state of the network at any moment is a binary vector of length N. There are exactly 2N possible states. Because the update rule is deterministic and the state space is finite, the network must eventually revisit a state it has already been in.

Distinct states = 2N  ·  For N = 16: 65,536 states  ·  For N = 32: ~4 billion states

Once a previously visited state is encountered, the network has entered an attractor — it will cycle through the same sequence of states forever.

4. Attractors and Basins

What Is an Attractor?

An attractor is a cycle of states that the network enters and never leaves. Two kinds exist:

Fixed-Point Attractor (period 1)

  • The network reaches a single state that maps back to itself
  • Every node's output equals its current input indefinitely
  • Common in ordered networks (K = 1)

Cycle Attractor (period > 1)

  • The network loops through a sequence of 2, 4, 8… states
  • Period = number of distinct states in the cycle
  • Dominant in critical and chaotic networks

Transient

The path from the initial (random) state until the network first enters its attractor is called the transient. Longer transients mean more steps before the cycle is found.

Basin of Attraction

Every initial state eventually flows into some attractor. The set of all initial states that lead to a particular attractor forms its basin of attraction. Large basins mean the attractor is robust — many different starting conditions converge on the same cycle.

Kauffman's biological analogy

Kauffman proposed that cell types correspond to attractors. A stem cell that differentiates into a liver cell or a neuron is following a trajectory in gene-expression state space that terminates at different attractors. The ~200 human cell types correspond to ~200 attractors in a network of ~25,000 genes.

5. Live Demo

Use the controls below to explore a Kauffman network in your browser. Change N and K, step through time, and watch for the attractor (red line in the history grid).

Step: 0
Density: —
Status: ready

Blue cells = node active in transient
Orange cells = node active in attractor
Red line = attractor start

6. The Three Regimes

The single parameter K — the number of inputs per node — determines which of three dramatically different behaviours the network exhibits. This is one of Kauffman's most striking findings.

Ordered — K = 1

  • Most nodes freeze into fixed states
  • Short transients, period-1 attractors dominate
  • Perturbations die out quickly
  • ~√N attractors, each very small
  • Analogous to a crystal: stable but rigid

Critical — K = 2

  • Longest transients relative to N
  • ~√N attractors, average length ~√N
  • Small perturbations sometimes propagate, sometimes die
  • Maximum diversity of behaviour
  • Kauffman's "edge of chaos" hypothesis

Chaotic — K ≥ 3

  • Exponentially long transients (in N)
  • Exponentially many attractors
  • Tiny perturbations avalanche through the whole network
  • Effectively unpredictable
  • Analogous to a gas: flexible but structureless

Quantitative Comparison

Regime K Number of attractors Average attractor length Damage spreading
Ordered 1 O(√N) O(1) — mostly fixed points Contracts, dies out
Critical 2 O(√N) O(√N) Propagates on average to 1 node
Chaotic ≥ 3 Exponential in N Exponential in N Avalanches through network
Practical consequence for the explorer

With K ≥ 3 and large N, the attractor may never be found within any reasonable number of steps because 2N grows very fast. Try K = 1 or K = 2 to see attractors reliably.

7. The Edge of Chaos

The phrase edge of chaos refers to the critical phase transition between order and chaos — the boundary where a system is complex enough to be interesting but constrained enough to be reliable.

Why K = 2 Is Special

For K = 2 and a random mix of Boolean functions, the average number of nodes directly influenced by a single node's change is exactly 1.0. This is the percolation threshold:

Spread factor λ = K · p(1 − p) · 2

where p is the fraction of 1-outputs in the truth tables. For random tables p = 0.5 and K = 2 gives λ = 1. Below 1, perturbations shrink (ordered). Above 1, they grow (chaotic). At exactly 1 — criticality.

Kauffman's Hypothesis

Kauffman argued that biological gene regulatory networks have been shaped by evolution to operate near criticality because:

Empirical support

Genetic studies suggest real organisms have effective K close to 2. The human genome (~25,000 genes, ~200 cell types) fits the prediction: √25000 ≈ 158 — in rough agreement with the observed ~200 cell types.

Beyond Biology

The edge-of-chaos concept has been proposed as a universal principle in complex adaptive systems: neural networks in the brain, ecosystems, immune systems, economies, and even evolutionary algorithms have been found to perform best — maximising information processing capacity — when tuned near criticality.

8. Using the Go Explorer

The companion program (go run .) gives you a real-time, full-resolution visualisation of NK networks.

Running It

cd /path/to/kauffman
go mod tidy     # first time only
go run .

Screen Layout

RegionWhat it shows
Header barN, K, current step, density, regime, attractor info
Left panel — Network GraphNodes in a circle. Orange = 1, Blue = 0. Arrows show directed connections.
Right panel — State HistoryGrid: each row is a timestep (newest at bottom), each column is a node. Blue = active in transient, orange = active in attractor cycle. Red line marks attractor start.

Controls

KeyAction
SpaceRun / pause the simulation
RGenerate a brand-new random network (same N and K)
SAdvance exactly one step while paused
↑ / ↓Increase / decrease N (resets network)
→ / ←Increase / decrease K (resets network)
= / −Speed up / slow down (frames per step)
Auto-pause

The program automatically pauses when an attractor is detected so you can inspect the state history. Press R to try a new network or Space to continue stepping.

9. Things to Try

Experiment 1 — Frozen Order (K = 1)

Set N = 20, K = 1. Press Space and watch. Nearly all nodes freeze within a few steps. The history grid quickly becomes solid columns. Attractor period is almost always 1 or 2.

Experiment 2 — Criticality (K = 2)

Set N = 20, K = 2. Run several networks with R. Notice that transients are longer and attractor periods vary more than in K = 1. Try to estimate the average attractor period — does it stay near √20 ≈ 4.5?

Experiment 3 — Chaos (K = 3 or 4)

Set N = 16, K = 3. Press Space. The network may run hundreds of steps without finding an attractor. The state history grid will scroll as it tries to find a cycle. Try N = 8, K = 4 — the state space is now 28 = 256 states so an attractor must eventually appear.

Experiment 4 — Scaling with N

Keep K = 2. Increase N from 10 to 50 in steps of 10 using ↑. Record the attractor period for several networks at each N. Do the averages grow roughly as √N?

Experiment 5 — Density Over Time

Watch the density reading in the header as the network runs. For K = 1 it stabilises quickly; for K = 2 it oscillates near 0.5 in the attractor; for K ≥ 3 it fluctuates erratically.

Experiment 6 — Large Networks (N = 50+)

Set N = 50, K = 2 and press = several times to run at maximum speed. The state history grid becomes a striking visual pattern. The blue transient phase and orange attractor phase are clearly separated by the red line.

Further Reading