Probability of an edge in directed random configuration graph
I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm:
Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ independently from the degree distribution $P$.
Accept the draw only if it is feasible, i.e. only if $sum_{n in [N]}(j_n-k_n)=0$.For every node $n$, create $j_n$ in-stubs and $k_n$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.
- For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.
Each such resulting pair of stubs forms a directed edge of the graph.
I am interested in the probabilities of an edge. My suggestion is:
Under this random matching approach, the probability that there is an edge from a node $i$ to a node $l$ is, with $m$ being the number of all edges:
$$p_{il}=frac{k_i cdot j_l}{(2m-1)},$$
as node $i$ has $k_i$ out-stubs and $j_l$ in-stubs out of $2m-1$ (excluding of node $i$) attached to $l$ to which it could connect.
And similarly the probability that there is an edge from a node $l$ to $i$ is:$$p_{il}=frac{j_i cdot k_l}{(2m-1)}$$
Is this correct, or am I missing something?
probability probability-theory graph-theory random-graphs
asked Nov 9 '18 at 15:09
AlisatAlisat
448
add a comment |
I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm:
Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ independently from the degree distribution $P$.
Accept the draw only if it is feasible, i.e. only if $sum_{n in [N]}(j_n-k_n)=0$.For every node $n$, create $j_n$ in-stubs and $k_n$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.
- For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.
Each such resulting pair of stubs forms a directed edge of the graph.
I am interested in the probabilities of an edge. My suggestion is:
Under this random matching approach, the probability that there is an edge from a node $i$ to a node $l$ is, with $m$ being the number of all edges:
$$p_{il}=frac{k_i cdot j_l}{(2m-1)},$$
as node $i$ has $k_i$ out-stubs and $j_l$ in-stubs out of $2m-1$ (excluding of node $i$) attached to $l$ to which it could connect.
And similarly the probability that there is an edge from a node $l$ to $i$ is:$$p_{il}=frac{j_i cdot k_l}{(2m-1)}$$
Is this correct, or am I missing something?
probability probability-theory graph-theory random-graphs
asked Nov 9 '18 at 15:09
AlisatAlisat
448
add a comment |
I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm:
Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ independently from the degree distribution $P$.
Accept the draw only if it is feasible, i.e. only if $sum_{n in [N]}(j_n-k_n)=0$.For every node $n$, create $j_n$ in-stubs and $k_n$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.
- For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.
Each such resulting pair of stubs forms a directed edge of the graph.
I am interested in the probabilities of an edge. My suggestion is:
Under this random matching approach, the probability that there is an edge from a node $i$ to a node $l$ is, with $m$ being the number of all edges:
$$p_{il}=frac{k_i cdot j_l}{(2m-1)},$$
as node $i$ has $k_i$ out-stubs and $j_l$ in-stubs out of $2m-1$ (excluding of node $i$) attached to $l$ to which it could connect.
And similarly the probability that there is an edge from a node $l$ to $i$ is:$$p_{il}=frac{j_i cdot k_l}{(2m-1)}$$
Is this correct, or am I missing something?
probability probability-theory graph-theory random-graphs
asked Nov 9 '18 at 15:09
AlisatAlisat
448
I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm:
Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ independently from the degree distribution $P$.
Accept the draw only if it is feasible, i.e. only if $sum_{n in [N]}(j_n-k_n)=0$.For every node $n$, create $j_n$ in-stubs and $k_n$ out-stubs, where in-/out-stubs are open ended half-edges with an in-/out-arrow.
- For any unpaired out-stub, select iteratively uniformly at random an unpaired in-stub and connect them.
Each such resulting pair of stubs forms a directed edge of the graph.
I am interested in the probabilities of an edge. My suggestion is:
Under this random matching approach, the probability that there is an edge from a node $i$ to a node $l$ is, with $m$ being the number of all edges:
$$p_{il}=frac{k_i cdot j_l}{(2m-1)},$$
as node $i$ has $k_i$ out-stubs and $j_l$ in-stubs out of $2m-1$ (excluding of node $i$) attached to $l$ to which it could connect.
And similarly the probability that there is an edge from a node $l$ to $i$ is:$$p_{il}=frac{j_i cdot k_l}{(2m-1)}$$
Is this correct, or am I missing something?
probability probability-theory graph-theory random-graphs
probability probability-theory graph-theory random-graphs
asked Nov 9 '18 at 15:09
AlisatAlisat
448
asked Nov 9 '18 at 15:09
AlisatAlisat
448
edited Jan 6 at 19:23
Alisat
asked Nov 9 '18 at 15:09
AlisatAlisat
448
asked Nov 9 '18 at 15:09
AlisatAlisat
448
asked Nov 9 '18 at 15:09
AlisatAlisat
448
448
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.
The first edge we choose has probability $frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is
$$
1-p_{il} = left(1 - frac{j_l}{m}right)left(1 - frac{j_l}{m-1}right) dotsb left(1 - frac{j_l}{m-k_i+1}right)
$$
and the probability you want is the complement of this one.
Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $frac{k_i cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)
Additionally, because there are $k_i$ edges with probability $frac{j_l}{m}$ of going to $l$, then $frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
|
show 1 more 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%2f2991478%2fprobability-of-an-edge-in-directed-random-configuration-graph%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
We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.
The first edge we choose has probability $frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is
$$
1-p_{il} = left(1 - frac{j_l}{m}right)left(1 - frac{j_l}{m-1}right) dotsb left(1 - frac{j_l}{m-k_i+1}right)
$$
and the probability you want is the complement of this one.
Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $frac{k_i cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)
Additionally, because there are $k_i$ edges with probability $frac{j_l}{m}$ of going to $l$, then $frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
|
show 1 more comment
We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.
The first edge we choose has probability $frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is
$$
1-p_{il} = left(1 - frac{j_l}{m}right)left(1 - frac{j_l}{m-1}right) dotsb left(1 - frac{j_l}{m-k_i+1}right)
$$
and the probability you want is the complement of this one.
Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $frac{k_i cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)
Additionally, because there are $k_i$ edges with probability $frac{j_l}{m}$ of going to $l$, then $frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
|
show 1 more comment
We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.
The first edge we choose has probability $frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is
$$
1-p_{il} = left(1 - frac{j_l}{m}right)left(1 - frac{j_l}{m-1}right) dotsb left(1 - frac{j_l}{m-k_i+1}right)
$$
and the probability you want is the complement of this one.
Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $frac{k_i cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)
Additionally, because there are $k_i$ edges with probability $frac{j_l}{m}$ of going to $l$, then $frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
We can choose a uniformly random matching in any order. So let's choose the $k_i$ edges out of node $i$ one at a time and see the probability none of them go to node $l$.
The first edge we choose has probability $frac{j_l}{m}$ of going to $l$. If it doesn't, then the second edge has probability $frac{j_l}{m-1}$. If that also doesn't happen, then the third edge has probability $frac{j_l}{m-2}$, and so on. So the overall probability that none of the edges go to node $l$ is
$$
1-p_{il} = left(1 - frac{j_l}{m}right)left(1 - frac{j_l}{m-1}right) dotsb left(1 - frac{j_l}{m-k_i+1}right)
$$
and the probability you want is the complement of this one.
Asymptotically, however, assuming $k_i$ and $j_l$ are small relative to $m$, the answer is in fact close to $frac{k_i cdot j_l}{m}$ which is what you have, except that $m$ and not $2m-1$ is the number of options for the first edge. (Unlike the undirected configuration model, here there are $m$ out-stubs and $m$ in-stubs, which we distinguish.)
Additionally, because there are $k_i$ edges with probability $frac{j_l}{m}$ of going to $l$, then $frac{k_i j_l}{m}$ edges is the expected number of edges from $i$ to $l$.
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
edited Jan 6 at 20:09
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
answered Jan 6 at 17:16
Misha LavrovMisha Lavrov
44.3k555106
44.3k555106
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
|
show 1 more comment
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
So I guess there is no "neat" form for the probability as in the undirected one, where it is of the form $p_{ij} =frac{ k_i k_j} {2m−1}$. ? (Only for the large limits as you stated $p_{il} =frac{ k_i j_l} {m}$)
– Alisat
Jan 6 at 18:35
1
1
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
The "neat" form is not the probability but the expected number of edges from $i$ to $l$.
– Misha Lavrov
Jan 6 at 20:10
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
And for the undirected case, the formula you give is also the expectation, not the probability.
– Misha Lavrov
Jan 6 at 20:15
1
1
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
The paper does not use the configuration mode. Instead, they define $p_{ij} = frac{k_i k_j}{2m}$ then add an edge $ij$ with that probability. As they mention on p. 3 (second paragraph) the actual degree of vertex $i$ is not guaranteed to be $k_i$ in this model.
– Misha Lavrov
Jan 6 at 21:19
1
1
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
Upon further reading, the paper does seem to claim that $frac{k_i k_j}{2m-1}$ is the exact edge probability in the random matching model, which is incorrect.
– Misha Lavrov
Jan 6 at 21:48
|
show 1 more 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%2f2991478%2fprobability-of-an-edge-in-directed-random-configuration-graph%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
