Definition

This section provides a short description of Random Boolean Networks, their properties and some terminology.

Random Boolean Networks - a short outline

Random Boolean Networks (RBN) are also known as NK-Networks and were first proposed by S.A Kauffman([B1], [B2]) in 1969 to model genetic regulation in cells. RBN are often specified by two parameters: N, the number of nodes and K, the number of incoming links per node. Sometimes, K also indicates the average number of incoming connections per node. Each node has a specific logic transition rule that determines the output and the state of the node in function of the values on the incoming links. The values taken by the outputs and, therefore also by the connections, are zero and one (off/on).

Connections and rules in a RBN are chosen at random. For a node with K incoming links there are 2^K possible sets of input vectors and the number of values in the rules of the network is N*2^K. Considering that each of these values can be zero ore one, there are 2^(N*2^K) different networks that can be created at random.

RBN can be regarded as binary neural networks and are therefore forming a subclass of neural networks. Comparing to neural nets, RBN do not have weighted connections and are consequently not suited for learning tasks. However, RBN can be used to study large systems of many interacting units and their dynamics (e.g gene regulation networks, neural networks, economics, etc.). Kauffman's studies ([B1]) have revealed surpisingly ordered structures in randomly constructed networks. It turned out that the networks exhibit three major regimes of behaviour: ordered (solid), complex (liquid) and chaotic (gas). The most highly organized behaviour appears to occur in networks where each node receives inputs from two other nodes (K=2).

RBN cannot only be seen as subclass of neural networks, but also as a generalization of the well-known Cellular Automata (CA) proposed by John von Neumann in the late 1940's. In this case a node only receives inputs from nodes in his local (spatial) neighbourhood and each node has the same logic transition rule.

Different types of RBN can be classified according to their update schemes.