WOLFRAM NOTEBOOK

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:

[[ 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

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.]]

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]]

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....]]

Non-Self-Overlapping Networks

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

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]]

Causal Invariant Rules

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:

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.)

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:

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.

Here are the first few rewrites from the table above:

Many of these rewrites, at least if used on their own, cannot evolve for more than one step. The first one that can is the following:

Out of the 425 rules with at most 8 nodes in which R does not contain L as a subnetwork, most cannot continue to apply XXX at all. Here are the only ones that can continue to apply, but to do so they require progressively large initial conditions:

Rules with more than one rewrite

[XXXXXXXXXXXXXXXXXXXXXXX]

Simplified Pure Networks

If one looks at pure networks that involve no self loops and no multiple edges, then with additional restrictions on the rewrites allowed, it is possible to set up network substitution systems that involve only these kinds of simplified networks.

The number of pure networks with no self loops and no multiple edges is given by the following (number of nodes runs down the page; number of hairs runs across; the first column corresponds to closed networks):

Colored Networks

(Could also consider colored edges)

Ordered Networks

In ordered networks, different hairs at each node are distinguished. (Another possible type of network is a cyclic network, in which only the cyclic ordering of hairs is distinguished.)

Forms of Possible Networks

The following shows all ordered networks with up to 2 nodes:

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

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

[[[The simplest closed ordered networks are:]]]] [[should be clearer in picture above...]]

Note: these seemingly similar networks often have rather different characteristics in evolution processes...

Non-Self-Overlapping Networks

The following shows all non-self-overlapping ordered networks with up to 2 nodes:

The total number of non-self-overlapping ordered networks is as follows (a dot is used in place of 0):

Causal Invariant Rules

The following gives the total numbers of rewrites involving ordered networks with up 4 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.)

[[[[Not yet ready....]]]]

For rules with a single rewrite, the following situations occur:
• 1 hair: [[[Activity cannot continue for more than one step????]]]
• 2 hairs: [[[Probably all that can happen is "decorated ribbons"]]]
• 3 hairs: The simplest case involves 13 nodes; in this case L is always contained in R, so a nested structure is always produced
• 4 hairs: Even with 24 nodes, non-trivial behavior can potentially be generated.

[[[[Also look at reversible rules vs. general]]]]

The first non-trivial cases are h=3, 35 nodes, and h=4, 24 nodes.

Rewrites with 4 Hairs and 24 Nodes

The following summarizes the number of rewrites of various types:

If one ignores ordering, it turns out that there are only two different forms of rules of this type (assuming that L is not in R):

The numbers of cases corresponding to each of these forms of rules are as follows:

With any particular initial condition, many of these 276 rules will often give identical behavior, at least if ordering is ignored.

The pictures below shows the distinct forms of behavior obtained by starting from the first 2-node closed network shown above ({{4,5,6},{1,2,3}}).

Each row shows behavior with one representative rule. Within each block, the sequence of node numbers at successive steps is the same. (The number given in parentheses is the size of network obtained after 10 steps.)

The different cases covered by a given row all lead to the same networks, at least for 4 steps, if ordering is ignored. (In some cases different networks are obtained on subsequent steps, as discussed below.)

[[[Note: should check with NetSameQ[ ] etc.; using GraphDiameter only here...]]]

(The rule numbers here are:)

[For these rules, 1st differences are equivalent to # of nodes updated...]

Even though these results are just for a single initial condition, they will turn out to be fairly representative of what is seen with other initial conditions.

The most common forms of behavior seen here are:

Given a kernel ker one can reproduce the sequence n[t] using:

The following shows the forms of n[t] obtained for each block of cases shown above:

The table is left blank when n[t] does not satisfy a linear recurrence. Note that in these cases there seems to be only "one way" (up to reorderings) that the given n[t] sequence can be obtained. In cases where n[t] satisfies a simple linear recurrence, there are often "several ways" that the form of n[t] can be obtained.

Note that in a statistical approximation where nodes have probability p to be active on a given step, one will get n[t]==(2 p + (1-p) ) n[t-1]==(1+p) n[t]; or about (1+p)^t nodes on step t.

[[[XXXX One can look at the corresponding results for diameters of the networks.... ]]]]

