Mixing
Is it true that a random graph's degree gives Poission distribution?
$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
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$.)
graph-theory random-graphs
asked Jan 13 at 9:08
ynnynn
616
$endgroup$
add a comment |
$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
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$.)
graph-theory random-graphs
asked Jan 13 at 9:08
ynnynn
616
$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
add a comment |
$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
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$.)
graph-theory random-graphs
asked Jan 13 at 9:08
ynnynn
616
$endgroup$
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
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$.)
graph-theory random-graphs
graph-theory random-graphs
asked Jan 13 at 9:08
ynnynn
616
asked Jan 13 at 9:08
ynnynn
616
edited Jan 13 at 9:45
ynn
asked Jan 13 at 9:08
ynnynn
616
asked Jan 13 at 9:08
ynnynn
616
asked Jan 13 at 9:08
ynnynn
616
616
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
add a comment |
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
2
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$
"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
$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
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071827%2fis-it-true-that-a-random-graphs-degree-gives-poission-distribution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071827%2fis-it-true-that-a-random-graphs-degree-gives-poission-distribution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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