expected number of in- and out-going links in random PA graph
I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is:
$t=1,$ one node $v_1$.
At each time step $(t+1)$ either we create a new node with probability $p$ which attaches immediately to an already existing node with probability $frac{(j_i(t)+1)}{N(t)+t}$, where $j_i(t)$ stands for the in-degree of a node $i$ at time $t$ and $N(t)$ stands for the number of nodes at time $t$ which is in expectation equal to $pt$. Or with probability $1-p$ we create a new link between two already existing nodes. The probability of having a link going from $i$ to a node $l$ will be $frac{(k_i(t)+1)(j_l(t)+1)}{(N(t)+t)^2}$, where $k_i(t)$ stands for the out-degree of a node $i$ at time $t$.
I am interested in calculating the expected number of in- and out-going edges for a node $i$ at time $t+1$.
My idea is that for $tgeq 2$,
$$mathbb{E}(text{in-going links to i})= (N(t)-i)frac{(j_i(t)+1)}{t(p+1)} + (t-N(t))frac{(j_i(t)+1)}{t(p+1)}=(t-i)frac{(j_i(t)+1)}{t(p+1)}$$
The first term comes from all newly created nodes and the second one from newly created links
and
$$mathbb{E}(text{out-going links from i})= 1 + (t-N(t))frac{(k_i(t)+1)}{t(p+1)}$$ where again the second one from newly created links and the $1$ comes from the very first link when $i$ got created.
Is this correct or am I missing something?
probability graph-theory random-graphs
asked Jan 4 at 9:41
AlisatAlisat
448
|
show 2 more comments
I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is:
$t=1,$ one node $v_1$.
At each time step $(t+1)$ either we create a new node with probability $p$ which attaches immediately to an already existing node with probability $frac{(j_i(t)+1)}{N(t)+t}$, where $j_i(t)$ stands for the in-degree of a node $i$ at time $t$ and $N(t)$ stands for the number of nodes at time $t$ which is in expectation equal to $pt$. Or with probability $1-p$ we create a new link between two already existing nodes. The probability of having a link going from $i$ to a node $l$ will be $frac{(k_i(t)+1)(j_l(t)+1)}{(N(t)+t)^2}$, where $k_i(t)$ stands for the out-degree of a node $i$ at time $t$.
I am interested in calculating the expected number of in- and out-going edges for a node $i$ at time $t+1$.
My idea is that for $tgeq 2$,
$$mathbb{E}(text{in-going links to i})= (N(t)-i)frac{(j_i(t)+1)}{t(p+1)} + (t-N(t))frac{(j_i(t)+1)}{t(p+1)}=(t-i)frac{(j_i(t)+1)}{t(p+1)}$$
The first term comes from all newly created nodes and the second one from newly created links
and
$$mathbb{E}(text{out-going links from i})= 1 + (t-N(t))frac{(k_i(t)+1)}{t(p+1)}$$ where again the second one from newly created links and the $1$ comes from the very first link when $i$ got created.
Is this correct or am I missing something?
probability graph-theory random-graphs
asked Jan 4 at 9:41
AlisatAlisat
448
1
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
1
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
1
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago
|
show 2 more comments
I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is:
$t=1,$ one node $v_1$.
At each time step $(t+1)$ either we create a new node with probability $p$ which attaches immediately to an already existing node with probability $frac{(j_i(t)+1)}{N(t)+t}$, where $j_i(t)$ stands for the in-degree of a node $i$ at time $t$ and $N(t)$ stands for the number of nodes at time $t$ which is in expectation equal to $pt$. Or with probability $1-p$ we create a new link between two already existing nodes. The probability of having a link going from $i$ to a node $l$ will be $frac{(k_i(t)+1)(j_l(t)+1)}{(N(t)+t)^2}$, where $k_i(t)$ stands for the out-degree of a node $i$ at time $t$.
I am interested in calculating the expected number of in- and out-going edges for a node $i$ at time $t+1$.
My idea is that for $tgeq 2$,
$$mathbb{E}(text{in-going links to i})= (N(t)-i)frac{(j_i(t)+1)}{t(p+1)} + (t-N(t))frac{(j_i(t)+1)}{t(p+1)}=(t-i)frac{(j_i(t)+1)}{t(p+1)}$$
The first term comes from all newly created nodes and the second one from newly created links
and
$$mathbb{E}(text{out-going links from i})= 1 + (t-N(t))frac{(k_i(t)+1)}{t(p+1)}$$ where again the second one from newly created links and the $1$ comes from the very first link when $i$ got created.
Is this correct or am I missing something?
probability graph-theory random-graphs
asked Jan 4 at 9:41
AlisatAlisat
448
I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is:
$t=1,$ one node $v_1$.
At each time step $(t+1)$ either we create a new node with probability $p$ which attaches immediately to an already existing node with probability $frac{(j_i(t)+1)}{N(t)+t}$, where $j_i(t)$ stands for the in-degree of a node $i$ at time $t$ and $N(t)$ stands for the number of nodes at time $t$ which is in expectation equal to $pt$. Or with probability $1-p$ we create a new link between two already existing nodes. The probability of having a link going from $i$ to a node $l$ will be $frac{(k_i(t)+1)(j_l(t)+1)}{(N(t)+t)^2}$, where $k_i(t)$ stands for the out-degree of a node $i$ at time $t$.
I am interested in calculating the expected number of in- and out-going edges for a node $i$ at time $t+1$.
My idea is that for $tgeq 2$,
$$mathbb{E}(text{in-going links to i})= (N(t)-i)frac{(j_i(t)+1)}{t(p+1)} + (t-N(t))frac{(j_i(t)+1)}{t(p+1)}=(t-i)frac{(j_i(t)+1)}{t(p+1)}$$
The first term comes from all newly created nodes and the second one from newly created links
and
$$mathbb{E}(text{out-going links from i})= 1 + (t-N(t))frac{(k_i(t)+1)}{t(p+1)}$$ where again the second one from newly created links and the $1$ comes from the very first link when $i$ got created.
Is this correct or am I missing something?
probability graph-theory random-graphs
probability graph-theory random-graphs
asked Jan 4 at 9:41
AlisatAlisat
448
asked Jan 4 at 9:41
AlisatAlisat
448
edited 2 days ago
Alisat
asked Jan 4 at 9:41
AlisatAlisat
448
asked Jan 4 at 9:41
AlisatAlisat
448
asked Jan 4 at 9:41
AlisatAlisat
448
448
1
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
1
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
1
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago
|
show 2 more comments
1
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
1
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
1
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago
1
1
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
1
1
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
1
1
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago
|
show 2 more comments
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%2f3061463%2fexpected-number-of-in-and-out-going-links-in-random-pa-graph%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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3061463%2fexpected-number-of-in-and-out-going-links-in-random-pa-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
1
I don't think your probabilities add up to $1$ as written. $frac{j_i(t)+1}{t}$ should be $frac{j_i(t)+1}{2t}$, and $frac{(k_i(t)+1)(j_l(t)+1)}{2t}$ should be $frac{(k_i(t)+1)(j_l(t)+1)}{4t^2}$ (assuming you allow $i=l$; if that is not allowed then the denominator is more complicated).
– Misha Lavrov
Jan 4 at 20:58
@MishaLavrov Oh thank you so much! If I leave it unchanged I get that the probabilities add up to $1+p$ so you are for sure correct- I was not aware of this ... I will soon edit my post accordingly. But if I change it as you suggested I still don't get that the probabilities add up to 1? ( I also realized that I can simplify my starting position s.t. we have $N(t)=pt$.)
– Alisat
Jan 5 at 7:23
@MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$)
– Alisat
Jan 5 at 7:50
1
Right, sorry - the sum of $j_i(t)$ over all $i$ is $t$, and the sum of $1$ over all $$ is $N(t)$, so the denominators should be $N(t)+t$ and $(N(t)+t)^2$.'
– Misha Lavrov
2 days ago
1
I will have to think about it longer but there must be some other flaw: if $p=1$, then your expected in-degree at time $t+1$ is less than the in-degree at time $t$.
– Misha Lavrov
2 days ago