4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure these papers use the ER model? $\endgroup$ – Raphael Feb 24 '15 at 22:52
  • 1
    $\begingroup$ Yes, in the first one it's always explicitly stated, and they are distinguished from the "random regular" graphs. In the second one, they are mentioned a couple of times and then referred as "random networks", but "random regular" graphs are not to used, so it's clear. $\endgroup$ – Agostino Feb 24 '15 at 23:02
  • $\begingroup$ Presumably $p$ is not confined to integers. $\endgroup$ – Yuval Filmus Feb 25 '15 at 4:21
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the supplementary information of the first paper, I read "In the case of ER networks, whose degrees are Poisson-distributed". How can I find a proper p? $\endgroup$ – Agostino Feb 24 '15 at 20:48
  • $\begingroup$ If $p = c/n$ for constant $c$ then the degrees will have roughly Poisson distribution with expectation $c$. $\endgroup$ – Yuval Filmus Feb 24 '15 at 21:54
  • $\begingroup$ So, is there a way to find a reasonably precise value for $p$, knowing just the final average degree? Would it be correct to simply put $m=avg.deg.*n/2$. Thanks. $\endgroup$ – Agostino Feb 24 '15 at 22:25
  • $\begingroup$ Yes, if a graph has average degree $d$, then it has $dn/2$ edges. $\endgroup$ – Yuval Filmus Feb 24 '15 at 22:27
  • $\begingroup$ You can solve for $p$ using the formula $p = d/n$. If the average degree is "constant" (say, 2), then the resulting degree distribution will be roughly Poisson. $\endgroup$ – Yuval Filmus Feb 24 '15 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.