How to Build a Network Automaton

Here is a cool new kind of complex system I am thinking about a lot that we might call a “network-automaton” or a “graph automaton” — a system that evolves networks (graphs) over time. This rule is similar to cellular automata rules such as the famous “Life” rule discovered by John Conway, however instead of computing the states of cells on a grid, it computes the shape of a network. In a nutshell this system applies a simple local rule at each node in a network that determines what other nodes it should connect to in the next step of time as a function of the connections each of those nodes had in the previous step of time. This yields complex network structures and interesting dynamical emergent behaviors over time — networks that grow and change as time goes by, networks in which there may even be stable or cyclical topological patterns that move across the network, as well as interactions between such patterns (topological interactions) that resemble the interactions between fundamental particles.
Network automata of the sort I propose here may be useful for modeling the structure and dynamics of a wide range of systems from physical systems, to biological systems, to the growth and development of computer networks, to social networks, business networks, and other types of higher-order networks.
(By the way — I would really like an open-source application — in Java perhaps — for generating and visualizing network automata rules such as those in this article. If you are a good programmer and would like to volunteer to make some software that can simulate the dynamics of the class of systems I propose here, please email me! I think this will be a very interesting avenue of exploration, and such a tool could be extremely useful.)

See the rest of this article for a detailed description of how to build a working network automaton….


Here is how a network automaton works….
We define a “network” as a set of locations called “nodes” that may be connected by “links.”  Nodes are represented as black dots, spaced regularly on a white colored plane. Links are black or white lines that connect pairs of dots. A black line corresponds to a link that is “on” and a white line corresponds to a link that is “off.”
We define the state of a given node as the number of “on” (black colored)  links it has to its neighbor nodes.
Now at each step in time t, for each node, we draw black or white links from it to each of its neighboring nodes, according to a function of the states of each of its neighboring nodes at time t-1. In other words, we update the link structure around each node as function of its local neighborhood.
For example, we draw either a black or white link between each node and each of its neighbor nodes at time t as a function of the state of each neighbor node at t-1. The state of each neighbor node is the number of “on” links that it has at time t-1. In other words, this rule deterimines the number of links of each node to its neighboring nodes as a function of the number of links of each of the nodes in its neighborhood.
One important note — You may have realized in visualizing this that there will be cases in which “conflicts” occur. For example, for a given pair of nodes A and B, A may compute the link A–>B as “on” but B will compute the link B–>A as “off.” What do we do in such cases? One option is to choose one of these choices randomly, another option is to have them “cancel out” to “off” or to “sum” them to “on.” An even more useful option is to keep both states. We can call this a “superposition” of states. We can represent this “indeterminate” state by a new color of link — not white or black, but perhaps grey. Our rule can be modified such that each node only sees it’s relative state for that link. Over time the network can “collapse” these indeterminate states as nodes come into agreement. For now, let’s just keep both states. So every link has two states, one in each direction but nodes can only “see” the links that correspond to their perspectives. This allows for the measurements that nodes make of one another to be relative to their own perspectives. Another way of viewing this is that there actually exists two links between every pair of nodes, one in each direction. Each link has 1 state. This is equivalent to the previous suggestion.
So now how might this system behave?
Let’s say that we are computing the state of a particular node, K. To do so, we must look at each of the nodes in K’s neighborhood. K has 8 neighbors named N, S, E, W, NE, SE, NW, SW that correspond to the nearest nodes at major points of the compass around K on the plane (Note: other neighborhood structures could also be possible such as just four neighbors N, S, E, W, or even hexagonal neighborhoods but for this example we will just use 8 neighbors). First we look at neighbor N and get its state: N’s state is the number of “on” links it has to other nodes. Our state-function might work as follows: If N’s state is 1 or 2 then we set the link from K to N equal to “off.” If N’s state is 3, 4, or 5 then we set the link from K to N equal to “on.” If N’s state is 6, 7 or 8 we set the link from K to N to “off.” After we finish this for N, we then do the same thing for the next neighbor, S. (Note: I have not tested this particular state-transition rule, it is just an example, there is a large set of possible rules given that each node can have one of up to 8 states. It would be interesting to try many of them). Once we go through all 8 neighbors of K, we have computed the new state of K (the state of K at time t+1) and so we then move on to the next node K+1. Once we go through all the nodes in the graph, we draw the results of the updated nodes and links. Then we start the cycle again for the next step of time, t+1.

Rules such as those described above result in graphs that evolve and change shape over time, depending on various initial conditions (sets of initial “on” links). Depending on the state-function chosen and the initial conditions we may find “rules” with more or less “interesting” behaviors. It is certain that some of these rules will display interesting emergent dynamics. This is similar to cellular automata rules such John Conway’s game of Life. The difference is that here we are using similar techniques — a set of interacting local rules — to evolve the topology of a network.

