Erdos-Renyi model
Recently I have discovered an online education system Coursera. While browsing through the available courses I noticed one named "Social and Economic Networks: Models and Analysis". Sadly it was already six weeks into the eight week program, so I was not able to formally complete it. Yet the knowledge I have obtained by viewing videos of this course enabled me to prepare couple of posts for this website.
During the next couple of posts I will consider some of the well-known network models. I'll start in this text from the Erdos-Renyi network formation model, and later will continue with the Watts-Strogatz model ("small world" networks) and the Barabasi-Albert model ("scale-free" networks).
Erdos-Renyi model and network properties
Erdos-Renyi model is one of the earliest network formation models. Thus it is relatively simple - the edges are put completely at random. Namely, we first have to generate \( N \) isolated nodes. And afterwards, while iterating through all possible pairs of nodes, we have to put random edges between the pairs (i.e., make random connections) with a certain probability \( p \).
Being that simple Erdos-Renyi network does not posses interesting features, such as power law degree distribution, high levels of clusterization and other observed in the real networks (and other network formation models). The degree distribution of Erdos-Renyi network is binomial, which is approximately Gaussian in the limit of large \( N \), while Poisson distribution (with \( \lambda = Np \)) is also a great approximation of Erdos-Renyi network degree distribution. The clusterization is low, there are no central hubs and etc.
Yet the Erdos-Renyi networks are still important in the network theory as they serve well as a benchmark tools. Namely, if certain property can exist on this network, then it might be so that the property arises purely at random and is not observed due to a more sophisticated reasons.
It is also worthwhile to note that this network formation model is somewhat related to the percolation theory. Imagine that a fully connected graph. Now let us remove a certain number of edges from it. How many edges could we randomly remove from a graph (network), for it to be still connected (i.e., with no isolated nodes)? The answer is pretty simple. We could remove edges with probability \( 1-p \), where \( p = \ln(N)/N \). Note that here \( p \) stands for a probability to create an edge in the Erdos-Renyi network! Try different \( p \) values, around the given, and see what happens with the network.
Interactive applet
We provide an interactive HTML5 applet for the Erdos-Renyi network formation model below. In this applet you can control both the numbers of nodes, \( N \), and the probability of putting and edge, \( p \), between each possible pair of nodes. Using the mouse wheel you can zoom in and out of the picture. The new graph (network) is generated by pressing ">" button.
On the left panel you should see the Erdos-Renyi network, while on the right panel we show the probability density of its nodes' degrees (blue circles) approximated by the Poissonian distribution (red curve). The obtained degree distribution should converge towards Poissonian in the large number of nodes, \( N \), limit (\( p \) should also be not too small).
