# 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 $$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?

• 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
• 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 Jan 5 at 15:18
• 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 Jan 5 at 16:58