Random Network (Erdős–Rényi) Simulation

What the simulation shows

The model has two parameters: the number of nodes n and the probability p that any given pair is linked. The lab asks for the mean degree c instead and sets p = c/(n − 1), so that networks of different sizes with the same c are comparable.

• Below c = 1 the network is dust. Most components are small trees; the largest one grows only like log n.
• Above c = 1 a giant component appears. Its share of the nodes rises steeply: about 58% at c = 1.5, 80% at c = 2 and 94% at c = 3. Everything outside it is still small.
• Degrees are Poisson. Nobody is a hub: the degree histogram is narrow and centered on c, unlike the heavy-tailed degrees of many real networks.

Press Play to rebuild the same network from nothing. Each pair was assigned one uniform random number when the network was generated, and a link is present at level p′ when that number is below p′. Raising p′ from 0 therefore adds links one at a time and passes through every G(n, p′) on the way, so you can watch the giant component form as the dot climbs the curve.

What theory predicts

Each of the n(n − 1)/2 pairs is an independent coin flip, so the number of edges is binomial with mean

A node’s degree is Binomial(n − 1, p), which tends to Poisson(c) as n grows with c fixed; in particular a fraction (1 − p)ⁿ⁻¹ ≈ e^−c of nodes is isolated.

For the giant component, let S be the fraction of nodes in it. A node is outside the giant component only if none of its neighbors is in it. With Poisson(c) neighbors, each inside with probability S, that happens with probability e^−cS, which gives the self-consistency equation

S = 0 always solves it; a second, positive solution exists exactly when c > 1, because the slope of the right-hand side at zero is c. The lab finds it by bisection. This is the simplest example of a percolation transition. Strictly, Erdős and Rényi studied graphs with a fixed number of edges, G(n, M); the version with independent links, G(n, p), was introduced by Gilbert the same year, and the two behave alike for large n.

Clustering, the probability that two neighbors of a node are themselves linked, is just p in this model, because every pair is linked independently. The expected number of triangles, C(n, 3)p³, tends to c³/6, so clustering vanishes as the network grows. Real social networks have far higher clustering and much more uneven degrees; the Watts–Strogatz small-world model and the configuration model are the usual next steps, and Newman’s Networks covers both.

Finite networks and what the numbers mean

The curve S(c) is a limit for n → ∞. In a network of a few hundred nodes the transition is smeared out: near c = 1 the largest component fluctuates a lot from seed to seed, and slightly below 1 it can still hold a noticeable fraction of a small network. Try n = 50 and n = 400 at c = 1.2 with several seeds.

Being connected is a different, later threshold: the whole network becomes one component only when isolated nodes disappear, around c ≈ ln n (about 5.3 for 200 nodes). Between c = 1 and ln n there is a giant component plus a shrinking scatter of small pieces, mostly isolated nodes.

The same giant-component threshold decides whether an infection can reach a large part of a contact network; an epidemic on a network builds on it. The drawing uses a force-directed layout computed only for display; node positions carry no meaning in the model.

Example result

With n = 200 nodes and mean degree c = 2 (p = 0.0101), seed 42 produced 212 edges against 200.0 expected, an observed mean degree of 2.12. The largest component holds 83.0% of the nodes, against the large-n prediction S = 79.7%, and 14.5% of nodes are isolated (theory 13.4%). The clustering coefficient is 0.0064 against p = 0.0101; the triangle count (1 here) stays near c³/6 ≈ 1.3 on average however large the network grows.

Implementation

The page runs simulation.js from the package below; the Python file is a line-by-line port with the same random-number generator, so a given seed produces the same result in both languages. The excerpts show the core of each.

// G(n, p): visit every pair once and link it with probability p. The uniform draw is
// kept with the edge, so the edges with u < p′ form G(n, p′) for any p′ ≤ p — the
// lab uses this to grow the network smoothly from empty.
export function generate(n, p, rng) {
  const edges = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const u = rng.uniform();
      if (u < p) edges.push([i, j, u]);
    }
  }
  return edges;
}

// Giant-component fraction S for mean degree c: the root of S = 1 − e^(−cS) in (0, 1],
// which exists only for c > 1 (bisection; S = 0 otherwise).
export function giantTheory(c) {
  if (c <= 1) return 0;
  let lo = 1e-12, hi = 1;
  for (let k = 0; k < 100; k++) {
    const mid = (lo + hi) / 2;
    if (mid - 1 + Math.exp(-c * mid) < 0) lo = mid; else hi = mid;
  }
  return (lo + hi) / 2;
}

def generate(n, p, rng):
    """G(n, p): link every pair independently with probability p; keep the uniform draw."""
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            u = rng.uniform()
            if u < p:
                edges.append((i, j, u))
    return edges


def giant_theory(c):
    """Root of S = 1 - exp(-c S) in (0, 1] for c > 1, found by bisection; 0 otherwise."""
    if c <= 1:
        return 0
    lo, hi = 1e-12, 1.0
    for _ in range(100):
        mid = (lo + hi) / 2
        if mid - 1 + math.exp(-c * mid) < 0:
            lo = mid
        else:
            hi = mid
    return (lo + hi) / 2

Run the full model from a terminal:

node simulation.js --n 200 --c 2 --seed 42
python simulation.py --n 200 --c 2 --seed 42

Download the model

Assumptions & limitations

• Independent, equally likely links. Every pair is linked with the same probability regardless of the rest of the network. No hubs, no communities, no geography.
• Undirected, simple graph. No self-loops, no multiple edges, no weights or directions.
• Theory is asymptotic. The giant-component fraction and the Poisson degree law are limits for large n; with at most 400 nodes, expect visible deviations, especially near c = 1.
• Clustering is the global transitivity: three times the number of triangles divided by the number of connected triples. It is undefined (shown as “—”) when no node has two neighbors.
• The layout is decoration. Positions come from a deterministic force-directed routine in the page, not from the model.

Related simulations

• OS-032Epidemic on a networkSIR spreading along the edges of random, small-world and scale-free networks, compared with homogeneous mixing.
• OS-033PageRankRank pages by where a random surfer spends its time: power iteration vs a simulated walk.
• OS-026Forest fire modelTrees grow, lightning strikes, fires spread: a cellular automaton with fires of every size.
• OS-012Random walkCoin-flip steps on a line or grid: distance grows like √n, and in 1-D and 2-D every walker comes back.

References

1. Erdős, P. & Rényi, A. (1959). On random graphs I. Publicationes Mathematicae Debrecen, 6, 290–297.
2. Newman, M. E. J. (2018). Networks, 2nd ed. Oxford University Press.