Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Giant Component and Phase Transition

Computer Science Dept, Ferdowsi University of Mashhad

In the previous page we counted edges, degrees and triangles in G(n,p)G(n,p), and every answer was a number: the expected degree is (n−1)p(n-1)p, the degree distribution is Poisson, the number of triangles is roughly (n3)p3\binom{n}{3}p^3. This page asks a different kind of question — a geometric one. When we raise pp from 0 to 1, at which point does the graph stop being a dust of tiny components and grow one component that holds a positive fraction of all vertices?

The answer is a sharp change at p=1/np = 1/n, and the tool that explains it is the branching process. This is the cleanest example in the course of a threshold phenomenon: a quantity that is o(1)o(1) below a critical value and Θ(1)\Theta(1) above it, with no gradual transition in between.

Goals

  • Read the component of a vertex as a branching process, with mean offspring c=npc = np.

  • Derive the survival probability from the fixed-point equation s=1−e−css = 1 - e^{-cs}.

  • Locate the threshold p=1/np = 1/n and see why it is a rescaling, not a constant.

  • Simulate the largest component against npnp and compare with the theory.

  • Know the second threshold, p=log⁡n/np = \log n / n, where the graph becomes connected.

  • Meet the small-world model (Watts–Strogatz) as a one-paragraph survey.

1. The component of a vertex as a branching process

Fix a vertex vv and explore its component one vertex at a time. Vertex vv has Bin(n−1,p)\mathrm{Bin}(n-1, p) neighbours, of mean c=(n−1)pc = (n-1)p. Take one of those neighbours; among the remaining n−2n-2 vertices it expects (n−2)p(n-2)p new neighbours, and so on. As long as the explored set is small compared with nn, every newly discovered vertex contributes about cc new vertices, so the exploration is a Galton–Watson process with offspring distribution

X∼Bin(n−1,p)  ≈  Poisson(c),c=np.X \sim \mathrm{Bin}(n-1, p) \;\approx\; \mathrm{Poisson}(c), \qquad c = np .

The number of vertices in the component is the total progeny of this branching process. Two things follow at once:

  • If c<1c < 1 (subcritical) the expected offspring is below one, a generation dies out almost surely, and the component of vv has finite size with an exponential tail.

  • If c>1c > 1 (supercritical) there is a probability s>0s > 0 that the process never dies out; conditioned on survival it grows geometrically, that is, its size is Θ(n)\Theta(n).

The process is a good approximation only while the component is small; that is why it can say nothing about the giant component’s exact size. But the probability of survival is exactly what we need: it is the fraction of vertices that end up in the giant component.

2. The survival probability

Let qq be the probability that the process dies out starting from one vertex. A vertex dies out if each of its children dies out, so by the law of total probability, with P(X=k)=e−cck/k!\mathbb{P}(X=k) = e^{-c}c^k/k!,

q=∑k≥0e−cckk! qk=e−c(1−q).q = \sum_{k\ge 0} e^{-c}\frac{c^k}{k!}\, q^{k} = e^{-c(1-q)} .

The equation q=e−c(1−q)q = e^{-c(1-q)} always has the root q=1q = 1. A second root in [0,1)[0,1) exists exactly when the derivative at 1, which is cc, exceeds one. Writing s=1−qs = 1-q for the survival probability,

  s=1−e−cs  \boxed{\; s = 1 - e^{-cs} \;}

with s=0s = 0 for c≤1c \le 1 (the only root) and a unique positive root for c>1c > 1. Expanding 1−e−cs≈cs−12c2s21 - e^{-cs} \approx cs - \tfrac12 c^2 s^2 near c=1c = 1 gives

s  ≈  2(c−1)c2for c↓1,s \;\approx\; \frac{2(c-1)}{c^{2}} \quad\text{for } c \downarrow 1,

so the giant component grows linearly from zero with infinite slope — a second-order transition. In the graph itself the same quantity appears as the fraction of vertices in the giant component, which is the statement

∣Cmax⁡∣n→  p  s(c),c=np,\frac{|C_{\max}|}{n} \xrightarrow{\;p\;} s(c), \qquad c = np,

in probability, for cc fixed and n→∞n\to\infty.

<Figure size 640x480 with 1 Axes>

3. Why the threshold is p=1/np = 1/n and not a constant

The expectation of the degree is (n−1)p(n-1)p, so the question “is the mean degree above or below one?” is a question about the product npnp, not about pp. Two consequences:

  • Scaling. p=c/np = c/n keeps the mean degree fixed while nn grows. Any constant pp gives a graph that is a single dense blob — every vertex has Θ(n)\Theta(n) neighbours — and the notion of “component” loses its interest. The interesting regime lives at scale 1/n1/n.

  • Sharpness. The transition is not spread over an interval of pp of constant length: at the scale c=1+λn−1/3c = 1 + \lambda n^{-1/3} the largest component changes size, so the window has width Θ(n−2/3)\Theta(n^{-2/3}) in the number of edges, which is Θ(n−1/3)\Theta(n^{-1/3}) in cc. On the cc axis the transition looks sharp for large nn and blunt for small nn — exactly the finite-size effect we see in the next plot.

