CS 297: Complex Systems

Assignment 2: Boolean Networks

In this assignment, you will simulate boolean networks and evaluate the results. To start, let's first review boolean networks:

A boolean network is a directed graph in which each node (vertex) has one or more incoming edges and one or more outgoing edges. The structure of the graph (the particular pattern of edges) is one important aspect of a boolean network. We'll refer to the structure as the network structure.

The state of each node is either 0 (zero) or 1 (one) at any time. To determine the next state of a node V, you examine the states of nodes at the ends of incoming edges to V. Suppose there are k incoming edges to V. Let the nodes on the other side of these edges be called U₁, U₂, ..., U_k. Then, if the current state of V is called S(V), the next state of V is a Boolean function of S(U₁), S(U₂), ..., S(U_k).

We allow a node to have an edge to itself, so a node can have itself as an incoming or predecessor node.

All nodes change state at the same time, as in a cellular automaton.

Each node has its own Boolean function that determines its next state. You can have networks where every node has the same Boolean function, or networks where nodes have different ones. For example, consider a boolean network where each node has exactly two incoming edges. Then, by using the AND function at each node, every node will have exactly the same Boolean function. Alternatively, some nodes could have AND functions, others could have OR, and so on.

When each node of a boolean network has exactly two incoming edges, we will refer to this kind of network as a binary boolean network.

If the network has n nodes, then the network can be in one of 2ⁿ states. We'll call these network states. If the network is in network-state X, then the network structure together with the Boolean functions at the nodes completely determine the next state.

Let the N = 2ⁿ network states be called X₀, X₁, ..., X_N-1. Then, if the current state is some X_i, and the next state is some X_j, we say that Nextstate(X_i) = X_j.

Define the dynamics graph or state-transition graph as follows: the nodes of the state-transition graph are the network states X₀, X₁, ..., X_N-1. For every i and j such that Nextstate(X_i) = X_j, we place an edge directed from node i to node j in the state-transition graph. It is the structure of the state-transition graph that is of interest in the study of boolean networks. For any network state X_i, consider what happens when applying "nextState" repeatedly, i.e.,

         nextState (X_i)
         nextState (nextState (X_i))
         nextState (nextState (nextState (X_i)))
         ...

There are four possibilities:

nextState (X_i) = X_i, in which case we get stuck in state X_i.
You get other states, but eventually cycle back to X_i. In this case, continued application of "next state" will eventually cause X_i to repeat.
You traverse through some states and eventually get stuck in another state X_j, where nextState (X_j) = X_j.
You reach a state X_j, such that X_j is in a cycle, but X_i is not. This means, that X_j will eventually repeat.

Of these four possibilities, the first one is really a special case of the second and third. Thus, there are really only three types of states: states in which you get stuck, called point attractors, cycles in which you get repetition called limit cycles (or cyclic attractors) and the remaining states.

For each state X_i, let L(X_j) denote the number of steps before it gets stuck into an attractor. Thus, in the first of the four cases above, L(X_i)=1. Another way of thinking about this, is to repeatedly apply "nextState" until you get the first repeated state; then L(X_i) the number of applications of "nextState" starting with state X_i.

Define L as the average value of L(X_i) over all states X_i. Define A as the number of point attractors. Let G be the number of nodes with no incoming edges. Finally, let D denote the in-degree distribution (how many nodes have 1 incoming edge, how many have 2 incoming edges, ... etc).

Note that once the network structure and Boolean functions are fixed, the measures L, A, G and D are completely determined.

With this background, let's focus on the assignment. We will study binary boolean networks characterized by three parameters p, q and r that we will define below. Your goal is to compute L and A for randomly generated networks and study the effect of varying the network parameters p, q and r.

We will next explain the parameter p, which is going to govern network structure:

You will start with the so-called ring binary network. In this network, each node i (among nodes 0, ..., n-1) has precisely two incoming edges from nodes i-1 and i-2. Note that for node 1, one of the neighbors will be node n-1, and node 0 will have neighbors n-1 and n-2. At this point, each node has exactly two incoming edges and exactly two outgoing edges.
Given the starting "ring" configuration, we will repeatedly re-wire the network as follows. Consider each node in turn. Choose the edge that comes from the numerically farther node and toss a p-biased coin (one that shows heads with probability p). If you get heads, replace this incoming neighbor with another one chosen randomly from any of the other nodes. If this is done in turn for every node, then there will be some re-wiring of the network depending on how large p is. Note that this is very similar to the re-wiring model used by Watts and Strogatz in creating small-world graphs.
Thus, the parameter p determines how "random" the the network structure is. For p = 0, there is no change; for p = 1, there is a lot of re-wiring. For small values of p, we'll get some re-wiring. Indeed, some values of p should give the "smallworld" structure.

Now, let's consider the the Boolean functions at each node:

To determine the Boolean function at a node, we will randomly assign one of three functions AND, OR or XOR to the nodes. Let q denote the probability that a node is assigned the Boolean function AND. Let r denote the probability that a node is assigned the Boolean function OR. Therefore, 1-q-r is the probability that it is assigned XOR. Stated differently, the triple (p, q, 1-p-q) determines the distribution of these functions.
Consider the following cases:
1. (1,0,0). All nodes use the AND function.
2. (0,1,0). All nodes use the OR function.
3. (0,0,1). All nodes use the XOR function.
4. (1/3, 1/3, 1/3). Equally likely between the three.
5. Explore some other combinations.

For each of the cases above, obtain the measures for 8-node and 10-node graphs. If you have time, you can try more nodes. The goal is to see whether which parameter combinations result in interesting behavior.

Finally, let's consider some implementation issues:

At first this will seem like a very long assignment. But upon some reflection, we will see that it's actually quite straightforward.
First consider the representation of the network graph. This is easily represented by a binary matrix where the entry i,j is 1 if there is a directed edge from node i to node j.
The network state can be represented in a 1-D array.
The Boolean function for each node, can be recorded in an array as well.
Once the network structure and Boolean functions are known, the next state function is easy to compute.
It is easy to generate all possible network states (You will need to think about how to represent this).
For each network state, you can compute the length measure. As you go along, you can track the point attractors and the number of leaf nodes (G).