First WhatsNewHelpConceptInfoGlossaryHomeContentsGalleryThemesOur PapersSearchAction !
BackNext TourbusIntroductionTutorLinksApplicatOnlineRelatedOfflineSoftwareSOSFAQExhibitionFun

Boolean Networks - Dynamic Organisms

by Chris Lucas

"Order for free, utterly natural, if previously mostly unknown,
will change our view of life"

Stuart Kauffman, At Home in the Universe, 1995, Ch 4

"Thanks to number, the cry becomes song, noise acquires rhythm, the spring is transformed into a dance, force becomes dynamic, and outlines figures."

Joseph Marie de Maistre (1753-1821)

Introduction

When we wish to model a complex system it is often useful to be able to make some simplifying assumptions. Many phenomena of interest in the biological or social areas operate in a discrete not continuous way. We either express a gene or we do not, we either eat a food or we do not, we either contact someone or we do not. If we treat these choices as binary yes/no decisions then we can model them easily by computer logic.

What is Logic ?

Logic is a form of truth where we say a statement is either correct or incorrect. If we use the symbol 1 to stand for correct and 0 to stand for incorrect, then a statement like 'We eat meat' will have an answer of either 1 or 0, no other choice is possible. In itself this tells us little, but we can expand the system by adding conditions. Let us add two to this case:

a) We are not vegetarian
b) We like the taste of meat

It seems clear that how we answer these questions determines our response to our initial question 'We eat meat'. If the first condition a) is false (so we ARE vegetarian), then 'We eat meat' must also be false, the answer (or output) is forced to 0, regardless of condition b). Only if a) is true (1) can condition b) come into play, and vice-versa.

Boolean Logic

Combining inputs like this requires us to work out how the combinations affect each other, this is the realm of Boolean Logic, the basis for Boolean Networks. For the above example, with two inputs (a and b), we can have 4 combinations - 00 01 10 and 11. The outputs will be:

00 = 0 (False - vegetarian and don't like meat)
10 = 0 (False - not vegetarian but don't like meat)
01 = 0 (False - vegetarian even if we like meat)
11 = 1 (True - not vegetarian and like meat)

Inspecting this result we can see that the output is 1 only if both inputs are 1, this we call an AND gate, both a) and b) must be 1 to give an output of 1. Several other types of gates (switches) are also possible, the output may be 1 if either a) or b) are 1 (we call this an OR gate). Perhaps the output is 0 if both a) and b) are 1, and 1 otherwise ? This we call a NOT AND gate or NAND for short (NOT just reverses 1 to 0 and vice-versa). Another common gate is an Exclusive OR (XOR for short) where the output is 1 if either a) or b) is 1 but not if both are 1 or both 0 (i.e. they are different), with its opposite Equivalence (EQV) where the output is 1 if both inputs are the same. For gates containing just two inputs there are 16 possible types in total (the output function is any 4 bit string, corresponding to the four combinations). This number increases rapidly if we add extra inputs, but here we will restrict ourselves to just the simplest case.

Some of these functions are what is known as canalizing, this means that the gate output can be forced to a particular state by forcing one of the inputs to a certain state (the remainder of the inputs then have no effect). A gate of this type is the AND gate, where if any input is 0 the output must also be zero. In contrast the XOR gate can always be changed by varying another input. This feature means that chains of canalizing functions can be locked into an unchanging block by a single external imput.

Boolean Networks

RBN

