Kauffman Networks[chaos]

A liver cell and a neuron contain essentially the same genome, yet maintain different patterns of gene activity. How can one set of genes support more than one stable pattern? In 1969, Stuart Kauffman stripped that question down to a network of switches (Kauffman, 1969).

Each switch represents a gene. It is either on (1) or off (0), and other genes determine what it will be at the next moment. Once the switches are connected back to one another, the network has a memory: what it does next depends on what it is doing now.

What does NK mean?

A bKauffman network is specified by two numbers:

• N is the number of genes in the network.
• K is the number of inputs read by each gene.

For every gene, choose K genes as inputs and choose a Boolean rule that turns their 2^K possible input patterns into either 0 or 1. In a random Boolean network, both the inputs and the entries in those rule tables are sampled at random.

The network below has N=4 genes and K=2 inputs per gene. This is a collapsed view: only genes and the dependencies between them are shown. An arrow B \rightarrow A means that gene A’s next value depends on gene B’s current value. The arrow alone does not say whether B activates or represses A; that depends on A’s complete Boolean rule.

Here are the four update rules used in this example:

The last rule deliberately ignores one of its two inputs. That is allowed: a rule may formally receive K inputs without every input changing its output.

Where do the connections come from?

The word random describes how an ensemble of Kauffman networks is constructed, not what happens at every time-step. For each target gene, the classical construction makes two independent choices:

1. Select K source genes from the N genes in the network.
2. Fill the target’s truth table by choosing one output bit for each of the 2^K input patterns.

For an unbiased network, each truth-table output is an independent fair coin flip. There are therefore 2^{2^K} possible Boolean functions for a particular ordered set of K inputs: 4 functions when K=1, 16 when K=2, and 256 when K=3. After the connections and rules have been sampled, they are held fixed while the network runs. The randomness is quenched: revisiting the same network state always produces the same next state. Resampling connections or rules at every update would be a different, stochastic model (Kauffman, 1969).

Exactly what “select K sources” means is a convention that must be stated. Here, a target receives K distinct inputs, sampled without replacement, and a gene is allowed to regulate itself. Thus D’s regulatory neighbourhood in Figure 1 is C, D, including the self-connection D \rightarrow D. Each gene has exactly K incoming arrows, but its number of outgoing arrows is unconstrained: one gene may regulate many targets while another regulates none.

The connections in this small worked example were chosen deliberately so the calculation can be followed; they were not presented as a random sample. Its update machinery is nevertheless the same as that of a sampled NK network. There is also a subtle difference between a formal connection and an effective connection. D formally reads C and D, preserving K=2, but its COPY rule ignores D. Changing D cannot change that rule’s output, so the self-arrow is structurally present but dynamically ineffective.

Three different kinds of neighbourhood

“Neighbour” is used for three different things in discussions of Boolean networks. Keeping them separate prevents a state perturbation from being mistaken for an evolutionary mutation.

• A gene’s regulatory neighbourhood is the set of genes feeding its update rule. For A here, it is B, C.
• A state’s Hamming neighbourhood contains states differing in one gene value. Every N-bit state has N such neighbours. Moving from 1010 to 0010, for example, flips A but leaves the connections and rules untouched.
• A network’s mutational neighbourhood contains networks reachable by one permitted edit to its inherited representation. This neighbourhood does not exist until a mutation operator has been specified.

The original NK construction defines an ensemble and its dynamics; it does not force one unique model of evolution. A common fixed-N, fixed-K evolutionary convention permits two elementary mutations:

1. Rule-bit mutation: choose one gene and flip one output in its 2^K-row truth table.
2. Rewiring mutation: choose one of a gene’s K input slots and replace its source with a source not already used by that gene.

Both are local edits, but local does not mean dynamically small. A one-bit rule mutation changes the update of one gene whenever that truth-table row is visited; across the complete N-gene state space, it redirects 2^{N-K} state transitions (Xiao & Dougherty, 2007). A rewiring can alter several truth-table lookups because the edited input slot now reads a different gene.

Under the convention above, the number of encoded one-mutation neighbours can be calculated. There are N2^K ways to flip one truth-table bit. For rewiring, choose one of N targets, one of its K input slots, and one of N-K sources not already used by that target, giving NK(N-K) possibilities.

For this network, with N = 4 and K = 2, that convention gives 32 one-mutation neighbours. This count is representation-level, not behaviour-level. Two different edits can produce the same state-transition map, and some mutations are neutral. For example, rewiring D’s ignored second input changes the encoded network but changes none of its trajectories. Replacing an entire Boolean rule at once, adding or deleting a connection, or adding or deleting a gene would define different neighbourhoods; the last two also allow K or N to change.

Let every gene update together

Choose a starting state, then advance the network in discrete steps. At each step every gene reads the old state, evaluates its rule, and only then do all genes change together. No gene gets to see another gene’s newly calculated value early.

Start with A and C on, written 1010 in the order A, B, C, D. In Figure 2, blue genes are on and white genes are off.

The first update illustrates the bookkeeping. With A and C on, A’s rule reads B = 0 and C = 1, so A turns off. B reads A = 1 and D = 0, so B turns on. C reads A = 1 and B = 0, so C stays on, while D copies C and turns on. The whole state therefore changes from 1010 to 0111.

The calculations below are generated by the same RULES object and the same evaluate_rule() function that produce the trajectory and drawings. Each row substitutes the current 0/1 values into all four rules before constructing the next state.

Continuing produces a repeating sequence. The transient states are followed by an attractor containing 3 states:

After 0001, the next update returns to 0100, so the attractor states repeat forever. This repeating set is an attractor; the earlier states form its transient. A fixed point is simply an attractor containing one state.

The recurrence is not an accident. An N-gene Boolean network has only 2^N possible states. Its rules assign exactly one next state to each of them. Sooner or later a trajectory must revisit a state, and from then on it must repeat the same cycle. Different starting states may flow into the same attractor, or into different ones. The collection of starting states that reaches an attractor is its basin of attraction.

Why vary K?

K changes how widely a disturbance can spread. When each gene reads few inputs, much of a random network tends to freeze and nearby starting states often converge. With many inputs, flipping one gene can alter several rules, whose changed outputs alter still more rules; nearby trajectories tend to diverge. Between these ordered and chaotic regimes is a critical boundary where perturbations, on average, neither disappear nor grow.

For unbiased random Boolean rules, the classic approximation places that boundary near K=2. This is an ensemble-level result, not a guarantee about every network: a particular K=2 network can still freeze, cycle, or behave sensitively depending on its wiring and rules. Kauffman’s larger proposal was that living regulatory systems exploit dynamics near this boundary—stable enough to preserve organisation, but flexible enough to change (Kauffman, 1993).

What the model explains—and what it leaves out

Kauffman proposed reading different attractors as different cell types. On that interpretation, one regulatory network can support several persistent patterns of gene activity without storing a separate blueprint for each one. Order can emerge from the network’s dynamics before natural selection chooses among the resulting possibilities.

That is the model’s useful lesson, not a literal picture of a cell. Real genes are not merely on or off, do not all update on one shared clock, and are affected by noise, molecular concentrations, signals, and spatial context. A classic Kauffman network is also closed: after its initial state is chosen, it receives no continuing input from neighbours or the environment. Opening that closed network—letting cells signal to one another—is one of the steps needed to move from a model of gene-state dynamics toward a model of multicellular development.