But this is just the beginning. We can devise many more intersting state-transition rules than the simple example above.
For example we could use probabilities —
Instead of stating that if K’s neighbor N has z number of links an “on” link is definitely created from K to N, we could instead use a probability P that a link is created. The probability P could in turn be computed as a function the state of N at time t-1, or perhaps as a function of the state of K at t-1, or of the states of both N and the and K at t-1, or perhaps as a function of the states of all of K’s neighbors at t-1, or as a function of the states of the nodes that K is linked to at t-1, or perhaps even as global property such as a function of the states of all nodes at t-1. As you can see there are many interesting variations to explore here.
Another interesting type of rule would be to have more than just “off” and “on” links. Instead, color the links as a function of the states of the nodes they point to at t-1, or of the states of both nodes they connect at t-1. This enables the formation of rules that treat the link-states as factors to amplify or dampen the measured states of the nodes they point to. Thus when K measures the state of its neighbor N, the result of that measurement might be a function not only of the number of links N has at t-1, but also a function of the state of the link from K to N at t-1.
We can also go another step further in our explorations. Rather than have purely local neighborhoods, we could combine the above concepts to allow for non-local neighborhoods. In this case, at each step in time, each node computes the state of the link between it and every other node. To accomplish this, each node considers every other node to be in its neighborhood. It looks at the state of the link connecting it to each other node at t-1 as well as the state each other node, and possibly of its own state at t-1 as well, and based on these it computes a state for the link from it to that node at time t. By configuring the rule carefully such as system can be made to evolve various network topologies and dynamics over time.
Another interesting potential modification of the above non-local rule is to compute the state of each node at time t as a function of the link-states and/or node-states of only those nodes to which it has links above a certain threshold (or of a certain value or range) at time t-1.
A final note. We can represent all the information in this system in an array. Let U be the number of nodes. This array therefore has U * U cells in it. Cells are named by their x,y coordinates in the array. So for example, cell(1,5) refers to the cell at location x=1, y=5 in the array. Now we adopt the convention that the “nodes” are represented by the cells where x=y, for example, (1,1), (2,2), (3,3) and so on. Cell (1,1) represents “node 1” and cell (2,2) represents “node 2” and so on. The “links” are all the other cells. So for example, cell (1,2) is the link “from node 1 to node 2,” and cell (2,1) is the link “from node 2 to node 1.” In each cell we will also store a number representing the state of that cell. So we will add another dimension, s, to this array, for the states. So each cell has values (x,y,s) — it’s xy coordinates in the array and its state. This 3 dimensional array is sufficient to represent all the information in the system.
It is important to realize that this array contains a link from each node to each other node. If that link has a value of zero it can be considered to be “off” and thus the nodes it connects may be considered to be non-local to one another. If that link is non-zero however, then the nodes it connects are local to one another. Depending on what the state of each such link is, any desired topology can be modeled. This in turn depends on the functions we use to compute states. We can choose to have a fixed “Euclidean neighborhood” in which every node has 8 nearest neighbors that never change, or we can use a rule such as the final rule above in which every node is in the neighborhood of every node. In the latter case, using a probability function or other more subtle functions the states of the links connecting nodes to all other nodes can change such that various local neighborhood structures can emerge over time in feedback with the node states. This is ultimately a more general model, but probably not a good starting point due to the complexity of visualizing it (it may require more dimensions — 3D, 4D or more).


– Andy Ilachinski, e-mailed a very helpful response to this article in which he provided a number of links to related research on what are called Structurally Dynamic Cellular Automata or SDCA’s. What I have proposed above is an approach to making SDCA’s in which the neighborhood topologies are the states of the nodes in the network. In other words, each node’s state is its local topology. Andy gave me some references to very interesting papers on the subject, including:
* There are some wonderful illustrations of the output of SDCA’s in Andy’s book “Cellular Automata: A Discrete Universe”. These illustrations are exactly what I have been visualizing — essentially beautiful sequences of the evolution of various topologies based on local rules. They vary from simple geometric symmetries to fascinating complex and chaotic networks. If you are interested in this I can’t recommend enough that you take a look at this book. Anyone working on the physics of networks should know about this.
* Steve Majercik wrote a Manfred Requardt

– The rules I am interested in compute the topology of each neighborhood as a function of the topologies of neighborhoods it is connected to. In the most general case (the last rule above), every neighborhood is connected to every other neighborhood, but the links have states as well. By having both node states and link states we can generate very sophisticated rules in which the way that any two nodes interact is a function of their link states (one in each direction). Thus the topologies of neighborhoods are functions of the states of nodes and links that comprise them. As these states change over time the topology of the network evolves. This effectively links the “energy in space” to the “shape of space” — unifying them at a fundamental level. Everything reduces to topology.

– In the final model that I came to in my thinking on this subject I realized that in the general case every node should have 2 directed links with every other node (on in each direction “to” and “from”). The state of a node is a function of the state of all its links. The state of each link is a function of the state of the node it comes from (or alternatively, of the states of both nodes it connects). I believe this model is capable of containing any topology, including systems in which the topology and geometry of space from the perspective of any location is relative (this is the value of having 2 directed links connecting each pair of nodes — it enables each node to measure the other independently of the other’s measurement of it — the link can can have a different state in each direction). This is basically a superset of the SDCA concept — any SDCA can emerge within such a network.

Social tagging: > > > > > > > >

Comments are closed.