Random & Distributed Networks

Updated: Sep 4

A random network is more formally termed the Erdős–Rényi random graph model, so named after two mathematicians who first introduced a set of models for random graphs in the mid 20th century.[1] As the name implies, this type of network is generated by simply taking a set of nodes and randomly placing links between them with some given probability. So we just take two nodes in the network and we roll a dice to see if there will be a connection between them or not. The higher we set our probability the more likely there will be a connection, and thus the more connected the overall graph will become. This may be defined as a simple system in that once one has decided how many nodes there will be, it is then really just defined by a single parameter, that is the probability parameter for the likelihood that any two nodes will form a connection.


Normal Distribution

Looking at the degree distribution of this network would reveal that it follows a normal distribution. Because it was randomly generated, there will be some difference in the distribution of degrees of connectivity among the nodes. Some will have one degree, some five, but there will be a well-defined normal or average degree. In this distribution, there will be very few nodes with a very large degree, and very few with a very low degree. Most will tend towards the normal amount of connections.[2] 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 characterizes many of the networks we see around us. Although a useful theoretical exercise, random networks, in general, do not represent networks in the real-world. They are considered far more random because real-world networks are typically created to serve some function and are constrained by some limiting resource that gives them a more distinct pattern. If we look at some network like the traditional trade routes across the Sahara desert in Africa, it may look somewhat random at first glance, but we know that it is not because of the caravans of camels and traders who created these networks. Setting out to cross the Sahara in any random direction would have of course been fatal to them.


Factors in Network Structure

This helps illustrate the two key factors to generating any given structure to a network. Firstly, the context or environmental constraints the network is under. Different types of networks are all under different types of environmental constraints. For example, this may be the geological constraints placed upon the travelers in our example above. It may be the physiological constraints placed upon the metabolic network with the human body, or it may be the financial constraints placed upon a logistic network. All of these represent resistance to network formation that the environment places on the network, but inversely we can look at this the other way around, asking what methods the nodes in the network use to overcome these constraints. Travelers in the Sahara would use prior knowledge encoded in maps as to where the water wells were in order to overcome the arid environmental constraint placed upon them. A national airline because of the limitations on finance may not be able to run a direct route between every city within the country, but will get around this by creating a hub and spoke network so as to reach all locations. Again, this is a method or strategy for overcoming resource constraints. And out of the interaction between these environmental constraints and the methods used by the nodes to overcome them, we will get a particular overall structure to the network that makes them distinctly different from our random network.


Distributed Networks

A distributed network is in many ways quite similar to a random model. It is defined by a low degree distribution level, meaning all or most of the nodes have the same degree of connectivity. And as there are no dominant nodes to provide global functions for the entire network, each node must contribute equally to the network’s maintenance.[3] And as there is no real global coordination in a distributed network,  nodes can have a very high degree of autonomy, as they are largely self-sufficient and independent from nodes outside of their neighborhood. An example of a distributed network might be a community alert group, where each member of the community has equal responsibility and authority to act when there is an event that others should know about. There is no hierarchy, and in this example, the network is only actualized when needed, thus placing very limited constraints on its members. Within the world of computing distributed networks are also called mesh networks.


Advantages & Disadvantage

Distributed networks have a number of advantages and disadvantage. On the positive side, they may be very robust to failure. As there is no critical or strategic nodes in the network, any node can theoretically be replaced by any other, and as we have already noted elements may have a high degree of autonomy, with little network maintenance tax placed upon them. But also this type of network can be less efficient in many circumstances. Without centralized nodes, there cannot be any centralized batch processing that leverages economies of scale, and diffusion across the network can be slow as there are no central hubs with which to reach many nodes in a single hop. This can also create problems in terms of coordinating the network as a whole. In many ways, a distributed network represents a system in a fine balance and relatively stable state and this is often not what we see when we look at real-world networks.


1. Clauset, A. (2011). Inference, Models and Simulation for Complex Systems. [online] Available at: http://tuvalu.santafe.edu/~aaronc/courses/7000/csci7000-001_2011_L13.pdf [Accessed 4 Sep. 2020].


2. Clauset, A. (2011). Inference, Models and Simulation for Complex Systems. [online] Available at: http://tuvalu.santafe.edu/~aaronc/courses/7000/csci7000-001_2011_L13.pdf.

3.‌ Beraldi, R. and Baldoni, R. (n.d.). UNICAST ROUTING TECHNIQUES FOR MOBILE AD-HOC NETWORKS. [online] Available at: http://www.dis.uniroma1.it/~beraldi/pub/B1.pdf [Accessed 4 Sep. 2020].

Systems Innovation

  • LinkedIn
  • YouTube
  • Twitter
  • Facebook