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:
- NODE
- NODE_VALUES
- CONNECTIONS
- CONN_TO_VALUE
NODE record
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:
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
- 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.
No comments:
Post a Comment