Random Graphs, Small Worlds and Scale-Free Networks, Side by Side

Three generative models, three different worlds

Not all graphs that look tangled are alike. A random graph generator is a recipe: a small set of rules that, applied to n nodes, produces a network with statistically predictable structure. The three classic ones — Erdős-Rényi, Watts-Strogatz and Barabási-Albert — were each built to explain a different observation about real networks, and comparing them side by side on the same node count is the fastest way to see why network topology is not one thing.

Erdős-Rényi: pure chance, and the giant component

The G(n, p) model, introduced by Erdős and Rényi in 1959, is the simplest possible random graph: take n nodes, and for every one of the n(n-1)/2 possible edges, flip an independent coin with probability p and include it if it comes up heads. Nothing about it is engineered — no node is special, no edge is more or less likely than any other.

for each pair (i, j) with i != j:
  if random() < p:  add edge(i, j)

expected degree of each node  ≈  p * (n - 1)
expected total edges          ≈  p * n(n-1) / 2

Its most famous property is the phase transition: as p crosses the critical threshold 1/n, the graph abruptly flips from being a sea of small disconnected fragments into having one giant component that contains a positive fraction of all nodes, and that giant component's size jumps discontinuously — not gradually — right at the threshold. Below the threshold the largest connected piece is only O(log n) nodes; above it, one component swallows almost everything. This single result, from a purely combinatorial toy model, is why percolation theory and epidemic-threshold arguments so often reduce back to the same p ~ 1/n calculation. The trade-off is that G(n,p) is a poor model of real social or technological networks: its degree distribution is a tight binomial (everyone has roughly the same number of connections) and its clustering coefficient is exactly p, both far lower than what real networks actually show.

Watts-Strogatz: how a ring becomes a small world

Watts and Strogatz's 1998 model starts from the opposite extreme — a highly regular ring lattice where each node connects to its k nearest neighbours on both sides, which has high clustering (your neighbours' neighbours tend to be your neighbours too) but a large diameter (getting from one side of the ring to the other takes many hops). Then it rewires each edge to a uniformly random target with a small probability β:

start:  ring lattice, each node connected to k nearest neighbours (high clustering, long paths)
for each edge:
  with probability beta:  rewire it to a uniformly random new endpoint

beta = 0     → the original regular ring (high clustering, long paths)
beta = 1     → essentially an Erdos-Renyi random graph (low clustering, short paths)
beta ~ 0.01-0.1 → the "small-world" sweet spot

The striking empirical result is how narrow the transition is: even a tiny fraction of rewired edges — a few percent — is enough to collapse the average path length from O(n) down to O(log n), while the clustering coefficient barely drops from its high starting value. A handful of random long-range shortcuts act as bridges across the whole network, the same intuitive mechanism behind the famous “six degrees of separation” finding: most of your friends know each other (high local clustering), but a few acquaintances have connections in completely different social circles, and those rare long jumps are what make the whole world reachable in a few hops.

Barabási-Albert: growth plus preferential attachment gives you hubs

Neither of the previous two models produces the hubs seen in real networks like the web, citation graphs, or airline routes — a small number of nodes with vastly more connections than everyone else. The Barabási-Albert model (1999) generates them from two simple mechanisms combined: the network grows one node at a time (it does not start with a fixed n and rewire), and each new node attaches preferentially to existing nodes in proportion to how many connections they already have — “rich get richer”, formally called preferential attachment:

start with a small seed graph of m0 nodes
for each new node (n - m0 times):
  add m new edges from the new node to m EXISTING nodes,
  choosing each existing target with probability proportional to its current degree:

  P(connect to node i)  =  degree(i) / sum of all degrees

  // a node that already has many edges is proportionally more likely
  // to be picked as the target of yet another new edge

The resulting degree distribution follows a power law, P(degree = k) ∝ k^(-γ) with γ typically around 3 for the basic model — meaning there is no characteristic “average” node degree the way there is for Erdős-Rényi; instead a few hub nodes have enormous degree and the overwhelming majority have very few connections, a scale-free structure because that same shape appears no matter what range of degree you zoom into. This is a strikingly good match for the actual in-degree distribution of the world wide web, protein-interaction networks, and airline route maps, and it comes with a well-known practical consequence: scale-free networks are unusually robust to random node failure (remove a random node, it is almost certainly a low-degree leaf, and the network barely notices) but unusually fragile to a targeted attack on the hubs (remove the top few highest-degree nodes and the giant component can fragment rapidly).

Measuring what you generated

Three summary statistics are how you tell these structures apart quantitatively once a graph is generated, and they are exactly what the simulation on this page computes live after each layout settles:

clustering coefficient  = fraction of a node's neighbour-pairs that are
                          themselves connected, averaged over all nodes
                          (ER: low & uniform  |  WS: high  |  BA: moderate)

average path length     = mean shortest-path distance between all node pairs
                          (ER: short, ~log n  |  WS: short after rewiring
                           |  BA: very short, hubs act as universal shortcuts)

degree distribution     = histogram of how many nodes have each degree
                          (ER: binomial/Poisson, tight bell curve
                           |  WS: still fairly tight
                           |  BA: power law, heavy-tailed with hubs)

The layout: a physics simulation of its own

Drawing any of these graphs in a way a human can read is a separate problem from generating them, solved by treating the layout itself as a force-directed physical system: every pair of nodes repels like same-signed charges (so unrelated nodes spread apart), every edge pulls its two endpoints together like a spring (so connected nodes stay close), and the whole system is integrated forward in time — velocity damped — until it settles into a local energy minimum. That settling process is why a force-directed graph visibly “relaxes” into clusters and hubs pulling apart from sparse regions: the physics is doing the same job a human eye does when untangling a diagram, just automatically.

Frequently asked questions

Try it live

Everything above runs in your browser — open Network Topology Generator and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.