Monday, November 23, 2020

Random Boolean Networks: (Using Python)

Note: some content is ideally viewed on larger than 7" displays.

 

My investigation of patterns in Random Boolean Networks using Python.

According to Wikipedia, they were first investigated in 1969. RBN's have some similarities with John Conways game of life from 1970, but  Life has a rigid rectangular grid of cells and rigid rules for state changes of nodes - not present in RBN's.


What it is


The figure above gives the gist of a random boolean network, but I will be investigating a more rigid form:

  • Each node has the same number of, (ordered), connections to random other nodes, (which can include connections to itself).
  • Each node uses the same, random function of its ordered connections to determine its next state.
  • All nodes are updated synchronously: All node values at time t determine all node values at time t+1.

Closer to code

 Lets say we define 

  • The number of nodes to be set by the name nodes with the value 7 for illustrative purposes.
  • We generate a random starting state for each node in the name values.
  • The number of connections each node has is set in name conn. (3 in this case).
  • We then randomly generate three connections per node stored in the list-of-lists conns
  • Each connected node of a given node, can be 1 or 0.
    If we were to construct the regular truth table of the 2**conn = 8 in this case, possible inputs to a node, we then generate a random 8 bit output of the truth table stored in the list conn2val.

Here are tables of a possible outcome:

Nodes








#nodes 7








_names
N0 N1 N2 N3 N4 N5 N6











values
0 1 0 0 1 1 1










Connections








#conn 3

















Adjacency list of conns[n][0]
N4 N4 N1 N2 N2 N5 N2
connections per conns[n][1]
N0 N2 N5 N6 N0 N2 N0
node. conns[n][2]
N5 N3 N4 N1 N1 N4 N4




















Connection to Value

conns conn2val


Truth Table

[n][2] [n][1] [n][0]





0 0 0 0





0 0 1 1





0 1 0 1





0 1 1 0





1 0 0 1





1 0 1 0





1 1 0 0





1 1 1 1






















Graphviz plot
















Using the tables

Node N6 has connections to N2, N0 and N4 in order. 

If at time T N2 = 0 and N0 = 0 and N4 = 1, then looking at the 1,0,0 row of the truth table, equivalent to looking up the binary 100 = decimal 4'th row of list conn2val we find that the value of N6 at time T+1 will be 1. This is stored in the updated values[6]  for time T+1.

The above is done for all the nodes leading to an update to the values. Note: only values from time T are used to calculate values for time T+1.

The values for successive time steps are calculated and examined.

Load, Dump, Replay

I decided to create a simple textual language that would allow me to load, dump and replay any of my RPN's. The language is a series of lines, each line has space separated fields. 

  • Unexpected lines that dont start with a recognised keyword are ignored.
  • Trailing unexpected fields in a line are ignored.
  • Some parsed lines expect a specific number of lines immediately after, in a specified format. (That may not be tolerant of extra fields).

The definition of an RBN has these records of possible multiple lines in this order:

  1. NODE
  2. NODE_VALUES
  3. CONNECTIONS
  4. CONN_TO_VALUE

NODE record

How many nodes in this RBN 

Example:
 NODE 7

NODE_VALUES record

Starting values of nodes, or an indication to chose random starting values

Example:

NODE_VALUES LIST
   0 1 0 0 1 1 1

Example 2:

NODE_VALUES RANDOMISED

A LIST is followed by a line of zero's and ones - starting values for the number of nodes specified in the prior NODES record.

RANDOMISED will assign random values. (And so expects no extra line).

CONNECTIONS record

The number of connections for each node and either a table of those connections or instruction to randomly generate that number of connections per node.

Example:

CONNEXTIONS 3 TABLE

4 0 5

4 2 3

1 5 4

2 6 1

2 0 1

5 2 4

2 0 4


Example 2:


CONNEXTIONS 3 RANDOMISED

The TABLE format is followed by that number of connections for the nodes: just the integers; each node on a separate line; each connection for that node in order, (for the truth table to come), on that line.

RANDOMISED will assign the stated number of connections to each node randomly. (And so expects no extra line).

 CONN_TO_VALUE record

If the conn=3 connections of a node form the truth table with 2**conn input rows then this record specifies the output value of a node when the input is one of the values 0 .. 2**conn - 1

Example:

CONN_TO_VALUE LIST
  0 1 1 0 1 0 0 1

Example 2:

CONN_TO_VALUE RANDOMISED

A LIST is followed by a line of zero's and ones - starting values for the number of nodes specified in the prior NODES record.

RANDOMISED will assign random values. (And so expects no extra line).


Specification for the tables above

The tables above are captured by the following specification:

NODES 7
NODE_VALUES LIST
  0 1 0 0 1 1 1
CONNEXTIONS 3 TABLE
  4 0 5
  4 2 3
  1 5 4
  2 6 1
  2 0 1
  5 2 4
  2 0 4
