Preferential Attachment

• Motivation: A growing Random Graph Model that naturally generates a power law degree distribution
• Model: $n$ nodes arrives sequentially in $n$ steps; let $X_i(t)$ be the in-degree of node $i$ at time $i\le t\le n$;
  • Initialization: $X_i(i)=1\{i=1\}$
  • Evolution: $X(t+1)=X(t)+I_t$, where $I_t$ follows a Categorical Distribution supported on $\{1,\dots ,t\}$ with probability $p_i=p/t+(1-p)X_i(t)/t$
  • Extensions:
    • An entering node can form multiple links
    • Undirected
• Basic properties
  • Degree distribution: CDF $F(d)\approx 1-c{d}^{-1/(1-p)}$, corresponding to a power law distribution with tail exponent $\gamma =\frac{1}{1-p}+1$
  • Clustering: $o(1)$
• Diameter: $\ln n$ a.s.
  • When there are multiple links formed by an entering node, the diameter is $\frac{\ln n}{\ln \ln n}$ a.s.
• Remarks
  • The same process with $p=1$ (uniform attachment) generates an exponential degree distribution (^eq-exp), which has a tail lighter than power law, but heavier than Poisson distribution generated by ER model

Differential Equation Approximation

When $n$ is large, we can reindex the time steps as $0,ϵ,2ϵ,\dots ,1$ with $ϵ=1/n=o(1)$. Then, we have a differential equation approximation for the expected degree dynamics:

$$\mathbb{E}{X}_i(t+ϵ)-\mathbb{E}{X}_i(t)=\frac{ϵ}{t}(p+(1-p)X_i(t)).$$

Let $x_i(t):=\mathbb{E}{X}_i(t)$. We then have

$${\dot{x}}_i=(p+(1-p)x_i)/t.$$

Integrating the above equation with initial condition $x_i(i)=1\{i=1\}$ gives

$$x_i(t)=\{\begin{array}{ll}\frac{p}{1-p}(t^{1-p}/p-1),& i=1,\\ \frac{p}{1-p}((t/i{)}^{1-p}-1),& i\ge 2,\end{array}t\ge i.$$

We see that $x_i(t)$ is monotonically decreasing in $i$, showing a first-mover advantage.

Solving $x_i(t)=d$ gives

$$\frac{i}{t}={\left(1+\frac{1-p}{p}d\right)}^{-1/(1-p)},$$

indicating that

$$\frac{|\{i:x_i(t)\ge d\}|}{t}\propto d^{-1/(1-p)},\text{as }d\to \infty ,$$

giving a power law with parameter $\gamma =2+\frac{p}{1-p}$.

Mean Field Approximation

Let $f(k,t)$ be the fraction of nodes with degree $k$ at time $t$. Then, we have the following master equation for $k\ge 1$:

$$(t+1)f(k,t+1)=tf(k,t)+\underset{\text{link to a node of degree }k-1}{\underbrace{f(k-1,t)(p+(1-p)(k-1))}}-\underset{\text{link to a node of degree }k}{\underbrace{f(k,t)(p+(1-p)k)}}.$$

For $k=0$, we have

$$(t+1)f(0,t+1)=tf(0,t)+1-pf(0,t).$$

Suppose a stationary distribution $f(k)$ exists, then we have

$$\frac{f(k)}{f(k-1)}=\frac{p+(1-p)(k-1)}{1+p+(1-p)k}=\frac{k+\frac{2p-1}{1-p}}{k+\frac{1+p}{1-p}}$$

Note that for a discrete Power Law Distribution with parameter $\alpha =1$, when $k\gg 1$, we have

$$\frac{p(k)}{p(k-1)}=\frac{c{k}^{-\alpha }-c(k+1{)}^{-\alpha }}{c(k-1{)}^{-\alpha }-c{k}^{-\alpha }}=\frac{1-(1+k^{-1}{)}^{-\alpha }}{(1-k^{-1}{)}^{-\alpha }-1}\approx \frac{1-1+\alpha k^{-1}-\frac{\alpha (\alpha +1)}{2}{k}^{-2}}{1+\alpha k^{-1}+\frac{\alpha (\alpha +1)}{2}{k}^{-2}-1}=\frac{k-\frac{\alpha +1}{2}}{k+\frac{\alpha +1}{2}}.$$

Thus, $\gamma =\alpha +1=2+\frac{p}{1-p}>2$.

One can also observe the above equivalence by calculating that

$$p(k)=\frac{\mathrm{B}\left(k+\frac{p}{1-p},2+\frac{p}{1-p}\right)}{\mathrm{B}\left(\frac{p}{1-p},\frac{1}{1-p}\right)},$$

where $\mathrm{B}$ is the Beta function, and using the asymptotic property of the Beta function that $\mathrm{B}(x,y)\sim \Gamma (y)x^{-y}$ as $x\to \infty$ for fixed $y$.

Degree Correlation

Let $F_i^t$ be the expected degree distribution CDF of $i$‘s in-neighbors at time $t$. Since ^eq-exp is strictly decreasing in the time a node enters, we know the for any $i$’ in-neighbor $j$, $x_j(t)<x_i(t)$. Additionally, if at time $\tau$, a node $j$ enters and links to $i$, then a neighbor has an expected degree smaller than that of $j$ if and only if it comes after $j$. Thus, for $d<x_i(t)$,

$$F_i^t(d)=\frac{x_i(t)-x_i(\tau (d,t))}{x_i(t)},$$

where $\tau (d,t)$ is the entrance time of the node with expected degree $d$ at time $t$; any node after $\tau$ has expected degree smaller than $d$ at time $t$ and any node before $\tau$ has expected degree larger than $d$ at time $t$. Further, by ^eq-exp,

$$F_i^t(d)=1-\frac{(\tau /i{)}^{1-p}-1}{(t/i{)}^{1-p}-1},$$

which decreases in $i$ for any fixed $d$ and $t$. Thus, the first-movers’ expected neighbor degree distribution first-order stochastically dominates that of later-movers. Together with the first-mover advantage, we see a positive degree correlation (age-based homophily/assortativity).