[Solved]: Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

Problem Detail: 

I'm trying to reproduce the synthetic networks (graphs) described in some papers.

The topic is the same as a previous question of mine, but with a different focus.

It is stated that the Erdos-Renyi model was used to create $2$ networks with average degrees $\langle k_a \rangle$ and $\langle k_b \rangle$.

In the first paper, the average degree is $k = 4$ , while the number of nodes $n$ is 50000.

In the second paper the average degree is not called $k$, but it's stated that the mean degree is $1.999$ for $n = 200$ (in Fig. 2), while it is $2.45$ for $n = 4000 $ and $ n = 6000$ (in Fig. 7).

I looked for libraries implementing the Erdos-Renyi algorithm and they seem to require different parameters than average degree. One is NetworkX, another is igraph. They work in similar ways and ask for:

• $n$ - number of nodes
• $0 \leq p \leq 1$ - the probability for drawing an edge between two arbitrary vertices
• $m$ - the number of edges in the graph (in alternative to $p$, only in igraph)

How can I calculate the settings to generate a graph with the same average degree as the ones described in the papers?

Here are the references:

• Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
• Small Cluster in Cyber Physical Systems, Huang et al. 2014
• Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used generating functions to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Asked By : Agostino

Answered By : Yuval Filmus

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability.

When $p=c/n$ for fixed $c$, the degree of a single vertex has roughly Poisson distribution (with mean $c$); formally, as $n\to\infty$ the distribution tends to Poisson. In practice, this means that for "small" $c$ and "large" $n$, the degree will be Poisson. Furthermore, while there is some dependency between vertices, we still expect the entire empirical degree distribution to be close to the same Poisson distribution (i.e., we expect the fraction of coordinates having degree $d$ to be roughly $e^{-c} c^d/d!$); this is probably proved formally in the literature.

When $p$ is constant, the degree of a single vertex has roughly Gaussian distribution, and it is probably the case that the joint distribution is also close to the appropriate multivariate Gaussian.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39774