CONN_TO_VALUE LIST
  0 1 1 0 1 0 0 1


Most randomised specification

The node count and the number of connections per node must be specified, but the other fields can be randomly assigned.

The following loose spec was used to generate the specific RBN in the tables above.

NODES 7
NODE_VALUES RANDOMISED
CONNEXTIONS 3 RANDOMISED
CONN_TO_VALUE RANDOMISED

I can repeat the use of similar loose specs and look at the succession of values produced by the random RPNs it produces.


Code

I am going to leave the details until later and concentrate on how the code was used in investigating RBNs.

Simple random generation run

This uses a loose spec to generate a new RBN then runs it for a few time-cycles.

def main0(nodes_in=10, conn_in=2, t=20):
    "Generate a random RBN and run it for t cycles"
    config = f"""\
        NODES {nodes_in}
        NODE_VALUES RANDOMISED
        CONNEXTIONS {conn_in} RANDOMISED
        CONN_TO_VALUE RANDOMISED\
    """
    print("#STARTING CONFIGURATION\n\n" + config)

    nodes, values, conn, conns, conn2val =  read_config(config)
    start = nodes, values.copy(), conn, conns, conn2val
    print("\n\n#GENERATED RBN\n\n" + config_to_text(*start))

    # Graphviz graphical display of network
    gr = Graph('', conns)
    display(gr._to_gv())

    print('\n#RUN:')
    for step in range(t):
        pval(values, step)
        new_values(nodes, values, conn, conns, conn2val)

Sample of random output

#STARTING CONFIGURATION

        NODES 10
        NODE_VALUES RANDOMISED
        CONNEXTIONS 2 RANDOMISED
        CONN_TO_VALUE RANDOMISED    


#GENERATED RBN

NODES 10
NODE_VALUES LIST
  0 0 0 1 1 0 1 0 0 1
CONNEXTIONS 2 TABLE
  2 6
  3 0
  8 4
  8 5
  7 1
  6 0
  8 1
  4 6
  8 9
  2 4
CONN_TO_VALUE LIST
  0 1 0 1

#RUN:
   0:  000  0 00 
   1:   0 0000   
   2:  0 000 00 0
   3:  000  0 000
   4:   0 0000 0 
   5:  0 000 00 0
   6:  000  0 000
   7:   0 0000 0 
   8:  0 000 00 0
   9:  000  0 000
  10:   0 0000 0 
  11:  0 000 00 0
  12:  000  0 000
  13:   0 0000 0 
  14:  0 000 00 0
  15:  000  0 000
  16:   0 0000 0 
  17:  0 000 00 0
  18:  000  0 000
  19:   0 0000 0 


The above looks OK.(I ran it several times and chose a sample run that repeats with a period > 1). 

The value at time 2 repeats at times 5, 8, 11, ...

RBN rerun

Lets check we can rerun the last RBN from its genrated description

def main1(config=None, t=20):
    "Run a given RBN textual config for t cycles"
    if config is None:
        config = """\
            NODES 10
            NODE_VALUES LIST
              0 0 0 1 1 0 1 0 0 1
            CONNEXTIONS 2 TABLE
              2 6
              3 0
              8 4
              8 5
              7 1
              6 0
              8 1
              4 6
              8 9
              2 4
            CONN_TO_VALUE LIST
              0 1 0 1
        """
    nodes, values, conn, conns, conn2val =  read_config(config)
    start = nodes, values.copy(), conn, conns, conn2val
    print("\n\n#RUNNING RBN\n\n" + config_to_text(*start))

    print('\n#RUN:')
    for step in range(t):
        pval(values, step)
        new_values(nodes, values, conn, conns, conn2val)


##
## Output
##

In [42]: main1()


#RUNNING RBN

NODES 10
NODE_VALUES LIST
  0 0 0 1 1 0 1 0 0 1
CONNEXTIONS 2 TABLE
  2 6
  3 0
  8 4
  8 5
  7 1
  6 0
  8 1
  4 6
  8 9
  2 4
CONN_TO_VALUE LIST
  0 1 0 1

#RUN:
   0:  000  0 00 
   1:   0 0000   
   2:  0 000 00 0
   3:  000  0 000
   4:   0 0000 0 
   5:  0 000 00 0
   6:  000  0 000
   7:   0 0000 0 
   8:  0 000 00 0
   9:  000  0 000
  10:   0 0000 0 
  11:  0 000 00 0
  12:  000  0 000
  13:   0 0000 0 
  14:  0 000 00 0
  15:  000  0 000
  16:   0 0000 0 
  17:  0 000 00 0
  18:  000  0 000
  19:   0 0000 0 

In [43]: 

That seems to reproduce the RBN and its outputs when run, successfully.