The same rescaling appears once more in this page: connectivity happens at p=(log⁡n)/np = (\log n)/n, again 1/n1/n times a slowly growing factor.

    c    s(c)    n=300   n=1500   n=6000
 0.30   0.000    0.022    0.005    0.002
 0.50   0.000    0.025    0.009    0.003
 0.70   0.000    0.041    0.021    0.005
 0.85   0.000    0.062    0.028    0.011
 0.95   0.000    0.155    0.072    0.030
 1.00   0.000    0.176    0.077    0.052
 1.05   0.094    0.166    0.162    0.100
 1.15   0.249    0.299    0.256    0.250
 1.30   0.423    0.375    0.419    0.420
 1.50   0.583    0.541    0.564    0.584
 1.80   0.732    0.711    0.725    0.730
 2.20   0.844    0.829    0.837    0.842
<Figure size 700x450 with 1 Axes>

Small nn rounds the corner of the curve and pushes the apparent threshold to the right: for n=300n = 300 the giant component only clearly appears around c≈1.5c \approx 1.5, while the limiting curve turns at c=1c = 1. This is the finite-size window of the previous section, not a disagreement with the theory. Note also that close to c=1c = 1 eight repetitions are not enough: half of the runs have a giant component and half do not, so the average jumps around. That is the bimodality of the next plot, seen from the outside.

A sharper diagnostic than the mean is the distribution of ∣Cmax⁡∣|C_{\max}| at a fixed cc near 1. Below the threshold it is small and concentrated; above it, a fraction ss of the runs produce a giant component while the rest stay small, so the histogram is bimodal right at the transition.

<Figure size 1100x320 with 3 Axes>

4. The second threshold: connectivity

A graph can have a giant component and still be disconnected: one isolated vertex is enough. The component of a fixed vertex has size nn only if the branching process stays alive and reaches every one of the remaining n−1n-1 vertices; the latter costs about (log⁡n)(\log n) generations, and the resulting threshold is

p=log⁡nn.p = \frac{\log n}{n} .

The reason the extra factor is logarithmic is the coupon-collector argument: the last isolated vertex is found by a union bound over nn vertices, each isolated with probability (1−p)n−1≈e−np(1-p)^{n-1} \approx e^{-np}, and ne−np→0n e^{-np} \to 0 requires np>log⁡nnp > \log n. So the graph becomes connected a constant factor above the point where the giant component appears.

<Figure size 640x480 with 1 Axes>

5. Small world: one paragraph

Erdős–Rényi graphs have short paths (diameter Θ(log⁡n)\Theta(\log n)) but almost no triangles. Real networks — social, biological, citation — have both. Watts and Strogatz start from a ring where each vertex is joined to its kk nearest neighbours, so clustering is high and paths are long, and then rewire each edge with probability β\beta to a uniformly random vertex. A tiny β\beta destroys the long paths (a few shortcuts are enough) while leaving most local triangles intact: the small-world regime. The model is here only as a bridge — clustering coefficients, path lengths and the degree distributions of real networks belong to a graph-mining course.

<Figure size 650x400 with 2 Axes>

6. What to remember

  1. The component of a vertex is a branching process with mean offspring c=npc = np; the giant component exists iff c>1c > 1, that is iff p>1/np > 1/n.

  2. Its asymptotic size is the survival probability ss, the positive root of s=1−e−css = 1 - e^{-cs}, which behaves like 2(c−1)/c22(c-1)/c^2 near the threshold.

  3. Two different thresholds live at the same scale 1/n1/n: the giant component at c=1c = 1 and connectivity at p=log⁡n/np = \log n / n.

  4. The tree-like approximation behind the branching process is what fails for the size, not for the threshold: loops are rare exactly when p=c/np = c/n.

The next page uses a graph as a state space rather than as a random object: a random walk on a fixed graph, its stationary distribution, and PageRank.

Exercises

  1. Model the component of a vertex as a branching process with Poisson offspring of mean c=npc=np. Show that the survival probability is zero for c≤1c\le1 and solve 1−s=e−cs1-s=e^{-cs} for c>1c>1.

  2. Simulate G(n,p)G(n,p) for n=104n=10^4 with pp around 1/n1/n, plot the size of the largest component against npnp, and locate the transition.

  3. Explain why the threshold is p=1/np=1/n and not a constant: rescale pp by nn and say which quantity stays fixed.

  4. Show that the expected number of triangles is (n3)p3\binom{n}{3}p^3 and that it tends to a constant when p=c/np = c/n. Explain why the branching-process approximation of the component is exact in this regime (hint: count cycles).

  5. Let qq be the extinction probability. Prove that q=1q=1 is always a root of q=e−c(1−q)q = e^{-c(1-q)}, and that the equation has a second root in [0,1)[0,1) if and only if c>1c>1, by looking at the derivative of f(q)=e−c(1−q)−qf(q) = e^{-c(1-q)} - q at q=1q=1.

  6. Use the coupon-collector argument to show that p=1+εnlog⁡np = \tfrac{1+\varepsilon}{n}\log n makes the probability of an isolated vertex tend to zero, and that p=1−εnlog⁡np = \tfrac{1-\varepsilon}{n}\log n leaves Θ(nε)\Theta(n^{\varepsilon}) isolated vertices on average.

  7. In the Watts–Strogatz experiment above, explain why the clustering coefficient barely changes for β≤0.03\beta \le 0.03 while the average path length already collapses. Which of the two is a local quantity?

Sources

  • Blum, Hopcroft, Kannan, Foundations of Data Science, Ch. 7–8 (branching processes and the giant component).

  • Durrett, Random Graph Dynamics, Ch. 1–2 (the critical window and the n−1/3n^{-1/3} scale).

  • Watts, D. and Strogatz, S., “Collective dynamics of ‘small-world’ networks”, Nature 393, 1998.

  • Bollobás, Random Graphs, Ch. 5–7 (connectivity and the (log⁡n)/n(\log n)/n threshold).