A New Kind of Science: The NKS Forum > Pure NKS > Enumerating Network Trees
Author
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

Enumerating Network Trees

Here introduced is an attempt to nail down an some kind of enumeration scheme for all possible trees of a certain kind. The reason these network trees are considered special is that they may be used as more practical conditional requirements for rules that evolve networks.

A typical 'rule' in a network system for a given node will have a structure so that the connectivity data of the nodes the target node is connected to must be in some way specified. It is suggested here that these trees, identified each with a unique number, can be used as a generalized form of acquisition of node neighbor relational data which specifies the number of outgoing connections for each node reached at each layer.

These specific trees created here are all (save a few trivial ones not made 'at the beginning' for inelegant reasons) possible trees of distance 2 from a given root node. Every one of them so far as I can tell is unique. All I did was use Mathematica's Partitions function to generate the actual orderless groupings of addends and use them to represent nodes with the number of addends of a particular kind as the number of nodes at level 1 with the actual value of the addend as the nodes found by those nodes on level 2.

This method accomplishes experimental usage of the objects but is in no way efficient in getting the actual network for the given number.

Anyways, the basic structure of these trees are what we could call nested orderless sets. If someone knew how to calculate and enumerate all possible 'nests' of orderless sets that specifies either a terminating node or a node that leads to more nodes, then I think they would be able to understand how to do this better than I do.

There are a number of ways to actually interpret the 'spread'. If the node scanned was actually the corner of a cube network, the neighbor data can be assessed in at least these ways:

• From the target nodes comes 3 new nodes, from those nodes each comes two nodes, then from each of those nodes comes a single node out, and then nothing. This way excludes previous nodes and terminates when no new nodes are available to traverse.

• From the node comes 3 nodes, then from each of those come 3 nodes, and then 3 nodes each come out of those, then three nodes out of those again. This method counts nodes regardless of whether they have been hit already or not. This method allows for nodes to distinguish exactly how many nodes radiate out of a given neighbor, so that nodes at different locations can identify the same node in the same way regardless of how its neighbors interact with it.

There might be more ways that I am not aware of.

In this way all possible relative network topologies have a way to 'funnel in' to simpler forms of classification in order to change the node at hand. Nodes can be changed in the following ways that I am aware of:

• The node can be deleted with all of its immediate connections. At range 2 and beyond, different branch-ends on the tree can correspond to the same nodes. Because of this it is non-trivial to implicate deletion of specific neighbors to a node on the next step and not others 'on the other side of the tree' that are the same node. But when precedence is assigned to each possible node state that can be determined then it turns out that these decisions can be made ( I think ).

• The node can have its color changed. The same kinds of issues that exist with node deletion exist here. I don't know how to enumerate networks of these kinds with different color configurations. Might sums be easier. And if you want to change the color of nodes in the local neighborhood then a precedence must be set for all of the colors. This gets even more hairy, but still potentially useful when all nodes of a network are being operated on at the same time. All I can say is that when you allow a precedence for each color, a node can receive multiple instructions to change and be able to pick one. Precedence on possible states is one way to make this happen, but there are also other ways, like counting the majority or 'votes' for a node to change a certain way and either have an added precedence on states when results are even, or choose randomly.

Many variations of network rule systems can be potentiated by these trees, of which I imagine containing some interesting simple programs.

Attachment: enumnt-4.nb

Last edited by Jesse Nochella on 04-28-2006 at 09:15 PM

Report this post to a moderator | IP: Logged

04-28-2006 08:50 PM
Jesse Nochella
WRI

Registered: Mar 2004
Posts: 132

One way to structure a tree would be to indicate a number of nodes as the leafs of the tree. These leafs are all known to converge to a single point at some time eventually. A node is assumed to 'have been spawned by' another node by creating a single new node attached to it repeatedly for some number of steps until it converges. Two or more nodes have to converge at the same time. Instructions for all nodes can be given in one piece of information, a sequence of numbers, to the layer. The sequence is a partition of the number of nodes. The number of nodes on the next step is the number of numbers in the previous sequence.

There also might be an additional piece of information required. The nodes that converge to the set of new nodes must be designated which 'group' of convergence they belong to for all nodes with different trees attached to them. In other words, if one node is the bottom of a pitch fork, and another is the bottom of a long stick-like thing, then it matters whether these two nodes condense to the same node or to two other nodes, and I don't think that information can be derived solely from the partition sequence. That's all I can figure out so far.

Report this post to a moderator | IP: Logged

04-28-2006 08:51 PM
mohammed1

France

Registered: Apr 2006
Posts: 17

I notice you post a lot on this forum. this is complicated english. i try hard to follow your english but it is too complicted maybe it is not the words but the way you place words. can you explain what this is to me ?

Report this post to a moderator | IP: Logged

04-30-2006 03:35 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us