1
$\begingroup$

In many documents, it is said that a random graph's degree follows Poisson distribution. However, my numerical calculation contradicts with the fact.

Assume a random graph whose number of nodes $N = 1000$ and the number of edges $E \simeq 200000$. The first picture is created with iGraph library's Graph.Erdos_Renyi() function. The second one is created with my implementation of Erdos Renyi model. The third one is created with my implementation of random walk method. All look the same. However, it seems the distributions are too sharp. In this case, you can approximate Poisson distribution as Gaussian distribution, then the peak's $y$ coordinate should be $y \simeq \frac{1}{\sigma \sqrt{2 \pi}} \simeq 0.02$ as is indicated here. (Please note Poisson distribution's mean and variance take the same value. So $\mu = 400 \Rightarrow \sigma = 20$.)

QUESTION: It is really true that a random graph's degree gives Poission distribution? If so, what point is wrong with my analysis?


The program code I used to create the first picture:

from igraph import *
g = Graph.Erdos_Renyi(n = 1000, m = 200000) #create graph
dist = g.degree_distribution() #calculate degree distribution
print(dist) #print histogram
#then normalize and plot with gnuplot

pic1 pic2 pic3


Supplement: I calculated the random walk method 200 times and plotted the histogram. The mean $\mu = 400$, the standard deviation $\sigma = 15.4651$, the largest $y = 0.02625$ and the Gaussian peak $y = \frac{1}{\sigma \sqrt{2 \pi}} \simeq 0.02580$. Shouldn't $\sigma$ be about $\sqrt{400} = 20$? (The blue line is Gaussian with $\mu = 400, \sigma = 15.4651$.) enter image description here

$\endgroup$
  • 2
    $\begingroup$ "However, my numerical calculation contradicts with the fact." Yes, because you are not in the regime where the Poisson approximation holds. With 1'000 vertices and 200'000 edges, each edge is present with probability 0.4. Poisson distributions appear in the limit when the number of vertices is large and the number of edges is of the same order (not of the order of its square, like here). $\endgroup$ – Did Jan 13 at 11:04
  • $\begingroup$ @Did Now I confirmed you are totally right. Thank you. I should have thought about the condition of approximation more carefully. Gaussian is indeed natural in my case as the limit of Binomial distribution. $\endgroup$ – ynn Jan 13 at 11:47

Your Answer

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

Browse other questions tagged or ask your own question.