Question about a preferential attachment model

Question

I am reading the book Complex Graphs and Networks by Fan Chung and Linyuan Lu, in chapter 3, they described a preferential attachment model:

Starting from a initial graph $G_0$ and at each time step,

with probability $p$, add a new vertex $v$ and an edge $\{u, v\}$ by randomly choosing $u$ in proportion to the degree of $u$ in the current graph, call this the vertex step,

with probability $1-p$, add a new edge $\{r, s\}$ by independently choosing vertices $r$ and $s$ with probability proportional to their degrees, call this the edge step.

$m_{k,\ t}$ denotes the number of vertices of degree $k$ at time $t$ and in the book, there is a recursive formula to calculate the expectation of $\mathbb{E}(m_{k,\ t})$ for $k>1$:

$$\mathbb{E}(m_{k,\ t})=\mathbb{E}(m_{k,\ t-1})(1-\frac{kp}{2t}-\frac{(1-p)2k}{2t})+\mathbb{E}(m_{k-1,\ t-1})(\frac{(k-1)p}{2t}+\frac{(1-p)2(k-1)}{2t})$$

I understand that $\frac{k}{2t}$ is the probability of choosing a specific vertex with degree $k$ in the vertex step, but shouldn't the probability of choosing this specific vertex in the edge step be $1-(1-\frac{k}{2t})^2=\frac{2k}{2t}-\frac{k^2}{4t^2}$ ? Did the authors omit the quadratic term or am I missing something?

---

I divide the vertices into 3 parts, those with degree $k$ (denoted by A), those with degree $k-1$ (denoted by B) and all the others (denoted by C). There are 6 cases that can influence $m_{k,\ t}$ in the edge step. In the following I abuse the notation to use $A$ and $B$ to denote the number of vertices in the corresponding group (instead of $m_{k,\ t-1}$ and $m_{k-1,\ t-1}$) and I calculate the contribution to the expectation for each case.

1. vertex in A connect to a different vertex in A ($m_{k,\ t}=m_{k, \ t-1}-2$),

$$-2\times A(A-1)(\frac{k}{2t})^2$$

2. vertex in A connect to itself ($m_{k,\ t}=m_{k, \ t-1}-1$),

$$-1\times A(\frac{k}{2t})^2$$

3. vertex in A connect to a vertex in C ($m_{k,\ t}=m_{k, \ t-1}-1$),

$$-1\times 2A(\frac{k}{2t})(1-A\frac{k}{2t}-B\frac{k-1}{2t})$$

4. vertex in B connect to a different vertex in B ($m_{k,\ t}=m_{k, \ t-1}+2$),

$$2\times B(B-1)(\frac{k-1}{2t})^2$$

5. vertex in B connect to itself ($m_{k,\ t}=m_{k, \ t-1}+1$),

$$1\times B(\frac{k-1}{2t})^2$$

6. vertex in B connect to a vertex in C ($m_{k,\ t}=m_{k, \ t-1}+1$).

$$1\times 2B(\frac{k-1}{2t})(1-A\frac{k}{2t}-B\frac{k-1}{2t})$$

Adding everything up, there are still two quadratic terms $A(\frac{k}{2t})^2$ and $-B(\frac{k-1}{2t})^2$

Answer 1

We don't need the quadratic term you describe, because when we choose $2$ vertices with degree $k$ to join by an edge, we lose $2$ vertices of degree $k$; similarly, when we choose $2$ vertices of degree $k-1$ to join by an edge, we gain $2$ vertices of degree $k$.

So when an edge $\{r,s\}$ is added to the graph, the probability that vertex $r$ goes from degree $k$ to degree $k+1$ is $\frac{k\mathbb E[m_{k,t}]}{2t}$, and the probability that vertex $s$ goes from degree $k$ to degree $k+1$ is also $\frac{k\mathbb E[m_{k,t}]}{2t}$. These are not independent, but since we are computing expectation, this doesn't matter: the overall contribution to the number of vertices of degree $k$ from this possibility is $-2 \cdot \frac{k\mathbb E[m_{k,t}]}{2t}$. This explains the $-\frac{(1-p)2k}{2t}$ term you see in the formula.

A similar calculation tells us what to expect for vertices going from degree $k-1$ to degree $k$.