Network Substitution Systems

Stephen Wolfram

(Unfinished draft as of March 28, 2006)

Basic Concepts

Types of Networks

[XXX Rearrange]

In ordinary, pure networks, neither nodes nor connections have any intrinsic properties (such as "colors"), and the connections at a given node have no particular order. The following are convenient types of networks to consider:

pure networks	no node or connection labels; no distinguished ordering
colored networks	nodes with several possible colors
ordered networks	a definite order for connections at each node
cyclic networks	a cyclic order for connections at each node
directed networks	connections have directionality

(Universality of trivalent networks)

In the simplest case, each triple is treated as orderless. This corresponds to plain undirected networks.

One can also treat the triples are ordered. They might be cyclic, or they might have no ordering equivalences defined at all.
[There are three inequivalent group actions on sets of three elements, corresponding to these three types of models.]

Closed and Open Networks

Networks consist of nodes and connections. In the case of trivalent networks, every node has exactly 3 connections. In a closed network, all the connections go to nodes within the network. In an open network, there can be dangling connections, or "hairs". Network substitutions typically work by replacing one open network by another. In general, there can be self loops in which both ends of a connection go to the same node, and there can also be multiple connections between two different nodes. Many network substitutions generate and apply to such self loops and multiple connections.

Generally, we assume that the whole network on which substitutions are performed is closed. We consider open networks in the specification of the rules, and as a convenience in studying parts of networks.

closed networks

open networks

It is sometimes convenient to think of each node as having 3 half-edges connected to it. Each half-edge can either connect to another half-edges, yielding an ordinary connection, or can dangle to form a hair. In a closed network with n nodes and no hairs, there are exactly 3n/2 complete connections. (Self loops count as connections.) In an open network with h hairs, there are (3n-h)/2 complete connections. Note that closed networks must always have an even number of nodes.

A convenient textual representation of both pure and ordered networks is a list of triples, with the ith triple corresponding to the ith node. The jth node is then considered to be associated with the half-edges with labels {3j-2, 3j-1, 3j}. Each triple in the specification for the ith node then gives the labels for the three half-edges to which the half-edges from that node connect.

Here for example are then all the 2- and 4-node closed pure networks, with their textual representations:

	4,5,6,1,2,3	1↔2,1↔2,1↔2
	4,3,2,1,6,5	1↔1,1↔2,2↔2
	4,7,10,1,6,5,2,9,8,3,12,11	1↔2,1↔3,1↔4,2↔2,3↔3,4↔4
	{{4,5,7},{1,2,10},{3,9,8},{6,12,11}}	{1↔2,1↔2,1↔3,2↔4,3↔3,4↔4}
	4,5,7,1,2,8,3,6,10,9,12,11	1↔2,1↔2,1↔3,2↔3,3↔4,4↔4
	4,5,7,1,2,10,3,11,12,6,8,9	1↔2,1↔2,1↔3,2↔4,3↔4,3↔4
	4,7,10,1,9,11,2,12,5,3,6,8	1↔2,1↔3,1↔4,2↔3,2↔4,3↔4

In pure networks, in which the order of connections at a node does not matter, an alternative representation can be given, consisting just of node-pair rules i↔j representing connections between nodes i and j. For ordered networks, this no longer provides a unique specification. For a closed network, one can convert to the node-pair specification using:

Sort[Join[Union[Select[#,SameQ@@#&]],Select[#,Less@@#&]]&[Flatten[MapIndexed[#2[[1]]↔Quotient[#+2,3]&,list,{2}]]]]

where the Selects handle self-loops and multiple connections respectively.

For an open network, hairs can be numbered sequentially, and are conveniently represented by

Here are all the 3-hair pure networks with 4 or fewer nodes:

	 1 , 2 , 3 	1↔ 1 ,1↔ 2 ,1↔ 3 
	 1 ,4,7,2,9, 2 ,3, 3 ,5	1↔2,1↔3,1↔ 1 ,2↔3,2↔ 2 ,3↔ 3 
	 1 , 2 ,4,3,7,8,5,6, 3 	1↔2,1↔ 1 ,1↔ 2 ,2↔3,2↔3,3↔ 3 
	 1 , 2 ,4,3, 3 ,7,6,9,8	1↔2,1↔ 1 ,1↔ 2 ,2↔3,2↔ 3 ,3↔3

For ordered networks, it is necessary in effect to distinguish three separate "attachment points" for the three connections at each node. One convenient graphical way to do this is to represent each node not as a single disk, but instead as a combination of red, green and blue triangles.

Here are some examples:

	 1 , 2 , 3 
	 1 , 2 ,6, 3 , 4 ,3
	6,9,12,11,7,1,5,10,2,8,4,3

[[[XXX The images should have little numbers at each hair]]]

Structure of Possible Rules

[[[Probably use ℒ and ℛ here....]]]]

A substitution rule consists of a collection of rewrites, each of which specifies that some open network L is to be replaced by an open network R, with some specified correspondence between the hairs in L and R. For LR to be a valid rewrite, the number of hairs in L must be the same as R. With the representation of networks described above, this means that the hair with a given label in L can always be associated with the hair with the same label in R.

There is one further condition needed for a rewrite to be valid: in effect that R be no less symmetrical than L. Consider the following three rewrites:



The first of these rewrites satisfies the symmetry condition; the other two do not. In effect what goes wrong is that when one matches L there is no way to determine which hair should be the distinguished one in R. In general, for a rewrite to be valid, it must be the case that for every possible permutation of the hairs in L, there must be some possible permutation of the hairs of R that can undo its effect.

Somewhat more formally, the h! possible permutations of the hairs in an h-haired network N form a group S[N]. There will then be some subgroup Aut[N] of these permutations which leave the structure of the network unchanged (i.e. yield a network that is the same up to network isomorphism). Any rewrite defines a map f from the permutation group of the hairs of L to the permutations group of the hairs of R. A rewrite is valid if f[Aut[L]] is a subgroup of Aut[R].

When one constructs rewrites, there are in general multiple ways to set up hair associations between given networks L and R. The following are the smallest pure networks where such multiple associations exist. (In each of these cases, there are exactly two such ways.) These rewrites with different hair associations are considered distinct.



[[[[Font size directive is not working....]]]]]

[Implementation note: VaryRewrite[L -> R] returns the minimal list of possible literal rewrites with different hair associations. It works by double coset enumeration....]

(It is rarer for there to be symmetries in ordered networks, but the same issues apply.)

[[[We assume that we are not interested in rules that lead to disconnectedness in the network....]]]

Causal Invariance

Causal invariance is the condition required to have a unique causal network for the evolution of a network substitution system.

To guarantee causal invariance in all possible evolutions according to a particular rule, the rule must have the property that none of the networks

that appear in its rewrites can overlap themselves or each other.

Here are all the pure non-closed networks with 7 or less nodes that do not overlap themselves:

This shows which of these networks overlap each other:

Note that the network with a single node and three hairs overlaps all networks. (It overlaps itself only trivially.)

Note that closed are never considered to overlap any other networks: they do not have hairs that can be attached into other networks.

The pure networks with 3 or less nodes that do overlap themselves are:

This shows for first 4 of these networks

what the minimal networks are in which each

can appear in more than one overlapping way:

[[ Where there is causal invariance, it implies that there is a meaningful notion of "steps of evolution": at each step one performs all possible non-overlapping substitutions at that step. ]]

Effective Causal Invariance

(I.e. causal invariance for particular initial conditions, but not for all possible initial conditions)

Additional Related Properties

(If the

are also non-overlapping, and



corresponds to a valid rewrite, then the rules are reversible...)
(If the rules are reversible, this means that evolution with reversed rules will correspond to evolution backwards from final states to initial ones. This also means that all evolution must be one-to-one, in the sense that there is a unique initial condition that evolves to a given final state.)

Example of a reversed rule: (note that when the system reaches the beginning, its rules no longer apply, and it stops....)





Network Germs

(What is the minimal open network that can continue to show activity for t steps with a given substitution rule?)

[Include implementation sketch when appropriate ... as notes]

Growth and Decay Rules

(Is L contained in R?)

Characteristics of Networks

(Dimension estimates; embedding data; etc.; cycle structure?)

Causal Networks

(Each event is the application of a rewrite. An event A is considered to lead to an event B---and is connected in the causal network---if nodes in the output from A overlaps nodes in the input to B.)

(For strings, one can have multiple edges connecting events ... corresponding to symbols that are shared between them.)

Pure Networks

Forms of Possible Networks

The following shows all pure networks with up to 4 nodes: [[XXX put correct spacing into the TextBand etc.]]

1 nodes; 1 hairs

1 nodes; 3 hairs

2 nodes; 0 hairs

2 nodes; 2 hairs

2 nodes; 4 hairs

3 nodes; 1 hairs

3 nodes; 3 hairs

3 nodes; 5 hairs

4 nodes; 0 hairs

4 nodes; 2 hairs

4 nodes; 4 hairs

4 nodes; 6 hairs

The total number of pure networks is as follows (a dot is used in place of 0): [[XXX label with "hairs" across the top; nodes down]] [[give totals]]

	0	1	2	3	4	5	6	7	8	9	10	11	12
1	·	1	·	1	·	·	·	·	·	·	·	·	·
2	2	·	2	·	1	·	·	·	·	·	·	·	·
3	·	3	·	3	·	1	·	·	·	·	·	·	·
4	5	·	9	·	6	·	2	·	·	·	·	·	·
5	·	12	·	19	·	10	·	2	·	·	·	·	·
6	17	·	49	·	50	·	21	·	4	·	·	·	·
7	·	67	·	147	·	114	·	39	·	6	·	·	·
8	71	·	338	·	475	·	291	·	84	·	11	·	·
9	·	441	·	1326	·	1399	·	697	·	172	·	18	·
10	388	·	2744	·	5159	·	4211	·	1756	·	376	·	37

The first column here represents closed networks, with 0 hairs.

The following shows all closed pure networks with up to 8 nodes: [[columns should just have a max width....]]

2 nodes (2 networks)

4 nodes (5 networks)

6 nodes (17 networks)

8 nodes (71 networks)

Non-Self-Overlapping Networks

The following shows all non-self-overlapping pure networks with up to 8 nodes:

1 nodes; 1 hairs

1 nodes; 3 hairs

2 nodes; 2 hairs

3 nodes; 1 hairs

5 nodes; 1 hairs

7 nodes; 1 hairs

8 nodes; 2 hairs

The total number of non-self-overlapping pure networks is as follows (a dot is used in place of 0): [[XXX label with hairs across the top; nodes down]]

	0	1	2	3
1	·	1	·	1
2	2	·	1	·
3	·	1	·	·
4	5	·	·	·
5	·	3	·	·
6	17	·	·	·
7	·	16	·	·
8	71	·	3	·
9	·	135	·	·
10	388	·	75	·

Causal Invariant Rules

A causal invariant rule must consist of valid rewrites



with the

all non-overlapping and non-self-overlapping.

A simple example is the following:



Evolving according to this rule gives a very simple nested structure in which the total number of nodes triples at each step:

step 1 (1 nodes)

step 2 (3 nodes)

step 3 (9 nodes)

step 4 (27 nodes)

step 5 (81 nodes)

step 6 (243 nodes)

Whenever

has the simple form shown here, the network substitution system is in effect neighbor independent, and it is inevitable that it must yield just a simple nested structure.

The following gives the total numbers of rewrites involving pure networks with up 8 nodes. [[[Label the plot across the top with "hairs"]]] In each case, the second column for a particular number of hairs gives the number of rewrites in which L does not appear as a subnetwork of R. (Note the first column in each case includes identity rewrites in which a network is replaced by an identical network.)

	1		2		3
11	1	.	.	.	1	.
13	3	1	.	.	1	.
15	12	4	.	.	1	.
17	67	19	.	.	4	.
22	.	.	2	1	.	.
24	.	.	8	4	.	.
26	.	.	32	14	.	.
28	.	.	165	61	.	.
31	1	1	.	.	.	.
33	3	2	.	.	.	.
35	12	10	.	.	.	.
37	67	57	.	.	.	.
51	3	3	.	.	.	.
53	9	9	.	.	.	.
55	36	33	.	.	.	.
57	201	195	.	.	.	.
71	16	16	.	.	.	.
73	48	48	.	.	.	.
75	192	192	.	.	.	.
77	1072	1056	.	.	.	.
82	.	.	6	6	.	.
84	.	.	26	26	.	.
86	.	.	130	130	.	.
88	.	.	841	837	.	.

Here are the first few non-trivial rewrites from the table above:







All rules allow evolution for one step, since they can just perform a rewrite they contain. But often a rule will not allow evolution for more steps: no rewrite applies to any network that can be generated after one step.

This is the situation for the first network shown above. Most of the remaining rewrites shown have the property that L appears as a subnetwork of R. The results after 4 steps of evolution are shown below; in each case a repetitive or nested structure is generated:



The following are the first few rewrites in which L does not appear as a subnetwork of R:







None of these can evolve for more than one step. Of those from the table above, the smallest that can evolve for two steps are as follows:







None of these rewrites, however, can ever increase the number of nodes, and thus none can lead to evolution that continues to grow from a fixed initial condition.

The following rewrites can in principle do this:







However, in practice these rewrites again end up requiring larger and larger initial conditions in order to avoid becoming "sterile" after some fixed number of steps. Here are the first few networks that can arise after two steps... [XXXX]



[XXXXXXXXXXXXXXXXXXXX More to add XXXXXXXXXXXXXXXX] [Try running from small closed networks, etc]
[So far, we have no example for pure networks that shows non-nested/repetitive continuing activity.]

Reversible Rules

A necessary condition for rules to be reversible is that R as well as L is not self overlapping. The number of rewrites that satisfy this condition is:

	1		2		3
11	1	.	.	.	1	.
13	1	1	.	.	.	.
15	3	3	.	.	.	.
17	16	12	.	.	.	.
22	.	.	1	.	.	.
28	.	.	2	2	.	.
31	1	1	.	.	.	.
33	1	.	.	.	.	.
35	3	3	.	.	.	.
37	16	16	.	.	.	.
51	3	3	.	.	.	.
53	3	3	.	.	.	.
55	9	6	.	.	.	.
57	48	48	.	.	.	.
71	16	16	.	.	.	.
73	16	16	.	.	.	.
75	48	48	.	.	.	.
77	256	240	.	.	.	.
82	.	.	3	3	.	.
88	.	.	8	4	.	.

To achieve reversibility, however, it must also be the case that RL corresponds to a valid rewrite. With this condition added, the numbers of possible rules are as follows. Note that for rewrites involving a single hair, there is no hair interchange symmetry, so RL must always be a valid rewrite.

	1		2		3
11	1	.	.	.	1	.
13	1	1	.	.	.	.
15	3	3	.	.	.	.
17	16	12	.	.	.	.
22	.	.	1	.	.	.
28	.	.	2	2	.	.
31	1	1	.	.	.	.
33	1	.	.	.	.	.
35	3	3	.	.	.	.
37	16	16	.	.	.	.
51	3	3	.	.	.	.
53	3	3	.	.	.	.
55	9	6	.	.	.	.
57	48	48	.	.	.	.
71	16	16	.	.	.	.
73	16	16	.	.	.	.
75	48	48	.	.	.	.
77	256	240	.	.

	0	1	2	3
1	·	1	·	1
2	2	·	1	·
3	·	1	·	·
4	5	·	·	·
5	·	3	·	·
6	17	·	·	·
7	·	16	·	·
8	71	·	3	·
9	·	135	·	·
10	388	·	75	·

	0	1	2	3
1	·	1	·	1
2	2	·	1	·
3	·	1	·	·
4	5	·	·	·
5	·	3	·	·
6	17	·	·	·
7	·	16	·	·
8	71	·	3	·
9	·	135	·	·
10	388	·	75	·

	0	1	2	3
1	·	1	·	1
2	2	·	1	·
3	·	1	·	·
4	5	·	·	·
5	·	3	·	·
6	17	·	·	·
7	·	16	·	·
8	71	·	3	·
9	·	135	·	·
10	388	·	75	·