Network Models: Preferential Attachment, BA, and Erdős–Rényi

Complex Systems · 3/8 · Series index · Notation

Scale-Free Networks and Preferential Attachment: Deriving the Distribution from the Mechanism

We use $n$ for the number of nodes, $M$ for the total number of edges, and $m$ for the number of edges introduced by each new node in the BA model.

What Does a Network Represent, and What Does Scale-Free Mean?

A network represents a system through nodes (vertices) and edges (links). Whether the model is appropriate depends first on how these are defined. The Internet can be represented by computers or routers linked by communication connections; the WWW by web pages linked by directed hyperlinks; and a citation network by papers linked by directed citations. Other examples are power stations/substations and transmission lines in a power grid, people and friendships in a friendship network, metabolites and reactions in a metabolic network, neurons and synapses in a neural network, and species and predation relations in a food web. Direction, weight, and the level of detail used to define nodes depend on the question.

Degree and the Degree Distribution

In a simple undirected graph, the degree $k_i$ of node $i$ is its number of neighbors. If a node is selected uniformly at random, the probability that its degree is $k$ is

$$p(k)=\frac{n_k}{n},\qquad \sum_k p(k)=1,\qquad \langle k\rangle=\sum_k k p(k)=\frac{2M}{n},$$

Here $n_k$ is the number of nodes whose degree is exactly $k$. For a directed graph, in-degree and out-degree distributions must be considered separately. The defining feature of a scale-free network is an approximately power-law tail in its degree distribution; a visually tangled drawing is not sufficient:

$$p(k)\sim Ck^{-\gamma},\qquad S(k)=\Pr(K\geq k)\sim C'k^{-(\gamma-1)},\qquad \alpha=\gamma-1.$$

For discrete degrees, $p(k)$ is a probability mass function; it is a probability density only in the continuous approximation. $S(k)$ is the complementary cumulative distribution function (CCDF), whereas the ordinary CDF is $F(k)=\Pr(K\leq k)$. Do not label a decreasing power-law tail as the ordinary CDF.

What the Exponent Means

A power-law tail makes high-degree nodes more common than an exponential or Poisson tail does. Such high-degree nodes are called hubs. Power-law scale-free behavior does not generally require $\gamma<3$; the range $1<\gamma<3$ is important because the second moment diverges in an ideal distribution with no upper cutoff. The condition is $\langle K^r\rangle<\infty$ if and only if $\gamma>r+1$; at equality, the divergence is typically logarithmic. Thus, for $2<\gamma<3$, the mean is finite while the variance is infinite; $\gamma=3$ is the boundary for the second moment. Real finite networks have a maximum degree, and their finite-sample moments are finite.

Example: interpreting exponents. A degree distribution with $\gamma\approx3.4$ has a finite second moment under an ideal pure power-law model. A distribution with $\gamma\approx3$ lies at the boundary. An exponent above three does not rule out a power law, and a power-law fit to one network does not establish that all real networks are strictly scale-free.

Counting Nodes and Edges

For a graph with 8 nodes and 10 edges, including one isolated node, the degrees must sum to $20=2\times10$. This provides a consistency check on an edge count. In a drawing, a crossing without a node marker does not create a node, and arrows used only as labels are not edges.

The BA Model: Growth and Preferential Attachment

Start with a seed network containing $n_0$ nodes and $M_0$ edges. At each step, add one node and connect it to $m$ existing nodes:

$$n(t)=n_0+t,\quad M(t)=M_0+mt,\quad \Pi_i=\frac{k_i}{\sum_j k_j},\quad \sum_i\Pi_i=1.$$

Growth continually introduces new nodes. Preferential attachment makes existing nodes with higher degree more likely to receive new edges. The seed must give a nonzero denominator and contain enough existing nodes; normally $m\leq n_0$ is required. Distinguishing the initial edge count $M_0$ from the initial node count $n_0$ avoids ambiguity.

Continuous Approximation: A Complete Derivation of Exponent 3

Derivation outline: preferential attachment $\Rightarrow$ growth of an individual node's degree $\Rightarrow$ the relation between birth time and degree $\Rightarrow$ the degree distribution across the network.

Step 1: Write the Expected Growth Rate

Each step supplies $m$ new edges that can attach to existing nodes. The mean-field approximation for a large network is therefore

$$\frac{\mathrm d k_i}{\mathrm dt}=m\Pi_i =\frac{m k_i}{\sum_jk_j},\qquad \sum_j k_j=2M(t)=2(M_0+mt)\simeq 2mt.$$

Hence,

