Preferential attachment

In preferential attachment, new edges favour existing vertices in proportion to a prescribed attractiveness, often their current degree of a vertex. A complete model must specify initial conditions, self-loop conventions and the normalization at each attachment. These details matter for the vertex degree distribution of the earliest vertices.

The Barabási-Albert model constructs a growing random graph by preferential attachment. Starting from a suitable seed, each new vertex brings $m$ edges and selects existing endpoints with probability proportional to their current degrees. A convention for sampling distinct endpoints must be specified.^[ref]

Older high-degree vertices tend to attract more edges. In the standard large-graph limit, the degree distribution has a tail proportional to $k^{-3}$, unlike the sharply concentrated degrees of a basic Erdős-Rényi model. Both growth and the attachment rule matter. The model supplies a mechanism for hubs; observing a heavy degree tail alone does not establish that this mechanism generated the data.

Start with one self-loop, and at step $t$ add one vertex and one edge. An old vertex $i$ is chosen with probability $d_i(t-1)/(2t-1)$, and the new vertex is chosen with probability $1/(2t-1)$, producing a self-loop. Self-loops contribute two to the degree of a vertex. There are $n$ edges and total vertex degree $2n$ at time $n$. This exact normalization is distinct from treating the total vertex degree as the number of edges.

In a uniform linearized chord diagram, $\mathrm{Pr}(\sqrt{n}{R}_1\ge x)=(1-x^2/n{)}^n\to e^{-x^2}$. Conditional on the right endpoints, $d_1(n)=2+{\sum }_{i=2}^n{1}_{\{L_i\le R_1\}}$, with independent success probabilities $R_1/R_i$. A Chernoff bound gives $R_i=(1+o(1))\sqrt{i/n}$ uniformly for $i\ge n^{1/10}$. The early indicators are $o(\sqrt{n})$, and the remaining conditional mean is $(2+o(1))n{R}_1$. Their conditional variance is $O_{\mathbb{P}}(\sqrt{n})$. Hence $d_1(n)/\sqrt{n}-2\sqrt{n}{R}_1\to 0$ in probability, proving the displayed tail limit. A self-loop's contribution is included in the constant two.

Pair $2n$ linearly ordered endpoints uniformly. Each pair is a chord; its larger endpoint ends a vertex block, with all endpoints after the previous right endpoint merged into that vertex. Orient the chord from its right-endpoint block to its left-endpoint block. Removing the last endpoint and its mate leaves a uniform smaller pairing. Reinserting the mate into one of $2n-1$ equally likely gaps chooses an existing block proportionally to its endpoint count, or the final gap creates a self-loop. This proves equivalence with the linearized chord diagram model.

An equivalent continuous representation draws $n$ independent pairs of independent uniform points on $[0,1]$, orders the pairs by their maxima $R_1<\cdots <R_n$, and calls their minima $L_i$. The $R_i^2$ are uniform order statistics; conditional on all the $R_i$, the $L_i$ are independent uniform points on $[0,R_i]$.