6. ERDOS-RENYI random graphs

Having explained the concept of Heterogeneity, we will discuss a concept of ERRG briefly as it would be important for the upcoming section. This concept is explained in further detail later in the paper.

Random Degree Distributions

A network with little structure, one in which is highly entropic and nodes are connected seemingly at random is called the Erdos-Renyi Random Graph. Gilbert produced a similar network a year earlier, but Renyi revisitng a previous Erdos work produced this method of a network. While the original network was static, it was later adapted by network scientists in the form of a growing network.

Constructing ERRG Topology

Erdos-Renyi random graphs are constructed as follows: begin with a small network, for example a ring network of size N. At each time-step, add a link m to a node at random. This means that each node in the network is equally likely to receive the additional link. Over time this results in a network of high entropy, with little discernible structure. There are examples of ERRGs, for example the connectivity of roads and highways in the United States. This means that the overall connectivity follows normal distribution and relevant binomial statistics such as the average and median are valid. In contrast, a more complex network could be something simpler, and more efficient, such as teh connectivity of airlines and the distribution of their hubs. In this case such simple mathematics might not be as appropriate.

ERRG Algorithm

When we apply the ERRG algorithm, we are ignoring the degrees of the nodes and therefore selecting a node at random. This means that there is no internal learning in the network, no algorithm with nontrivial results. The network is not necessarily efficiently designed.

Normal Statistics averages, etc.

This also means that when we take the average of a node that it actually is the average of the network. This also means that if this was the type of network that existed in social engagement, then current measurements of the engagement rates would still be valid. It is in fact the reason that ERRGs don’t exist in the real world in the complex way, that allows heterogeneity to take place, and therefore nontrivial structural and robust topologies to exist in networks in the real-world.