$$\frac{\mathrm d k_i}{\mathrm dt}=\frac{k_i}{2t},\qquad k_i(t_i)=m,$$

Here $t_i$ is the time at which node $i$ enters the network. The factor $2$ in the denominator comes from each undirected edge contributing $2$ to the total degree. The factor $m$ comes from adding $m$ edges per step. Both factors are essential.

Step 2: Separate Variables and Apply the Initial Condition

$$\int_m^{k_i(t)}\frac{\mathrm dk}{k} =\frac12\int_{t_i}^{t}\frac{\mathrm d\tau}{\tau} \quad\Longrightarrow\quad \ln\frac{k_i(t)}m=\frac12\ln\frac{t}{t_i}.$$

This gives

$$\boxed{k_i(t)=m\left(\frac{t}{t_i}\right)^{\beta},\qquad \beta=\frac12.}$$

At a fixed observation time, earlier nodes have higher expected degrees; the expected degree of a given node grows as $t^{1/2}$. Random realizations fluctuate, so the statement that older nodes have larger degrees on average does not mean that every pair of nodes must be ordered strictly by age. If the seed's edges are retained in the calculation, the same continuous equation gives $k_i(t)=m\sqrt{(M_0+mt)/(M_0+mt_i)}$, which approaches the expression above at large times.

Step 3: Obtain the CDF and CCDF from Birth Times

Select a node uniformly at a large observation time $T$. One node is born at each step, and the fraction of seed nodes tends to zero. Neglecting those seed nodes, $t_i$ is approximately uniform on $(0,T]$, with density $f_{t_i}(s)=1/T$. For $k\geq m$,

$$\begin{aligned} F(k)&=\Pr\!\left[m\left(\frac{T}{t_i}\right)^\beta<k\right] =\Pr\!\left[t_i>T\left(\frac{m}{k}\right)^{1/\beta}\right]\\ &=1-\left(\frac{m}{k}\right)^{1/\beta}, \qquad S(k)=\left(\frac{m}{k}\right)^{1/\beta}. \end{aligned}$$

The inequality reverses because $k_i$ decreases as birth time $t_i$ increases. Birth times are uniformly distributed; degrees are not.

Step 4: Differentiate

$$p_{\rm cont}(k)=\frac{\mathrm dF}{\mathrm dk} =\frac1\beta m^{1/\beta} k^{-(1+1/\beta)}.$$

Substituting $\beta=1/2$ gives

$$\boxed{p_{\rm cont}(k)=\frac{2m^2}{k^3},\quad S_{\rm cont}(k)=\frac{m^2}{k^2},\quad \gamma=1+\frac1\beta=3,\quad\alpha=2.}$$

The tail parameter $\alpha=2$ here does not make the BA degree distribution a Gaussian stable distribution: the BA second moment remains at the logarithmically divergent power-law boundary. The exponent is independent of $m$; changing $m$ changes the minimum degree, mean degree, and prefactor. The continuous approximation satisfies $\int_m^\infty p_{\rm cont}(k)\,\mathrm dk=1$ and has mean degree $2m$. Do not use this density as an exact discrete probability at small integer degrees.

The Master Equation: Discrete Degrees and the Birth Boundary Condition

The continuous approximation reveals the exponent conveniently; the master equation also gives the prefactor of the discrete degree probabilities. Let $q(k,t_i,t)$ denote the probability that a node born at $t_i$ has degree $k$ at time $t$. In the large-time approximation, that node increases its degree by one in the next step with probability $k/(2t)$, giving

$$q(k,t_i,t+1)=\frac{k-1}{2t}q(k-1,t_i,t) +\left(1-\frac{k}{2t}\right)q(k,t_i,t).$$

The first term is inflow from degree $k-1$ after receiving an edge; the second retains nodes that already had degree $k$ and receive no edge. For $m>1$, this is the standard large-network master-equation approximation. Choosing $m$ different targets without replacement in a finite network must not be described as an exact collection of independent Bernoulli trials.

Counting Nodes Makes the Birth Term Explicit

Let $N_k(t)$ be the expected number of nodes with degree $k$. Then

$$N_k(t+1)-N_k(t) =\frac{(k-1)N_{k-1}(t)-kN_k(t)}{2t}+\delta_{km},$$

Here $\delta_{km}=1$ when $k=m$ and is $0$ otherwise. The last term accounts for one new node of degree $m$ at every step. Suppose a stationary degree fraction exists, so that $N_k(t)\simeq t p(k)$. The left-hand side is then $p(k)$, not $0$: the network's total number of nodes is still growing.

