Power-Law Degree Distributions

Definition

Many real-world networks have degree distributions that follow a power law:

$P(k) \propto k^{-\alpha}$

where $k$ is the node degree (number of edges incident to the node) and $\alpha$ is typically between $2$ and $3$. For the Web’s in-degree distribution, $\alpha \approx 2.1$; for citation networks, $\alpha \approx 3$.

Scale-Free Property

A power-law distribution is called scale-free because it looks the same at any scale. Formally, scaling the degree by a constant factor $c$ only multiplies the probability by $c^{-\alpha}$:

$P(c \cdot k) \propto (ck)^{-\alpha} = c^{-\alpha} \cdot k^{-\alpha} \propto P(k)$

There is no “characteristic” or “typical” degree that describes most nodes. The mean and the most probable value can be very different. In a random (Poisson) network, the degree is concentrated around a characteristic scale $\langle k \rangle$; in a scale-free network, there is no such concentration.

What It Means in Practice

• A few hubs have extremely high degree (thousands or millions of connections).
• Most nodes have very low degree (1–5 connections).
• The mean degree is not representative: it is pulled upward by the tiny fraction of hubs.
• The variance may be infinite (if $\alpha \leq 3$), meaning the degree varies enormously from node to node.

In the Web: a handful of sites (Google, Wikipedia, YouTube) receive a large fraction of all links; the vast majority of pages receive almost none. In citation networks: a few landmark papers are cited tens of thousands of times; most papers are cited once or not at all.

Origin: Preferential Attachment (Barabási-Albert Model)

The dominant explanation for power-law degree distributions is preferential attachment, also known as the “rich get richer” or “Matthew effect”.

Mechanism: when new nodes join the network, they do not connect uniformly at random. Instead, the probability that a new node connects to existing node $i$ is proportional to $k_i$ (the current degree of node $i$). Nodes that already have many connections attract even more connections from newcomers.

Over time, early-arriving nodes accumulate a disproportionate share of all edges. The few nodes that were “first to market” become the hubs. This positive feedback loop produces the heavy-tailed power-law distribution.

Robustness and Fragility

Power-law networks exhibit a sharp asymmetry in resilience:

• Robust to random failure: randomly removing a node is overwhelmingly likely to remove a low-degree node (since most nodes have low degree). Removing a leaf or low-degree node has minimal impact on connectivity because few shortest paths pass through it. The giant component survives extensive random damage.
• Fragile to targeted attack: removing the top 5–10% highest-degree nodes (the hubs) rapidly fragments the network. Since most shortest paths pass through hubs, their removal destroys the giant component. The Internet is robust to random router failures but vulnerable to a coordinated attack on major exchange points.

Contrast with Random (Erdős-Rényi) Networks

In an Erdős-Rényi random graph with $N$ nodes and edge probability $p$, the degree distribution is binomial (approximately Poisson for large $N$):

$P(k) \approx e^{-\langle k \rangle} \cdot \frac{\langle k \rangle^k}{k!}$

Property	Power-Law (Scale-Free)	Random (Erdős-Rényi)
Degree distribution	Heavy-tailed, $P(k) \propto k^{-\alpha}$	Poisson, peaked around $\langle k \rangle$
Hubs	Exist (nodes with extreme degree)	Do not exist (degree tightly bounded)
Mean degree	Poorly representative	Representative
Random failure	Robust	Moderately robust
Targeted attack	Very fragile	More resistant (no hubs to target)
Variance	May be infinite	Finite and moderate

Detecting Power-Law Behaviour

Plot $\log P(k)$ against $\log k$. If the degree distribution follows a power law, this log-log plot is approximately a straight line with slope $-\alpha$. This is the standard diagnostic. Real-world data rarely follows a perfect power law across all $k$ — often the tail (high $k$) deviates due to finite-size effects — but the broad trend is a straight line over several orders of magnitude.

Summary

Aspect	Property
Formula	$P(k) \propto k^{-\alpha}$, $\alpha \approx 2$–$3$
Meaning	Few hubs with very high degree; most nodes low-degree
Scale-free	Distribution looks the same at any scale; no “typical” degree
Origin	Preferential attachment (Barabási-Albert model)
Random failure	Robust (most nodes have low degree)
Targeted attack	Fragile (remove hubs, network fragments)
Diagnostic	Straight line on log-log plot of $P(k)$ vs $k$

Past paper questions: y2020p3q9, y2025p3q8