Random Graphs & 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.

The Erdos-Renyi model G(n,p) creates a random graph on n vertices where each possible edge exists independently with probability p. 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. 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. 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. 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.