Random Graphs & Networks

Erdos-Renyi, small-world, and scale-free networks

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.

In this section, you'll explore three foundational models: Erdős-Rényi random graphs, Watts-Strogatz small-world networks, and Barabási-Albert scale-free networks.

What You'll Learn

🎲
Random Graphs
Erdős-Rényi G(n,p) model
🌐
Small-World
Six degrees of separation
⭐
Scale-Free
Preferential attachment
📊
Network Metrics
Clustering and path length

Erdős-Rényi Random Graphs

The Erdős-Rényi model G(n,p) creates a random graph on n vertices where each possible edge exists independently with probability p. Adjust the parameters and generate!

0
Vertices
0
Edges
13.5
Expected
No
Connected
Connectivity threshold: p ≈ ln(n)/n = 0.230
✓ Above threshold - graph is likely connected

About Erdős-Rényi Graphs

  • Introduced by Paul Erdős and Alfréd Rényi in 1959
  • Expected edges: E[m] = p × n(n-1)/2
  • Sharp threshold at p = ln(n)/n for connectivity
  • Degree distribution is approximately Poisson

Small-World Networks

The Watts-Strogatz model shows how a regular network becomes a small-world with random rewiring. Adjust β to see the transition from regular → small-world → random!

Regular (β=0)Small-WorldRandom (β=1)
Original edges
Rewired edges
Small-World
0.000
Clustering
-
Avg Path
0
Rewired
0
Total Edges
Small-World Properties
High clustering (like regular) + Short paths (like random) = Six degrees of separation!

About Small-World Networks

  • Introduced by Watts & Strogatz in 1998
  • Models "six degrees of separation" phenomenon
  • Small β maintains clusters, adds shortcuts
  • Found in social networks, neural networks, power grids

Scale-Free Networks

The Barabási-Albert model demonstrates preferential attachment: new vertices connect to existing vertices with probability proportional to their degree. The rich get richer!

Hub vertices
Regular vertices
New vertex
0
Vertices
0
Edges
0
Max Degree
0
Steps
Degree Distribution
Degree (number of connections)
Preferential Attachment
New vertices are more likely to connect to high-degree vertices. Early vertices accumulate more connections over time, creating "hubs" — a hallmark of scale-free networks found in the web, social networks, and biological systems!

About Scale-Free Networks

  • Introduced by Barabási & Albert in 1999
  • Degree distribution follows a power law: P(k) ~ k−γ
  • Most nodes have few connections, few nodes (hubs) have many
  • Robust to random failures, vulnerable to targeted attacks

Network Properties Comparison

Compare key properties across different network models. Each model has distinct characteristics in clustering, path length, and degree distribution.

Small-World Sweet Spot
Watts-Strogatz achieves both high clustering (like regular lattice) and short paths (like random graphs) — the small-world property!
Scale-Free Hubs
Barabási-Albert has the widest degree range due to preferential attachment creating hub vertices with many connections.

Key Network Metrics

  • Clustering coefficient: Probability that neighbors are also connected
  • Average path length: Mean shortest path between all vertex pairs
  • Degree distribution: How connections are spread across vertices

What We've Learned

1. Erdős-Rényi Random Graphs: The simplest random graph model where each edge exists independently with probability p. Shows a sharp transition to connectivity at p = ln(n)/n.

2. Small-World Networks: The Watts-Strogatz model shows how adding a few random "shortcut" edges to a regular lattice dramatically reduces average path length while maintaining high clustering — explaining "six degrees of separation."

3. Scale-Free Networks: The Barabási-Albert model demonstrates preferential attachment where "the rich get richer." This creates hub vertices and a power-law degree distribution found in the web, social networks, and biology.

4. Network Properties: Different network models have characteristic clustering coefficients, average path lengths, and degree distributions that reveal their underlying structure.

Next Up: You've completed the main Graph Theory curriculum! Head to the Playground to explore freely and test your knowledge with quizzes.