0
$\begingroup$

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 $t\geq 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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Misha Lavrov Jan 4 at 20:58
  • $\begingroup$ @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$.) $\endgroup$ – Alisat Jan 5 at 7:23
  • $\begingroup$ @MishaLavrov Shouldn't the denominators be $(1+p)t$ and $(p+1)^2t^2$ respectively? (Provided $N(t)=tp$) $\endgroup$ – Alisat Jan 5 at 7:50
  • 1
    $\begingroup$ 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$.' $\endgroup$ – Misha Lavrov Jan 5 at 15:18
  • 1
    $\begingroup$ 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$. $\endgroup$ – Misha Lavrov Jan 5 at 16:58

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.