[ Welcome to NKS - SJSU ]

 Networks and Space

by Christine Meyer

 

Home | Links | Applets | Papers | Class Plan | Team

 

Networks and Space

 

 

 

TABLE OF CONTENTS:

1.     Abstract:. 1

2.     Introduction.. 2

3.     Network Design Patterns.. 2

4.     Establishing Rules for Connection Rerouting.. 4

5.     Comparison between Networks and Space.. 4

6.     Combining Space and Time.. 5

7.     Causal Networks.. 6

8.     Random Networks vs Scale-Free Networks.. 7

9.     Conclusion.. 7

10.       References.. 8

 

1.   Abstract:

Networks are in existence in many different forms.  Networking is used for communication between groups of people.  Networks of nerve cells also exist in the brain.  Networks are used for internet services, which is the most familiar use of networks.  The distribution of nodes throughout the network may have several different forms.  This paper discusses some of these networking patterns.  These patterns can be created by applying different network automaton rules for adding new nodes to a network structure.  As new nodes are added, the connections between the nodes are changed.  Also networks are compared to space and a comparison made to determine if the network model is a good model to use to describe space.  Time is discussed as a fourth dimension.  Since time needs to be expressed in a network format, causal networks are discussed.  Finally, since the internet is one of the largest networks in existence, scale-free networks are discussed.

2.   Introduction

A network is a collection of nodes with connections between these nodes.  For network automata, rules are established describing how these connections will change from one cycle to the next cycle.  Rules are also established for adding new nodes to the existing structure.  Initially, the simplest form of a network will consist of nodes with two connections.   By limiting the number of outgoing connections, the various combinations can be described easily.  Several design patterns are discussed below.

 

But to apply a network design to characteristics in space, the number of connections must be increased to three connections.  Since nodes with additional connections can be expressed as nodes with three connections, adding more than three connections does not add any value.  Therefore, network designs with three connections are also discussed.

 

The internet is one of the largest networks.  The internet is a scale-free network.  There are some nodes with few connections while other nodes have many connections.  The growth usually appears around nodes that are already congested, which are the popular sites like yahoo and google.  The internet is discussed in detail below.

3.   Network Design Patterns

A connection from a node can either wrap back to the same node or connect to another node.  The number of combinations increase as more nodes are added to the network.  For one node, there is only one pattern available.  The connections must wrap back to the same node.  For two nodes,  there are three different combinations.  For three nodes, there are 14 different combinations.    So as the number of nodes increase, the number of combinations increase exponentially.

 

The nodes can be connected horizontally, displaying the following pattern in one dimension:

           

 

 

For simplicity in drawing diagrams, each connection is considered bi-directional.

 

The above pattern can be expanded to two and three dimensions.  See below for the two dimensional diagram. 

 

 

 

 

 


There are still only two outgoing connections per node, but each block of nodes are connected to four neighboring blocks to form a grid pattern.

 

Tree diagrams can also be represented using nodes with two outgoing connections as illustrated below:

 

 

 

 

 

Tree diagrams can be expanded to represent infinite tree patterns.  The nodes in a tree can be laid out in different design patterns as shown on page 196 of Wolframs book “A New Kind of Science”.

 

It is also possible to form a nested geometrical structure using nodes with two connections as illustrated below:

 

 

 

4.   Establishing Rules for Connection Rerouting

There are several different possibilities for rerouting connections from a node.  To describe the two connections, there is one connection above the node, and one connection below the node.  Here are some possibilities:

 

(1)               The rerouting is established by first following the “below” connection and then following the “above” connection from the node.

 

(2)               The “above” connection from the node is looped back to the same node.  In some cases, this results in disconnected nodes.  Since there is no logical rule for connecting these nodes, the nodes are not tracked.  Therefore, the number of nodes in a network decrease.

 

(3)               It is possible for nodes to increase by add a new node.  One method is to route the connections identical to an existing node just below it.

 

(4)               Another method  for adding a new node is to route the connections in reverse of an existing node just below it.

 

But the best results are obtained by applying different rules based on the local structure near each node.  One technique in accomplishing this task is to look at the connections coming out of each node.  If both connections lead to the same node then use one rule, and if the connections lead to different nodes then use another rule.

 

It is also possible to increase the number of nodes used in the computation for the rule.  This will allow for more variance in the rule which leads to random behavior.

5.   Comparison between Networks and Space

With only two connections, only trivial network designs can be created.  Therefore, to compare networks with space, the number of connections have been increased to 3 connections.  A wider range of networks can now be created.

 

In space, one of the ways to describe the distance between two points is to find the distance of the shortest path between two points.  In a network, it is possible to find the shortest path between two nodes by finding the minumum number of connections between two nodes.

 

There are several algorithms which find the shortest path between two nodes.  The most popular is Dijkstra’s Algorithm.  This algorithm takes into consideration a numeric value for each path, but in this case the value of each connection will be the same.

 

