Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 36 · Applications

Network Models: Small Worlds and Scale-Free Graphs

Generate and measure Erdos-Renyi, Watts-Strogatz small-world and Barabasi-Albert scale-free graphs in Python: giant components, clustering, path lengths and degree distributions.

Real networks such as friendships, the web, power grids and protein interactions are neither regular lattices nor completely random. They show surprising patterns: you can reach almost anyone in a few steps ("six degrees of separation"), your friends tend to know each other, and a few hubs have enormous numbers of links. To understand such patterns, graph theorists build random graph models and compare them with real data. This lesson introduces the three most important models and the statistics that tell them apart.

Statistics that describe a network

  • Degree distribution P(k): the fraction of vertices with degree k.
  • Average shortest path length L: the mean distance between connected pairs. Computed with BFS from every vertex.
  • Clustering coefficient C: for a vertex with d neighbors, the fraction of the d(d−1)/2 neighbor pairs that are themselves adjacent. It measures how often "a friend of my friend is my friend", i.e. the density of triangles around the vertex. The graph's C is the average over vertices.
  • Giant component: a connected component containing a large fraction of all vertices.

Three classic models

Erdős-Rényi Every pair linked with probability p
Watts-Strogatz Ring lattice plus random shortcuts
Barabási-Albert Rich get richer growth

Each reproduces a different real-world feature

1 / 2

Erdős-Rényi random graphs

In the G(n, p) model, each of the n(n−1)/2 possible edges is present independently with probability p. The expected degree is about (n−1)p. The model's key feature is a phase transition: when the average degree c = np is below 1, all components are small (size around log n); once c exceeds 1, a giant component containing a constant fraction of the vertices emerges. The graph becomes fully connected when p exceeds about ln n / n.

Python The giant component appears around average degree 1

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The jump from a few dozen vertices to most of the graph over a narrow range of c is the famous phase transition. However, G(n, p) has almost no clustering (C ≈ p) and a Poisson degree distribution without hubs, so it fails to describe social networks.

Watts-Strogatz small worlds

Start with a ring lattice: n vertices in a circle, each joined to its k nearest neighbors. This graph has high clustering (neighbors of neighbors are close together) but long paths (about n/2k). Now rewire each edge, with probability β, to a random endpoint. Even a small β creates a few long-range shortcuts that collapse the path length while barely touching the clustering. The result: high clustering with short paths, the small-world property of real social networks.

Python A few shortcuts make a small world

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With β = 0.05, the path length has dropped sharply while clustering is still close to the lattice value. This is the core finding of Watts and Strogatz: you do not need many shortcuts to shrink a network.

Barabási-Albert scale-free networks

Many networks have hubs: web pages with millions of links, airports with hundreds of routes. Their degree distribution follows a power law P(k) ∝ k^(−γ) with γ typically between 2 and 3, a heavy tail unlike the thin Poisson tail of random graphs. Barabási and Albert explained it with preferential attachment: the network grows one vertex at a time, and each new vertex links to m existing vertices chosen with probability proportional to their current degree. Popular vertices get more popular, "the rich get richer".

Python Preferential attachment grows hubs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both graphs have a similar average degree, but the Barabási-Albert graph contains hubs with degrees several times larger than anything in the random graph, and most vertices stay at the minimum degree. Hubs make scale-free networks robust against random failures but fragile against targeted attacks: removing a few hubs shatters the network, a fact used in studies of epidemics (vaccinate the hubs) and infrastructure security.

Comparing the models

Property Erdős-Rényi Watts-Strogatz Barabási-Albert
Degree distribution Poisson Narrow, near k Power law
Clustering Low (≈ p) High Low-moderate
Average path Short (~ ln n) Short with shortcuts Very short (~ ln n / ln ln n)
Hubs No No Yes

Real networks usually combine features, so researchers also use stochastic block models (communities), configuration models (fixed degree sequence) and geometric graphs. The best check for any model is to measure the statistics above on your real data and see which model reproduces them.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In G(n, p), what happens when the average degree np passes 1?

    Around np = 1 the random graph undergoes a phase transition: below it components are tiny, above it one component contains a constant fraction of all vertices.
  2. 2. What is the "small-world" property?

    Small-world networks resemble lattices locally (high clustering) yet have short paths because of a few long-range shortcuts.
  3. 3. What rule creates hubs in the Barabási-Albert model?

    Preferential attachment makes high-degree vertices more likely to gain further edges, which produces a heavy-tailed degree distribution.
  4. 4. Why are scale-free networks fragile to targeted attacks?

    A random failure usually hits a low-degree vertex, but deliberately removing hubs destroys many paths at once.

Summary

  • Network statistics: degree distribution, average path length, clustering coefficient and giant component.
  • Erdős-Rényi graphs have a sharp giant-component threshold at average degree 1 but little clustering and no hubs.
  • Watts-Strogatz graphs show that a few random shortcuts give small-world behavior: high clustering and short paths.
  • Barabási-Albert preferential attachment produces power-law degrees and hubs, which makes networks robust to random failure yet vulnerable to targeted attack.

Next: Project: Campus Timetable Scheduler