Deriving the Degree Distribution of the Barabási–Albert Model: Continuum Approximation#

1. Introduction#

The Barabási–Albert (BA) model explains how scale-free networks emerge through growth and preferential attachment.

Nodes that already have many connections are more likely to receive new connections.

This note derives the degree distribution of the BA model using the continuum approximation.

2. Growth Rules#

1. Start with a small seed network.
2. At each time step, add one new node.
3. The new node creates $m$ links.
4. Existing node $i$ receives a new link with probability proportional to its degree $k_i$.

Therefore,

$$ \Pi_i=\frac{k_i}{\sum_j k_j}. $$

3. Total Degree of the Network#

Each new node contributes $m$ new edges.

After $t$ steps,

$$ E \approx mt. $$

Since the sum of degrees equals twice the number of edges,

$$ \sum_j k_j \approx 2mt. $$

Thus,

$$ \Pi_i=\frac{k_i}{2mt}. $$

4. Growth of a Node’s Degree#

Consider node $i$ that entered the network at time $t_i$.

Initially,

$$ k_i(t_i)=m. $$

The expected degree growth is

$$ \frac{dk_i}{dt}=m\Pi_i. $$

Substituting the attachment probability,

$$ \frac{dk_i}{dt} = m\frac{k_i}{2mt} = \frac{k_i}{2t}. \tag{1} $$

Equation (1) is the core of the continuum approximation.

5. Solving the Differential Equation#

Starting from

$$ \frac{dk_i}{dt} = \frac{k_i}{2t}, $$

separate variables:

$$ \frac{dk_i}{k_i} = \frac{dt}{2t}. $$

Integrating,

$$ \ln k_i = \frac{1}{2}\ln t + C. $$

Exponentiating,

$$ k_i(t)=C’t^{1/2}. $$

Using the initial condition $k_i(t_i)=m$,

$$ C’=mt_i^{-1/2}. $$

Therefore,

$$ k_i(t) = m\left(\frac{t}{t_i}\right)^{1/2}. \tag{2} $$

or

$$ k_i(t) = m\sqrt{\frac{t}{t_i}}. $$

6. Interpretation#

Equation (2) implies:

• Earlier nodes accumulate more links.
• Later nodes have less time to grow.
• Degree grows as the square root of time.

This is a form of cumulative advantage.

7. From Degree Growth to Degree Distribution#

We seek the degree distribution $P(k)$.

Starting from

$$ k_i(t) = m\left(\frac{t}{t_i}\right)^{1/2}, $$

consider

$$ k_i(t)>k. $$

Then

$$ m\left(\frac{t}{t_i}\right)^{1/2}>k. $$

Rearranging,

$$ t_i<\frac{m^2t}{k^2}. \tag{3} $$

Thus nodes with degree greater than $k$ are nodes that entered sufficiently early.

8. Distribution of Arrival Times#

One node enters per time step.

Therefore arrival times are uniformly distributed on

$$ [0,t]. $$

Using Equation (3),

$$ P(K>k) = P\left(t_i<\frac{m^2t}{k^2}\right). $$

Since arrival times are uniform,

$$ P(K>k) = \frac{m^2t/k^2}{t} = \frac{m^2}{k^2}. $$

Hence,

$$ P(K>k)\sim k^{-2}. \tag{4} $$

9. Obtaining the Degree Distribution#

Differentiate Equation (4):

$$ P(k) = -\frac{d}{dk}P(K>k). $$

Therefore,

$$ P(k) \sim -\frac{d}{dk}k^{-2} \sim k^{-3}. $$

10. Why Does the Exponent Equal 3?#

The exponent emerges from two ingredients:

1. Degree growth:

$$ k(t)\sim t^{1/2}. $$

2. Uniform node arrival times.

Together,

$$ P(K>k)\sim k^{-2}, $$

which implies

$$ P(k)\sim k^{-3}. $$

11. Final Result#

The BA model produces a power-law degree distribution

$$ P(k)\sim k^{-3}. $$

with exponent

$$ \gamma=3. $$

This is the defining signature of a scale-free network.

One-Sentence Summary#

Early-arriving nodes accumulate links through preferential attachment, and this cumulative advantage generates the scale-free degree distribution

$$ P(k)\sim k^{-3}. $$