Value Loop detection

 Because next values are wholly dependent on current node values, you can keep a dict mapping values as a tuple to the time step it was first found in. If a future value is in the dicts keys then a loop of values has been found that will recur.

Strongly connected components. 

An examination of node connectivity in an RBN might show that the network is composed of multiple strongly connected components, SCC's. Nodes within one SCC affect each other but not nodes from another SCC. So, for example, given the 10 nodes of the last example, they are grouped into the following single  strongly connected component:

[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]

SCC's should act independently with their values intertwined with other SCC's of the network.

Network cycle detection

Cycles in the network, where  node X affects node Y affects ... affects initial node X;   should have a partial effect on the length of loops in the output values when the network is run. I'd think that you won't find a value loop of length l unless their are log2(l) or more nodes interconnected in a cycle.

The last example has a value loop from time t=2 to time t=5 of length 3 time steps. It has 26 cycles in its network, from the smallest being feedback from node 8 back to itself; all the way to the cycle of nodes [0, 2, 8, 9, 4, 7, 6, 1, 3, 5], in that order, and going back to the start node 0 afterwards, is implied. 

The truth table as well as the starting values also affect the size of value loops found.

Search for value loops with long periods.

 This code loops through the generation of random networks; checks for adequate cycle length; then filters for ever increasing loop periods.

if __name__ == '__main__':
    
    #config_in = config_inx[-1]
    config_in = config_rnd
    max_loopsize = loopsize = 0
    better_configs = []
    nodes, *_rest = read_config(config_in)
    while max_loopsize < 2**(nodes - 1) - 1:
        while loopsize <= max_loopsize:
            nodes, values, conn, conns, conn2val =  read_config(config_in)
            gr = Graph('', conns)
            if max_loopsize >= 2**max(len(s) for s in gr.scc):
                continue    # cant possibly loop for longer?
            start = nodes, values.copy(), conn, conns, conn2val
            print()
            #display(gr._to_gv())
            print(config_to_text(*start))
            print('\n#RUN:')
            val2step = {}
            for step in range(2**nodes):
                if step < 25:
                    pval(values, step)
                v = tuple(values)
                if v not in val2step:
                    val2step[v] = step
                else:
                    print(f"Loop found from step {val2step[v]} to {step}")
                    loopsize = step - val2step[v]
                    break
                new_values(nodes, values, conn, conns, conn2val)
        display(gr._to_gv())
        better_configs.append((loopsize, start))
        max_loopsize = loopsize
       #input(f'{len(better_configs):>2} Paused')

Next investigations

What I plan on investigating next:
  •  Two and more RBN's of differing, long-ish value loop periods and each having only the single strongly connected component: What happens when they are combined?
  • Add structure to the connections table and see its effect.
  • Are RPN's with long periods likely to have a a truthtable with even-ish numbers of ones and zeroes?

The rest of the code

Note that I import code from my "Finding cycles in a graph. Johnsons method in Python." blog entry  

# -*- coding: utf-8 -*-
"""
    Random Boolean Networks - Computerphile
        https://www.youtube.com/watch?v=mCML2B94rUg&ab_channel=Computerphile
    Boolean Dynamics withRandom Couplings:
        https://arxiv.org/pdf/nlin/0204062.pdf?
Created on Fri Nov 13 23:33:15 2020

@author: paddy3118
"""
import random
from graph_cycles_johnson import Graph


##
## Some example configurations of use
##

config_rnd = """
NODES 7
NODE_VALUES RANDOMISED
CONNEXTIONS 3 RANDOMISED
CONN_TO_VALUE RANDOMISED
"""

