Erdos-Renyi, small-world, and scale-free networks
Random graphs are fundamental models for understanding complex networks in the real world. From social networks to the internet, random graph theory helps us understand how networks form and what properties emerge from simple generative rules.
Three foundational models capture different aspects of real networks: Erdos-Renyi random graphs exhibit sharp phase transitions, Watts-Strogatz networks explain the small-world phenomenon, and Barabasi-Albert models produce the hub-dominated structures seen in nature and technology.
The Erdos-Renyi model G(n,p) creates a random graph on n vertices where each possible edge exists independently with probability p. Adjust the parameters to observe the sharp connectivity threshold at p = ln(n)/n.
Key insight: There is a sharp phase transition at p = ln(n)/n where the graph almost surely becomes connected — below this threshold it is almost surely disconnected.
The Watts-Strogatz model demonstrates how adding a few random shortcut edges to a regular lattice dramatically reduces average path length while maintaining high clustering. This explains the “six degrees of separation” phenomenon.
Key insight: Even a small rewiring probability creates short paths across the network while preserving local structure — the defining property of small-world networks found in social, neural, and power systems.
The Barabasi-Albert model demonstrates preferential attachment: new vertices connect to existing vertices with probability proportional to their degree. This “rich get richer” mechanism produces hub vertices and power-law degree distributions.
Key insight: Preferential attachment creates a power-law degree distribution P(k) ~ k^(-gamma), making the network robust to random failures but vulnerable to targeted attacks on hub vertices.
Different network models have characteristic clustering coefficients, average path lengths, and degree distributions. Compare all four models side by side to see how their structural properties differ.
Key insight: Watts-Strogatz achieves the small-world sweet spot with both high clustering (like regular lattices) and short paths (like random graphs), while Barabasi-Albert stands out for its wide degree range.