$$p(k)=\frac{k-1}{2}p(k-1)-\frac{k}{2}p(k)+\delta_{km}.$$

Rearranging gives the unified equation

$$(k+2)p(k)=(k-1)p(k-1)+2\delta_{km}.$$

The Boundary at $k=m$ and the Recurrence for $k>m$

Each new node has minimum degree $m$, so the stationary fraction satisfies $p(m-1)=0$. A finite set of seed nodes does not affect the limiting fractions. Thus,

$$\boxed{p(m)=\frac{2}{m+2}},\qquad \boxed{p(k)=\frac{k-1}{k+2}\,p(k-1)\quad(k\geq m+1)}.$$

Multiplying the recurrence terms and canceling common factors yields

$$\begin{aligned} p(k)&=\frac{2}{m+2}\prod_{r=m+1}^{k}\frac{r-1}{r+2}\\ &=\frac{2}{m+2}\frac{m(m+1)\cdots(k-1)}{(m+3)(m+4)\cdots(k+2)}\\ &=\boxed{\frac{2m(m+1)}{k(k+1)(k+2)}} \sim 2m(m+1)k^{-3}. \end{aligned}$$

This is the asymptotic discrete degree distribution of the standard BA model, again with tail exponent $3$. Replacing $k(k+1)(k+2)$ by $k^3$ is an asymptotic approximation for $k\gg1$, not an identity valid at every $k$.

Normalization Checks and the Discrete Tail Probability

Use the identity

$$p(k)=m(m+1)\left[\frac1{k(k+1)}-\frac1{(k+1)(k+2)}\right],$$

The terms telescope, giving $\sum_{k=m}^\infty p(k)=1$. For an integer threshold $K\geq m$, they also give

$$\boxed{\Pr(k_i\geq K)=\frac{m(m+1)}{K(K+1)}},\qquad \sum_{k=m}^{\infty}kp(k)=2m.$$

The continuous prefactor $2m^2$ differs from the discrete prefactor $2m(m+1)$ because the two calculations use different levels of approximation. Their exponents, mean degrees, and large-degree behavior are consistent.

Testing the Mechanism and Comparing with Erdős–Rényi Networks

Why Are Both Mechanisms Needed?

Removing preferential attachment while retaining growth produces a rapidly decaying degree distribution. Removing growth and keeping a fixed node set also fails to maintain the BA model's growing power-law state. This explains how the two ingredients work together in the BA model; it does not establish that every power law must come from BA. A static graph can also be constructed directly with a specified power-law degree distribution.

A useful calculation is to choose the targets of new edges uniformly among existing nodes. Then $\mathrm dk_i/\mathrm dt\simeq m/t$, giving $k_i(t)\simeq m+m\ln(t/t_i)$. Combining this with uniformly distributed birth times gives the approximate tail probability $\Pr(K\geq k)\simeq\exp[-(k-m)/m]$, demonstrating that growth alone does not automatically produce a power law. Preferential attachment can be investigated empirically by measuring whether the probability of receiving new links increases with existing degree, for example in citation or collaboration networks.

Definition of the ER Model

In $G(n,p)$, fix $n$ nodes and connect each pair of distinct nodes independently by an undirected edge with probability $p$. There are no self-loops or parallel edges. Since there are $\binom n2$ possible edges,

$$M\sim\operatorname{Bin}\!\left(\binom n2,p\right),\qquad \mathrm E[M]=p\frac{n(n-1)}2.$$

The quantity $pn(n-1)/2$ is the expected number of edges; the realized edge count is random. A single node has $n-1$ potential neighbors, so

$$K\sim\operatorname{Bin}(n-1,p),\qquad \Pr(K=k)=\binom{n-1}{k}p^k(1-p)^{n-1-k},$$

$$c=\mathrm E[K]=(n-1)p,\qquad \operatorname{Var}(K)=(n-1)p(1-p).$$

Here $c$ is the theoretical mean-degree parameter; the realized mean degree of a particular graph is still $2M/n$.

The Poisson Limit for a Large Sparse Network

Let $n\to\infty$, taking $p=c/(n-1)\to0$ while holding $c$ fixed. For a fixed $k$,

$$\binom{n-1}{k}\simeq\frac{(n-1)^k}{k!},\qquad \left(1-\frac{c}{n-1}\right)^{n-1-k}\longrightarrow e^{-c}.$$

Substitution into the binomial probability gives

$$\boxed{\Pr(K=k)\longrightarrow e^{-c}\frac{c^k}{k!}},\qquad \mathrm E[K]=\operatorname{Var}(K)=c\quad\text{(Poisson limit)}.$$

