|
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
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.
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.
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:
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.
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 r-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 3
nodes at distance r. This example
grows faster than to r. 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.
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.
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.
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.
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.
[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
|
![[ Welcome to NKS - SJSU ]](http://sjsu.rudyrucker.com/images/nkslogo1.gif)
