How do you estimate the remaining degree distribution?
$begingroup$
Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(v_1,v_2,v_3,v_4)$, and edges $E=(e_1,e_2,e_3)$ where $e_1=(v_1,v_2)$,$e_2=(v_2,v_3)$ and $e_3=(v_3,v_4)$.
In other words a graph with the structure
o-o-o-o
Am I correct in assuming that $q_{j,k}$ can be calculated with the formula
$q_{j,k} = mu(j,k)frac{n(j,k)}{2|E|}$
where $n(j,k)$ is the number of edges connecting nodes with remaining degrees $j$ and $k$, and $mu(j,k) = begin{cases} 2 text{ if } j = k \ 1 text{ else} end{cases}$. In which case an estimation of $q_{j,k}$ based on graph $G$ would be the following:
$q_{0,1} = q_{1,0} = 1frac{2}{6} \ q_{1,1} = 2frac{1}{6}$
As you can see, all probabilities sum to 1. However online there is a slide show (page 9) that shows that the joint degree distribution, which is closely related to the remaining degree distribution, is apparently supposed to be calculated with a similar formula except $j$ and $k$ are now degrees rather than remaining degrees (subtract 1), and $mu(j,k) = begin{cases} 1 text{ if } j = k \ 2 text{ else} end{cases}$.
With the formula suggested in the slide show the calculation of $q_{j,k}$ wouldn't work even if $j$ and $k$ were degrees rather than remaining degrees because the probabilities wouldn't add up to 1. So am I missing something or has a mistake been made in those slides?
probability probability-distributions graph-theory estimation network
asked Jan 12 at 20:38
JonathanJonathan
1957
$endgroup$
add a comment |
$begingroup$
Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(v_1,v_2,v_3,v_4)$, and edges $E=(e_1,e_2,e_3)$ where $e_1=(v_1,v_2)$,$e_2=(v_2,v_3)$ and $e_3=(v_3,v_4)$.
In other words a graph with the structure
o-o-o-o
Am I correct in assuming that $q_{j,k}$ can be calculated with the formula
$q_{j,k} = mu(j,k)frac{n(j,k)}{2|E|}$
where $n(j,k)$ is the number of edges connecting nodes with remaining degrees $j$ and $k$, and $mu(j,k) = begin{cases} 2 text{ if } j = k \ 1 text{ else} end{cases}$. In which case an estimation of $q_{j,k}$ based on graph $G$ would be the following:
$q_{0,1} = q_{1,0} = 1frac{2}{6} \ q_{1,1} = 2frac{1}{6}$
As you can see, all probabilities sum to 1. However online there is a slide show (page 9) that shows that the joint degree distribution, which is closely related to the remaining degree distribution, is apparently supposed to be calculated with a similar formula except $j$ and $k$ are now degrees rather than remaining degrees (subtract 1), and $mu(j,k) = begin{cases} 1 text{ if } j = k \ 2 text{ else} end{cases}$.
With the formula suggested in the slide show the calculation of $q_{j,k}$ wouldn't work even if $j$ and $k$ were degrees rather than remaining degrees because the probabilities wouldn't add up to 1. So am I missing something or has a mistake been made in those slides?
probability probability-distributions graph-theory estimation network
asked Jan 12 at 20:38
JonathanJonathan
1957
$endgroup$
add a comment |
$begingroup$
Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(v_1,v_2,v_3,v_4)$, and edges $E=(e_1,e_2,e_3)$ where $e_1=(v_1,v_2)$,$e_2=(v_2,v_3)$ and $e_3=(v_3,v_4)$.
In other words a graph with the structure
o-o-o-o
Am I correct in assuming that $q_{j,k}$ can be calculated with the formula
$q_{j,k} = mu(j,k)frac{n(j,k)}{2|E|}$
where $n(j,k)$ is the number of edges connecting nodes with remaining degrees $j$ and $k$, and $mu(j,k) = begin{cases} 2 text{ if } j = k \ 1 text{ else} end{cases}$. In which case an estimation of $q_{j,k}$ based on graph $G$ would be the following:
$q_{0,1} = q_{1,0} = 1frac{2}{6} \ q_{1,1} = 2frac{1}{6}$
As you can see, all probabilities sum to 1. However online there is a slide show (page 9) that shows that the joint degree distribution, which is closely related to the remaining degree distribution, is apparently supposed to be calculated with a similar formula except $j$ and $k$ are now degrees rather than remaining degrees (subtract 1), and $mu(j,k) = begin{cases} 1 text{ if } j = k \ 2 text{ else} end{cases}$.
With the formula suggested in the slide show the calculation of $q_{j,k}$ wouldn't work even if $j$ and $k$ were degrees rather than remaining degrees because the probabilities wouldn't add up to 1. So am I missing something or has a mistake been made in those slides?
probability probability-distributions graph-theory estimation network
asked Jan 12 at 20:38
JonathanJonathan
1957
$endgroup$
Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be an undirected graph with nodes $V=(v_1,v_2,v_3,v_4)$, and edges $E=(e_1,e_2,e_3)$ where $e_1=(v_1,v_2)$,$e_2=(v_2,v_3)$ and $e_3=(v_3,v_4)$.
In other words a graph with the structure
o-o-o-o
Am I correct in assuming that $q_{j,k}$ can be calculated with the formula
$q_{j,k} = mu(j,k)frac{n(j,k)}{2|E|}$
where $n(j,k)$ is the number of edges connecting nodes with remaining degrees $j$ and $k$, and $mu(j,k) = begin{cases} 2 text{ if } j = k \ 1 text{ else} end{cases}$. In which case an estimation of $q_{j,k}$ based on graph $G$ would be the following:
$q_{0,1} = q_{1,0} = 1frac{2}{6} \ q_{1,1} = 2frac{1}{6}$
As you can see, all probabilities sum to 1. However online there is a slide show (page 9) that shows that the joint degree distribution, which is closely related to the remaining degree distribution, is apparently supposed to be calculated with a similar formula except $j$ and $k$ are now degrees rather than remaining degrees (subtract 1), and $mu(j,k) = begin{cases} 1 text{ if } j = k \ 2 text{ else} end{cases}$.
With the formula suggested in the slide show the calculation of $q_{j,k}$ wouldn't work even if $j$ and $k$ were degrees rather than remaining degrees because the probabilities wouldn't add up to 1. So am I missing something or has a mistake been made in those slides?
probability probability-distributions graph-theory estimation network
probability probability-distributions graph-theory estimation network
asked Jan 12 at 20:38
JonathanJonathan
1957
asked Jan 12 at 20:38
JonathanJonathan
1957
edited Jan 12 at 21:19
Jonathan
asked Jan 12 at 20:38
JonathanJonathan
1957
asked Jan 12 at 20:38
JonathanJonathan
1957
asked Jan 12 at 20:38
JonathanJonathan
1957
1957
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j ne k$, then the edge has a $frac12$ chance of contributing to $q_{j,k}$ and a $frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $frac{m(j,k)}{nu(j,k) cdot m}$ where $m$ is the number of edges and $nu(j,k) = begin{cases}1 & j=k \ 2 & text{else}end{cases}$, and it's possible that here is where the mistake comes from.
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
add a comment |
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%2f3071363%2fhow-do-you-estimate-the-remaining-degree-distribution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j ne k$, then the edge has a $frac12$ chance of contributing to $q_{j,k}$ and a $frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $frac{m(j,k)}{nu(j,k) cdot m}$ where $m$ is the number of edges and $nu(j,k) = begin{cases}1 & j=k \ 2 & text{else}end{cases}$, and it's possible that here is where the mistake comes from.
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
add a comment |
$begingroup$
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j ne k$, then the edge has a $frac12$ chance of contributing to $q_{j,k}$ and a $frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $frac{m(j,k)}{nu(j,k) cdot m}$ where $m$ is the number of edges and $nu(j,k) = begin{cases}1 & j=k \ 2 & text{else}end{cases}$, and it's possible that here is where the mistake comes from.
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
add a comment |
$begingroup$
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j ne k$, then the edge has a $frac12$ chance of contributing to $q_{j,k}$ and a $frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $frac{m(j,k)}{nu(j,k) cdot m}$ where $m$ is the number of edges and $nu(j,k) = begin{cases}1 & j=k \ 2 & text{else}end{cases}$, and it's possible that here is where the mistake comes from.
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
You are right - either way, no matter if you want the joint degree distribution or the remaining degree distribution, you want the diagonal terms $q_{j,j}$ to be the ones multiplied by $2$, not the other ones.
We sample from either distribution by picking an edge, then picking which endpoint is first and which is second. If the degrees of its endpoints are both $j$, then the edge contributes to $q_{j,j}$ no matter what. If the degrees of its endpoints are $j ne k$, then the edge has a $frac12$ chance of contributing to $q_{j,k}$ and a $frac12$ chance of contributing to $q_{k,j}$.
You might write down the same function as $frac{m(j,k)}{nu(j,k) cdot m}$ where $m$ is the number of edges and $nu(j,k) = begin{cases}1 & j=k \ 2 & text{else}end{cases}$, and it's possible that here is where the mistake comes from.
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
edited Jan 13 at 2:16
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 13 at 0:04
Misha LavrovMisha Lavrov
47.7k657107
47.7k657107
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
add a comment |
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
$begingroup$
Thanks very much for the answer but unfortunately this does not answer my question. I am already aware of how the two distributions are related. I wanted to make sure my formula for calculating the distribution was correct. The source of confusion was about function $mu(j,k)$. To reiterate, in the learning material I linked to, the $mu(j,k)$ function appears to be wrong precisely because using their version of the function causes the probabilities to not add up. But mine appears to be right. So I just wanted to clarify if I'm right or the learning material is right and I've missed something.
$endgroup$
– Jonathan
Jan 13 at 2:04
1
1
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
$begingroup$
Oh, I see - I missed completely the fact that in your second definition of $mu$, the $1$ and $2$ are switched.
$endgroup$
– Misha Lavrov
Jan 13 at 2:12
1
1
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Anyway, you're completely right that this has to be a mistake.
$endgroup$
– Misha Lavrov
Jan 13 at 2:16
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
$begingroup$
Thanks so much for the quick response, very helpful answer.
$endgroup$
– Jonathan
Jan 13 at 2:23
add a comment |
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%2f3071363%2fhow-do-you-estimate-the-remaining-degree-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