For the particular initial condition discussed so far, the maximum fixed size that can be obtained is 8 nodes.

A straightforward form of linear growth is seen in case (d) (the red dots indicate nodes that will be updated at a given step):

Another form of linear growth, seen in case (e), consist in effect in "decorating" the initial conditions:

The different forms of case (h) yield slightly different patterns of linear growth (all these pictures are for step 10):

The rules used here take 2 nodes and replace them with 4 nodes. The total number of nodes n[t] will grow fastest if at each step, each pair of nodes is replaced—leading to n[t]=2^t. There are in effect several ways that such growth can be achieved, as indicated in the pictures below (which correspond to the different cases labeled (l) above). Each of these is show for step 5:

Here are the results at step 10, with cells that are updated no longer explicitly indicated:

Fibonacci-like growth (case (k)) can also be achieved in several ways:

In a sense, the most interesting cases are ones that do not satisfy a linear recurrence.

Case (j): [step 10]

Case (i):

The structure is slightly clearer in 3D: it has a regular nested form, but arranged on a sphere-like surface:

Case (f) (which is also reversible):

The number of nodes on successive steps here are:

Here is a plot of the log of their differences (or equivalently, of the log of the number of updated nodes at each step):

The ratio of these behaves as follows:

For the largest t shown here, the fluctuations are of period 4, and are roughly between 1.15 and 1.21.

[Using about 2.5 GB of memory:]

This shows the shells around a particular node:

[[[See additional material in Summary--02a.nb ]]]

[[From Todd:
Every other step it appears that the two "oldest" nodes get updated. In particular, the first two nodes, and the order of the nodes is similar to a tag system with the replacement behaving like
Append[Delete[g, pattern], replacement] ]]]

SHOW:
- causal networks
- activity patterns
- diameter growth rates
- distribution of distances ("small worlds", etc.)

However, there are non-trivial net germs.....

(Could also consider cyclic networks)

Causal Networks

Case (l) (2^t growth)

Case (k):

Case (g):

Case (j):

Case (i):

Case (f):

Other Investigations

Rules in which L appears in R

There are 264 rules in which L is non-self-overlapping, but appears in R.

This is a summary of their behavior:

The rules shown here are:

If L appears in R, there is always growth. For the particular case shown here, the growth is most often at the maximal rate. But other growth rates do occur. The following summarizes the growth rates found:

Note the appearance of quadratic growth:

These show Fibonacci growth (case (c)):

Several new forms of pure 2^t growth are seen:

Case (d) is the one example where the growth does not appear to follow a linear recurrence. After 9 steps it generates the following network:

Here is the sequence of sizes it produces:

The ratios seem close to 1.83, but exhibit some wiggles, and there appears to be no linear recurrence which fits them.

Properties of other rules

Planarity

The following rules generate nonplanar networks after 3 steps, starting from a simple 2-node network:

[[Is there a way to test for nonplanarity just by asking about the presence of certain graph minors?]]

Group Properties

There is an immediate correspondence between trivalent ordered networks and semigroups with 3 generators.

Take the labels associated with hairs at each node to be a, b, c or 1, 2, 3. These labels can then be thought of as corresponding to operations in the semigroup which transform the network. Applying the operation b, for example, consists in taking the network and from each node going to the node obtained by following the "b connection".

a, b, c thus correspond to the generators of the semigroup.