Let us suppose that we have a number of gates of various sorts (we'll choose just 9, a matrix of 3 gates by 3 gates). Now let us connect the inputs of each gate individually to the output of another of the gates. This forms a network, and since the gates are boolean logic gates we call it a Boolean Network. Notice that we have not specified in any way the meaning of the inputs or outputs here, this network is quite abstract and general.

Because the network operation is determined only by the logic of the gates and their input connections (in terms of 1s or 0s), we can apply it (map it) to any real life situation that has a similar decision structure and interconnectivity. We can go further and create a specific network that reflects what we know about a particular real life situation, either social interactions, plan dependencies, gene regulation, cellular structure or whatever. Studying the behaviour of the network will then tell us about the expected behaviour of the real life system - providing we have the correct configuration.

Random Boolean Networks

What if we don't know the configuration ? Well, there is another approach. Suppose we randomly initialise our network, choosing both the gate types at random and their connections. This we call a Random Boolean Network (RBN). We can have any number of gates (which we call Nodes, denoted by N) and number of inputs to each (connections, denoted by K). We shall stick with N=9 and K=2 here, which permits over 10 to power 21 different networks to be created.

These random networks will show some behaviour, so by trying out many different networks we can come to understand the general properties of such logical networks. They can be divided into 3 rough classes.

  1. The network can rapidly approach a fixed state, a point attractor. In these systems it doesn't matter from which initial state we begin, the network always converges to the same point.

  2. The network can cycle through a chaotic sequence affecting all the nodes, rarely giving the same combined output state. For our very simple 9 node case up to 512 different outputs (each of 9 bits) are possible.

  3. The network can settle down to a short sequence affecting only a few of the nodes. Many nodes are fixed in 0 or 1 states and the remainder cycle through a succession of repeating states.

Attractor Changes

attractor basins

This third possibility is the interesting one. What happens if we change the starting position, in other words the initial configuration of output states ? Well, we can regard the cyclic sequence as an attractor of the system, the initial state was a point in the basin of attraction of that attractor - which then flowed to the attractor as the network self-organized. If we change the initial state we pick a new point, which may or may not be in the same basin of attraction. If it is in the same basin then the network is stable to that mutation, the output states soon return to the same sequence as before. If the new point is not in the same basin of attraction then it will flow to a new attractor. attractor switching This may be different to the previous one in many ways, shorter or longer in length, involving different nodes, maybe a point attractor or a chaotic one.

This possibility of switching behaviour drastically by a simple change in initial state (without changing either gate types nor connections) is interesting in the context of cell, mind and social behaviours. For a such a simple network as our 9 node case we can have several simultaneously present attractors, only one of which is expressed at any one time. The perturbation required to change the attractor may be a single bit change or may require several bits to be changed simultaneously. Both types of unstable and stable behaviour are found in nature, suggesting that this model is a useful one.

Activation Sequences

For these types of attractor, the outputs of the various nodes will follow a sequence, some may be always on, some always off, some on and off alternately, some on once in three cycles and so forth. Depending on how we regard these networks we can assign meaning to them in various ways, by mapping them to interesting 'real world' applications. If the outputs are regarded, say, as gene activations then the hormones being produced could correspond to gates switching 'on' perhaps; if regarded as behaviours then sequential cycles may be seen (e.g. eat, drink, sleep, mate); if instead we are concerned with transient thoughts we may have several active concepts appearing in parallel, each proportional in strength to the respective 'on' time of the node.

The identification of such correspondences can be a difficult problem. The meaning (or semantics) depends closely also on the timestep we employ. Systems may operate at more than one rate, e.g. cellular metabolism versus the life and death of the cell, or at different emergent levels, e.g. personal needs versus social values, each requiring alternative and specific interpretations. In complex systems it may prove difficult to even identify which nodes comprise a sequence, or even what is, in fact, a 'node', let alone to determine what any particular sequence means in terms of the overall system. Nethertheless, the general approach outlined here is proving fruitful in many areas of research, and we can extend it from the very simple systems considered until now to much more complex networks.

Real World Networks

The human genome is said to have around fifty thousand genes, the brain around ten billion neurons, the internet over twenty million computers and the world over six billion people. For such massive connectivity it would appear that the attractor options are astronomical. Luckily connectivity in all these systems seems far sparser than our randomly connected models (a phenomenon sometimes called 'small-world networks', where most nodes connect to few others, but some nodes have large connectivity - a fractal spread of connectivity results from self-organizational processes). We seem able to divide up real life systems into modular units, which are amenable to being treated as small cooperating networks. When larger networks are analysed, those in the third form (exhibiting interesting behaviour), seem to evolve in such a way as to show small regions of dynamics separated by barriers of unchanging nodes, this we call a self-organized criticality and it allows both modular autonomy combined with system wide communication possibilities - reminiscent of both organisms and societies.

Network models (whether the connections are explicit, as here, or implicit as in cellular automata) offer a useful viewpoint on many complex systems. Topologically these models are isomorphic (equivalent) to the underlying natural system and this isn't affected by the size or nature of the 'real' system. Many different types and levels of system may thus map onto the same network arrangement and then will be expected to exhibit the same emergent behaviours. In this way we can make connections between the various types of natural system and perhaps see nature for what it is, a unified whole operating by common laws.

Logic Continuums

We started with a simplification, by assuming that all nodes had either a 1 or 0 output. We know that in many cases that isn't true - there are processes which do genuinely have smoothly varying outputs, strength of grip for example, or pen movement. Can we treat these in the same way ?

To do this we need to extend our logic to cover the cases having intermediate truth values. This isn't possible using traditional logic since that excludes the possibility of cases that are partly true and partly false, but a new form of logic has been invented that can deal with such situations. This is called Fuzzy Logic.

In a fuzzy logic treatment we express the inputs as continuous values between 0 and 1, the output then combines these using a suitable function to generate an output also varying between 0 and 1. Because we are just generalising our model to an analogue (continuous) case from a digital (discrete) one we would expect the findings to still hold in general, these fuzzy networks should also be found to exhibit attractor dynamics, modularity and self-organized criticality. This also applies to systems based upon the 'S' shaped sigmoid function common to many natural 'triggered' reactions.

Since stability requires a resistance to change, the stability of attractors for various forms of the function will vary. In the worst case (linear functions) there may be just one attractor, a single equilibrium state of the system. As the function produces a more non-linear response then the attractor boundaries will sharpen, until for a pure 1/0 logic step we can have a single bit transition between adjacent attractors.

This is important when we come to consider multidimensional systems, in which each node has many 'choice' variables or parameters. In these, from a binary point of view, we find that to move from a state, say, of all 1's (e.g. 11111) to a state of all 0's (00000) requires 5 simultaneaous 'mutations', an extremely improbable scenario, so the system is 'stuck' in one local optimum (broken symmetry or broken ergodicity) - assuming 11111 and 00000 are both optimums and that mixed states (e.g. 10101) are not. For continuous systems however the attractor boundaries get fuzzier, and the system can then more easily drift from one attractor to another, until we get (in the limit) to classical ergodic systems where no movement restrictions apply. Nonlinear functions generate scenarios between these two extremes, and these of course prove to be closer to the situations that we encounter in day-to-day life.

First WhatsNewHelpConceptInfoGlossaryHomeContentsGalleryThemesOur PapersSearchAction !
BackNext TourbusIntroductionTutorLinksApplicatOnlineRelatedOfflineSoftwareSOSFAQExhibitionFun
Page Version 4.83 December 2005 (Paper V1.3 February 2005 Original August 1997)