config_inx = ["""
NODES 10
NODE_VALUES LIST
  1 1 1 1 1 0 1 1 0 0
CONNEXTIONS 2 TABLE
  0 2
  2 0
  2 1
  3 2
  9 9
  6 9
  1 4
  7 0
  3 8
  8 6
CONN_TO_VALUE LIST
  1 0 1 0
""",
"""
NODES 10    # loop 1 .. 128
NODE_VALUES LIST
  1 1 0 1 1 1 1 1 1 1
CONNEXTIONS 2 TABLE
  0 7
  6 7
  8 0
  6 9
  4 0
  8 9
  6 5
  9 2
  4 7
  5 1
CONN_TO_VALUE LIST
  0 1 1 0
""",
"""
NODES 10    # loop 1..63
NODE_VALUES LIST
  0 0 0 1 1 1 1 0 0 0
CONNEXTIONS 2 TABLE
  6 9
  9 8
  0 0
  6 5
  3 4
  1 3
  8 2
  1 4
  8 3
  0 5
CONN_TO_VALUE LIST
  1 0 0 1
""",
"""
NODES 10     # loops from 1 to 106
NODE_VALUES LIST
  1 1 1 0 1 1 0 0 1 0
CONNEXTIONS 2 TABLE
  4 5
  1 6
  1 7
  9 6
  0 0
  2 1
  2 3
  5 6
  1 3
  6 0
CONN_TO_VALUE LIST
  1 0 0 1
""",
"""
NODES 10    # Loops from 0..127
NODE_VALUES LIST
  0 1 1 0 1 1 0 1 0 1
CONNEXTIONS 2 TABLE
  6 4
  5 3
  2 7
  2 8
  7 9
  3 5
  8 4
  9 7
  1 8
  0 5
CONN_TO_VALUE LIST
  1 0 0 1
""",
"""
NODES 10    # loops 1..218
NODE_VALUES LIST
  1 1 1 0 0 0 1 1 0 0
CONNEXTIONS 2 TABLE
  9 1
  3 7
  5 9
  2 6
  2 1
  2 0
  3 5
  3 4
  8 1
  5 7
CONN_TO_VALUE LIST
  1 0 0 1
""",
"""
NODES 10
NODE_VALUES LIST   # loops 0..381
  0 1 1 1 0 0 1 1 0 1
CONNEXTIONS 2 TABLE
  7 3
  4 0
  3 9
  5 9
  2 3
  1 0
  0 2
  5 0
  6 0
  7 8
CONN_TO_VALUE LIST
  0 1 1 0
""",
"""
NODES 10    # loops 0..511?
NODE_VALUES LIST
  0 1 0 0 0 0 1 0 1 0
CONNEXTIONS 2 TABLE
  7 6
  2 8
  6 5
  7 0
  1 9
  5 2
  0 9
  3 8
  0 1
  7 4
CONN_TO_VALUE LIST
  1 0 0 1
""",
]

##
## End examples
##

def read_config(config):
    """
    Parameter:
        config:     Str. Textual configuration for RBN
        
    Returns:
        nodes:      Int. Count of nodes in network
        values:     List. Initial node values
        conn:       Int. Count of connections per node
        conns:      List-of-list. Connections per node
        conn2val:   List. Truth-table function outputs
    """

    nodes = values = conn = conns = conn2val = None
    line_gen = (l for l in config.strip().split('\n'))
    for line in line_gen:
        field = line.strip().split()
        record = field[0]
        if record == 'NODES':
            nodes = int(field[1])
        elif record == 'NODE_VALUES':
            if field[1] == 'RANDOMISED':
                values = random.choices([0, 1], k=nodes)
            elif field[1] == 'LIST':
                line = next(line_gen)
                values = [int(f) for f in line.strip().split()]
            else:
                raise ValueError('Cannot Parse NODE_VALUES')
        elif record == 'CONNEXTIONS':
            conn = int(field[1])
            if field[2] == 'RANDOMISED':
                conns = [random.choices(range(nodes), k=conn)
                         for _ in range(nodes)]
            elif field[2] == 'TABLE':
                conns = [[int(x) for x in line.strip().split()]
                         for num, line in zip(range(nodes), line_gen)]
            else:
                raise ValueError('Cannot Parse CONNEXTIONS')
        elif record == 'CONN_TO_VALUE':
            if field[1] == 'RANDOMISED':
                conn2val = random.choices([0, 1], k=2**conn)
            elif field[1] == 'LIST':
                line = next(line_gen)
                conn2val = [int(f) for f in line.strip().split()]
            else:
                raise ValueError('Cannot Parse CONN_TO_VALUE')
    return nodes, values, conn, conns, conn2val

        
def new_values(nodes, values, conn, conns, conn2val):
    "New from old values and RBN description"
    # Boolean conversion
    connected_vals = [sum(2**x * values[c] 
                          for x, c in enumerate(conns[n][::-1]))
                      for n in range(nodes)]
    new_v = [conn2val[cv] for cv in connected_vals]
    values[:] = new_v  # in place overwrite
    return new_v

def config_to_text(nodes, values, conn, conns, conn2val):
    "Convert internal RBN to textual form"
    txt = []
    txt.append(f"NODES {nodes}")
    txt.append( "NODE_VALUES LIST")
    txt.append('  ' + ' '.join(str(v) for v in values))
    txt.append(f"CONNEXTIONS {conn} TABLE")
    for c in conns:
        txt.append('  ' + ' '.join(str(cc) for cc in c))
    txt.append( "CONN_TO_VALUE LIST")
    txt.append('  ' + ' '.join(str(v) for v in conn2val))
    
    return '\n'.join(txt)

def pval(v, step=None):
    "print node values in order. 0 for 0, space for 1, for visibility"
    line = ''.join(' ' if bit else '0' for bit in v)
    print(f"{(step if step is not None else ''):>4}:  {line}")
    
if 1:
    # parsed interesting examples for possible cycle extraction 
    examples = [read_config(c) for c in config_inx]

 

END.