[[[[Associate with each label of hair from each node an operation a, b or c. Then consider taking the network, and applying these operations. The result is that each node is transformed to the node reached by following the corresponding hair. The set of these operations forms a semigroup with 3 generators. ]]]

Sometimes the semigroup associated with an ordered network is actually a group. For closed networks, the [[[a ???]]] criterion for this is:

Note that groups of order 2^n are so-called 2-groups...

Most likely these groups are so-called automatic groups....

Geometry

Note the presence of the tetrahedron and cube in the sequence of evolution of rule 45:

Shells

Networks of size 2^t probably have the feature that they are completely homogeneous: so that e.g. all balls around each node have the same structure.

However:

[[What is the relationship between the causal network and the group structure?]]

Here are shells within this object:

The object is basically two-dimensional, as one can see from the sizes of shells:

Here is the structure of shells within these networks:

The following show the growth rates of balls in each case: There is some slight hint of 3-dimensionality in some of the cases:

Different Initial Conditions

Size-4 Initial Conditions for All Rules

Looking at all 438 possible closed 4-node networks, and all 276 rules, the following are the number of occurrences of different linear recurrence growth rates: (note that trailing 0's in the kernels are ignored, thus ignoring initial transients):

The kernel {2,-1} corresponds to linear growth; the last two kernels with base 1 to quadratic growth. (The final one shows a period-3 oscillation.)

[[[Note: there may be additional linear recurrences to be found....]]]

The following shows which rules and which initial conditions lead to growth rates described by linear recurrences, and then what the base of their growth rate is. Black indicates cases where no linear recurrence is found.

[[[[How do the equivalence classes break up when there are more complicated initial conditions?]]]]

Study the case of rules which rarely grow, but when they do grow, give complex growth sequences.....

Multiple Rewrites

(Typically want to find cases based on rewrites where individually there is not too much growth.....)

When there are multiple rewrites, it is still always possible to have behavior that follows a single rewrite---unless that rewrite gets stuck, and can do no more.... [This follows from the non-overlapping of the different rewrites....]

Hence, look for 24 and 31 (or ? 21) in which the 24 stops after finite time.....

Speculate that one of two behaviors can happen when a node-reducing rewrite (such as 31) is added to a node-increasing one (such as 24). If previously the rule evolved to a constant-size network, that network can now get either bigger or smaller. But if it already grew............ [???]

24 (4 hairs) and 31(3 hairs)

The following table gives the various patterns of growth obtained with these rules. [[[FindRecurrence needs to be run for longer...]]] In all but two straightforward cases, the growth rate patterns are exactly the same as we already saw with single 24 rewrites.

Here is an example of a rule that shows a pattern of growth not observed without 31 rules (blue indicates the use of the 31 rule):

Here is a case where adding a 31 rule leads to different behavior:

There are exactly 72 cases in which adding the 31 rule changes overall growth rate. In all of these cases, as above, a pattern of growth of the form {2, 4, 6, 6, 6, ...} result is turned into one that shows a decrease at the end.

[[[Probably it will be more interesting to try more complicated initial conditions]]]

24 (4 hairs) and 42 (4 hairs)

There are 3 non-self-overlapping 2-node networks with 4 hairs, and 255 4-node such networks. From these, there are 276 valid 24 rewrites, and 24588 valid 42 ones, in each case assuming that R does not contain L. For any given valid 24 rewrite, it turns out that it can always be paired with one of 12 distinct sets of 2320 or 2328 42 rewrites to yield a valid overall rule. This results in a total of 642240 overall possible {24, 42} rules.

Starting with the simplest 2-node closed network one then finds the following. For 210 of the 276 24 rewrites, adding any valid 42 rewrites does not change the sizes of networks one gets (at least for the first 15 steps). However, for 60 of the 24 rewrites, there are 4 distinct patterns of growth, and for 6 there are 19.

Here is an example of the 19 patterns of growth:

Here is a typical actual evolution. The 42 rule is used in some early steps, but not later.

After 20 steps, the network produced is:

If only the 24 rule is included, only linear growth is seen:

[[[Perhaps also try everything on a more complicated network ...e.g. the tetrahedron]]]

Can one go from non-growing with 24 to growing with {24, 42}?

24 (4 hairs) and 22 (4 hairs)

Althoguh there are 24 valid 22 rewrites with 4 hairs, none can be combined with any 24 rewrites to yield valid rules. [[why??]] [[see ResultGenerator.nb]]

24 (4 hairs) and 22 (2 hairs)

There are 438 valid 22 rewrites with 2 hairs. All can be combined in either 87 or 90 ways with 24 rewrites with 4 hairs to yield valid overall rules.

At least starting from the simplest 2-node network, most do not lead to different patterns of growth than pure 24 rules. But in 12 cases, they lead to 2 additional patterns; here are the most interesting cases:

[[[NOTE: something has gone wrong here .... the second rule is not being used...]]]

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.

I understand and wish to continue anyway »