Random Networks
"The advantage of a random network over a normal network is that, as long as there are at least a few common links, the number of links between nodes is very small. This is true however many nodes there are in the network."
-- Stigmergic Systems

Good News !!

You are viewing a draft of the book entitled "Patterns – The Art, Soul, and Science of Beholding Nature". The final version of this book has now being published as an Amazon Kindle eBook.

There are some significant changes in the eBook that are not in this draft. You may purchase the eBook here

Some of the ideas in the eBook are contained in posts at my Patterns In Nature Blog. You are encouraged to visit this blog site. If you press the "Like" button shown below, your Facebook page will provide you with short notifications and summaries of new blog posts as they become available.



The network architecture that is opposite to the "regular" architecture is the homogeneous random network that was analyzed by Paul Erdös and Alfred Rényi in the mid twentieth century.  A random network, is a theoretical construct which contains links that are chosen completely at random with equal probability. A randoim network is considered to be highly disordered. Using a random number generator, one assigns links from one node to a second node.

Random links typically result in shortcuts to remote nodes, thus shortening the path length to otherwise distant nodes. For example, random links between nodes #6 and #10 or nodes #4 and #1 serve to reach to clusters on the opposite side of the network. This shortening of path length tends to increase connectivity.

Unlike real world networks, there is low clustering in random networks. Therefore, the resulting network very rarely contains highly connected nodes. Consequently, a random network is not a good candidate model for the highly connected architecture that characterize emergent patterns in nature. The random network shown to the right portrays a circular random network with a probability of 30% that a node will have a link.


The clique, shown to the left, is a highly connected random network where each node has a 100% probability of being connected to every other node. This means that you can get from any node to any other node in a single step. Each node is connected to every other node. The model is equivalent to a group of people who all know each other. The clique diagram is useful for portraying clusters but rarely exists by itself in nature. Real world networks in nature are "sparse", meaning that they have far fewer links than what exists in a clique.



In a random graph, unlike the "regular" architecture, the topological rule is that the node degrees may not all be equal. Instead, the degrees are distributed according to a Poisson distribution because it is assumed that any linking between nodes can happen with equal probability. In the random graph degree distribution shown below, most nodes have 10 degrees. Random graphs that follow this topological rule are useful theoretical exercises, but do not generally represent networks in the real world.

Poisson


You are invited to explore more detail by looking at random networks, small world networks, and scale-free networks.


Useful References



Navigation

Table Of Contents