To show that networks are similar to space: for any dimension d and distance r, the number of nodes that appear in it is limited to rd-a.  There are several networks which meet this requirement.  But the question arises as to whether all networks meet this requirement.  In Wolfram’s book on page 479, network (i) is a tree-like structure with 3r nodes at distance r.  This example grows faster than to rd.  Therefore, this network cannot be related to ordinary space.

 

So the networks which we choose to model must also correspond to ordinary space in three dimensions as described above.  The rules for updating the network must also preserve this requirement.

6.   Combining Space and Time

To show passage of time is just a matter applying the cellular automaton rules.  The nth unit of time will be the nth cycle.  This is much different than moving in space.  To move in space it is just a matter of moving to a different location.  But if we look at time as simply another dimension (fourth dimension) then it should be possible to move to a different time period just as we handle space.  We can create a time machine.

 

The question arises, is it possible to represent space-time as a four-dimensional network?  On page 483 of Wolfram’s book, there are several diagrams of networks with  dangling connections which are possibilities for a four-dimensional network.  It turns out that only three of these networks can be used (c, d, f).  In each of these cases, an infinite set of networks are allowed.  But only one network can actually represent our complex spacetime universe.  What should that network look like?

 

There are 690 non-trial networks if we limit the distance to two.  We can eliminate 681 because a complete network cannot be formed.  The six remaining allow an infinite sequence of networks, but three allow just single networks.  Therefore, there is only three networks remaining.

 

The question remaining is whether there is a simple set of constraints which can be used to establish a complex network.  Wolfram doubts that it is exists.

 

The universe may evolve in time based on explicit rules which symmetry is built in between space and time.  Wolfram doubts that this is possible either.  Therefore, the conclusion is that there is no direct correspondence between space and time.

7.   Causal Networks

A cellular automaton updates all of its cells at one time.  It is very unlikely that the universe has a global clock and updates everything at once.  Instead of updating all cells at once, it would be more realistic to update a few cells at a time.  The most logical choice would be a mobile automaton or turing machine.

 

The question arises as to whether the universe can be modeled using a mobile automaton.  Since events happen in parallel in our universe, and a mobile automaton updates cells sequentially, it is unlikely that a mobile automaton can be used to model the universe.

 

But Wolfram wanted to continue with this train of thought, so here’s his theory.  It all depends on our perception of the universe.  Since we are observing from within the universe, our perception of events which are changing may be different than if we were outside the universe.  Wolfram believes that if we were outside the universe then we would see events happening sequentially rather than in parallel.

 

So the next step is to trace the causal events which occur using a mobile automaton.  These events are identified on page 489 of Wolfram’s book.  Once the events are identified, create an ordered network in which the events are nodes in our new network.  This network has connections which only go one direction because one event leads to another event.  On pages 492 and 493 there are several networks drawn based on different mobile automatons.

8.   Random Networks vs Scale-Free Networks

Random networks have nodes which are connected at  random.  These random networks usually have a bell shaped distribution.  In random networks, most nodes have the same number of connections.  An example of a random network is the U.S. Highway System.

 

Scale-free networks have nodes which may have many connections.  Also there may be nodes which have few connections.  Therefore, it is not scaled as in random networks.  An example of scale-free networks is the internet.  There are some sites which are hit constantly while other sites are hit very infrequently.  This type of distribution is called power law distribution. 

 

Random networks are susceptable to accidental failure.  This failure can cause disconnected nodes which fracture the network system.  On the other hand, scale-free networks have multiple connections and therefore ignore the failure and take another path.  The disadvantage with scale-free networks is that scale-free networks have hubs which are susceptable to attack.

9.   Conclusion

At first we looked at some networks with 2 outgoing connections.  These networks were one dimensional, two dimensional, and three dimensional.  The one dimensional network has nodes laid out in a single line.  This concept was expanded to a two dimensional array network.  Also tree networks are possible in two and three dimensions.

 

Then we discussed how to route connections in our network in order to add new nodes and remove nodes from our network.  By adding more complexity to the rules, we were able to create more random behavior.

 

Then the number of nodes was increased to three to discuss similarities between networks and space.  Since only a few networks have the same characteristics as space, the network that is chosen must also have these characteristics and the rules that are chosen must preserve these characteristics.

 

A correlation was made between space and time.  Can time be expressed similarly as space?  This was a difficult task and the possibilities looked slim.

 

Causal Networks were discussed as a method for expressing time in our networks.  By capturing the events which occurred in the mobile automaton, a new network can be drawn where events appear as nodes.  This new network expresses time by drawing connections between events.

 

Also, the difference between random networks and scale-free networks are discussed.  Random networks have a bell shaped distribution whereas scale-free networks have a power law distribution.

 

10.         References

[1] Steven Wolfram, “A New Kind of Science”, 2002

 

[2] Albert-Laszlo Barabasi and Eric Bonabeau, “Scale-Free Networks”, Scientific American pages 60-69, May 2003

 

 

 

 

 

 

All NKS-SJSU Applets are Open Source Shareware, Papers are Copyrighted to their Authors.

 



d

r

d