The aim of this tutorial is to introduce the structure and dynamics of Random Boolean Networks (RBNs). It will also provide an introduction to Matlab and the RBN toolbox for Matlab.
This document describes the mechanics and dynamics of Random Boolean Networks. Each section includes a series of questions. At the end of the document there is a series of tasks requiring the use of Matlab to investigate the structure and dynamics of RBNs.
For more information on RBNs see:
The Random Boolean Network model was introduced by Kauffman in 1969 as an abstract model of the dynamics of gene regulation. In this model, nodes in the network correspond to genes, and edges between nodes indicate regulatory relationships between genes. That is, if there is an edge between node A and node B, then gene A regulates gene B. Attractors in the network (described below) have been argued to correspond to cell types, and the transient dynamics of the network have been likened to a developmental process. The aim of using Random Boolean Networks as a model of gene regulation is to ask questions about the nature of self-organisation in biological systems, and to explore the ways in which simple changes to a system's rules and biases can affect its global behavioural properties.
In addition to modelling the general properties of the dynamics of gene regulation, Random Boolean Networks are also prototypical discrete dynamical systems and are illustrative of combinatorial structure.
A Random Boolean Network consists of N randomly connected nodes, each of which has a binary state: on or off (1 or 0). In NK networks (a.k.a. Kauffman networks) every node receives exactly K inputs chosen randomly from other nodes in the network and in most cases self-connection is allowed (Figure 1 shows an example of the topology of an RBN).
Figure 1: Example of the topology of an RBN.
The state of each node in the network at time t+1 is determined by the states of its inputs at time t through a randomly generated Boolean function which can be represented with a look-up table for each node (see Table 1). Typically the Boolean functions do not change throughout the lifetime of the network. In an RBN the Boolean function for each node maps each of the 2^{K} possible input combinations to an output state of 0 or 1.
Table 1: Example of a Boolean function with K inputs represented by a look-up table. Each node in an NK network has its own Boolean function with a randomly chosen output state for each of the 2^{K} possible input combinations.
The network is given a random initial state by assigning each node a value of 0 or 1. The value of each node at the next time step is determined using the state of its inputs and each node's Boolean function. All nodes are updated at the same time (synchronously). The new state of the network is generated and then used to determine the next state and so on. An example of the network activity is displayed in Figure 2.
Figure 2: Activity pattern for an RBN with 16 nodes for 50 time steps. The initial state is the column furthest to the left with nodes represented vertically and time moving to the right.
Since each node can be in one of two states, the total number of possible states for the entire network is 2^{N}. Thus the system has a finite state space where each network state can be represented as a bit-string of length N. The use of deterministic Boolean functions means that the transitions between the network states are also deterministic and with a finite state space, the network will always fall into periodic behaviour.In other words, if the network is in state A and proceeds into state B at the next time step, then this transition will occur every time the system is in state A. As soon as one state is repeated, the network has entered a periodic attractor with a period length equal to the number of iterations since the network was last in same state. There may be a number of periodic attractors in the state space with period lengths ranging from 1 to a possible (though extremely unlikely) 2^{N}.
Figure 3: A periodic attractor (yellow) and its basin of attraction (cyan). Each point in the state space represents a network state.
Not every state of the network is part of a periodic attractor. The other states lie in the basins of attraction for each attractor which consist of the transient states through which the network passes before it enters an attractor. Due to the deterministic dynamics none of the basins can overlap so the state space is divided into a number of periodic attractors with their associated basins of attraction.
Figure 4: The entire state space of an RBN with 10 nodes. Note: Self connections do not appear so a period-1 attractor appears to have no outputs although each network state must have exactly one output.
The number of attractors and the size of their periods are important quantities for RBNs. If a network is in a period 1 attractor its behaviour will be fixed. Behaviour with a low period is also easily recognisable as periodic (see Figure 2), however, if the behaviour has a very high period, the activity pattern will appear random as it may take many thousands of time steps before the pattern repeats, even for modest sized networks. Long periods typically occur in networks that can be classified as chaotic (see below) and vice versa.
Network behaviour can be classified into 3 regimes: frozen, chaotic and critical. The existence of chaotic behaviour is identified by the way in which perturbations (e.g. changing the state of a node) spread through the network. To measure such damage spreading the activity pattern of an RBN is recorded, this is the original activity pattern. Then the initial network state is perturbed by changing the state of one node from a 0 to a 1 or vice versa. The perturbed activity pattern is monitored over time. After a number of iterations, if the damage has spread so that the network state now differs from the original activity pattern in an increasing number of places, the network is called chaotic — characterized by sensitive dependence on initial conditions. If the perturbation has disappeared so that both networks display the same pattern, the network is called frozen (or ordered). Alternatively, the states of the two networks still differ in a limited number of places so that the damage may not have spread or disappeared, in this situation the network is said to display critical behaviour.
The key factor in determining network behaviour is the connectivity. Averaged over many networks, critical behaviour occurs in NK networks for K = 2, frozen behaviour occurs for K < 2 and chaotic behaviour occurs for K > 2. It is important to understand that this classification applies when averaged over many networks and that an individual network with K > 2 can display ordered dynamics with low period attractors.
An associated property in the classification of networks is the way in which period length grows with increasing the number of nodes (see Table 2).
Regime | K | Period Length | Damage Spreading | Matter Analogy |
Frozen |
Less than 2 |
Independent of N (typically period 1) |
Perturbations die out; stable dynamics. |
Solid |
Critical |
2 |
Grows algebraic with N (believed to be proportional to N^{1/2}). |
Perturbations continue to affect a limited number of nodes; marginally stable dynamics. |
Transitional (Liquid?) |
Chaotic |
Greater than 2 |
Grows exponentially with N. | Perturbations cause extensive changes to the network state; unstable dynamics. | Gas |
Table 2: RBN Classification
A list of the properties of Random Boolean Networks outlined above is available in the Summary of Random Boolean Network Properties.
The following tasks are designed to be done using the Matlab mathematical programming environment. If you are not familiar with Matlab, you should first look at the One Page Introduction to MATLAB. You will also be using a set of tools called the Matlab Random Boolean Network Toolbox.
Documentation for Matlab (and RBN Toolbox) commands can be obtained by typing help <command> at the Matlab prompt, where <command> is the function that you wish to access help for. Documentation is also available at the toolbox website.