Properties of an Erdos Renyi Network

The Erdos Renyi (ER) Network is a random graph model. In this type of network, the nodes are connected based on a random probability, $p$, of an edge existing. ER graphs are characterized by a binomial degree distribution which at very large $N$ approaches the Poisson distribution. ER Network is useful when one has an absolute lack of knowledge in the principles governing edge creation. 

An ER Network has the following properties at large N:

1. As $N \rightarrow \infty,  <K> = Np$

2. As $N \rightarrow \infty,  <C> = p$

3. As $N \rightarrow \infty$, the degree distribution approaches a Poisson distribution

For this post, we'll be showing these notable properties of of an ER network. We construct an ER network with varying lattice sizes and determine whether we get the above quantities for very large $N$. 

The outline for the network construction is as follows:

1. We initialize a random $N \times N $ lattice A with values ranging from. We set a threshold  $th  \epsilon [0,1]$ which determines whether two nodes will be connected. When $A_{ij} \ge th$ then we change its value to 1 otherwise we change it to 0. Hence the probability of an edge existing is given by $p = 1 - th$.

2.  We construct the adjacency matrix and use it to solve for the mean degree, $<K>$, mean clustering coefficient, $<C>$, and the degree distribution for several degree sizes.

Shown below are the plots of the degree distribution for increasing values of $N$. The mean degree, $<K>$ and the %error from the mean of a Poisson distribution $\lambda = Np$. As shown by the decreasing %error, $<K>$ approaches $\lambda = Np$ as the number of nodes become large.

Figure 1. Degree distribution for different number of nodes N in the ER network

The summary of the network metrics are shown in Table 1. It can be observed that as N increases the errors in the quantities also decrease, suggesting that the values for <K> and <C> reduce to $Np$ and $p$ for large $N$, respectively. 

Table 1. Summary of network metrics ($<K> $- average degree,$ <C> $average clustering coefficient, $M $ number of edges) for different number of nodes $N$ in an Erdos-Renyi network