In particular, the probability of an isolated node is $p(0)=e^{-c}$, so the expected number of isolated nodes is approximately $ne^{-c}$. This rare-event limit is not the central limit theorem. If $c$ is also large, a Poisson distribution can be further approximated by $\mathcal N(c,c)$. More generally, a binomial distribution admits a normal approximation when both $(n-1)p$ and $(n-1)(1-p)$ are sufficiently large. The sparse limit with fixed $c$ does not by itself make the degree distribution normal.

The Main Differences Between ER and BA

ER fixes the node set and assigns independent, identically distributed edge indicators. Degrees concentrate around $c$ and their tail decays rapidly. BA continually adds nodes, makes attachment depend on existing degree, has $\langle k\rangle\to2m$, and produces $p(k)\sim k^{-3}$ with more prominent high-degree nodes. ER graphs can still contain nodes whose degree exceeds the mean. Relative degree homogeneity does not mean that the maximum degree equals the mean.

Typical Scale-Free Network Problems: Calculations, Derivations, and Checks

Example 1: Growth of an Individual Node

In a BA model with $m=2$, a node enters at $t_i=25$. Find its expected degree at $T=400$.

$$k_i(400)\simeq2\sqrt{400/25}=8.$$

To estimate the time needed to reach degree $20$, solve $20=2\sqrt{T/25}$, which gives $T=2500$. This is a mean-field time scale; the time at which an individual random node actually reaches that degree fluctuates.

Example 2: A Continuous Density Is Not an Exact Discrete Probability

For $m=2$, the boundary condition and recurrence give

$$p(2)=\frac12,\qquad p(3)=\frac25p(2)=\frac15, \qquad p(4)=\frac36p(3)=\frac1{10}.$$

In a network with approximately $10^4$ nodes, the expected stationary number of nodes with degree exactly $3$ is about $2000$. The fraction with degree at least $10$ is

$$\Pr(K\geq10)=\frac{2\cdot3}{10\cdot11}=\frac3{55}\simeq0.0545.$$

The expected count is therefore about $545$. The continuous approximation gives $m^2/10^2=0.04$; it captures the scaling law and need not match the discrete result at a relatively small integer threshold.

Example 3: ER Network Parameters

Take $n=1000,p=0.004$:

$$c=999\times0.004=3.996,\qquad \mathrm E[M]=\frac{1000\times3.996}{2}=1998.$$

Since $p$ is small, approximate an individual node's degree by $\operatorname{Poisson}(3.996)$. For example,

$$\Pr(K=0)\simeq e^{-3.996}\simeq0.0184, \qquad \mathrm E[n_{\rm isolated}]\simeq18.4.$$

Here $n_{\rm isolated}$ is the number of isolated nodes. The value $18.4$ is an expectation; a realized count must be a nonnegative integer.

Example 4: Reading an Exponent from a Plot

If the degree probability $p(k)$ has slope $-2.7$ on a log–log plot, then $\gamma=2.7$, and the CCDF should have slope approximately $-1.7$. If a CCDF instead has slope $-2$, then $\gamma=3$, consistent with the standard BA exponent. This exponent alone does not prove that the generating mechanism is BA.

The Shortest Complete Derivation Answer

A complete continuous derivation should include $\Pi_i=k_i/\sum_j k_j$, $\sum_jk_j\simeq2mt$, $\dot k_i=k_i/(2t)$, $k_i(t_i)=m$, $k_i(t)=m(t/t_i)^{1/2}$, uniformly distributed birth times, $F(k)=1-m^2/k^2$, and $p(k)=2m^2k^{-3}$. A complete master-equation derivation should include inflow, outflow, the $\delta_{km}$ birth term, stationary fractions represented by $N_k(t)\simeq t p(k)$, the boundary value $p(m)$, the recurrence, and cancellation of its product.

Common Mistakes

• $\Pi_i$ describes the attachment tendency of one new edge; $m\Pi_i$ gives the approximate expected degree increase per time step.

• A "stationary degree distribution" means the fractions stop changing. It does not mean that the node count or individual degrees stop growing.

• $\gamma$ is the degree-probability exponent, whereas $\alpha=\gamma-1$ is the tail-probability exponent. For BA, $\gamma=3,\alpha=2$.

• Distinguish the continuous approximation $2m^2/k^3$ from the discrete result $2m(m+1)/[k(k+1)(k+2)]$ and state which one you are using.

• $G(n,p)$ fixes an edge probability. The ER model $G(n,M)$ fixes the edge count instead, so its edge indicators must not be assumed independent.

---

← Scale-free distributions · Series index · Network fundamentals →