Random Graphs and Null Models
A null model defines what variation is expected under a specific reference process. “Compare with a random graph” is incomplete: different generators preserve different properties and therefore answer different questions.
Prerequisites
Complete network visualization without misleading readers. You should understand which transformations produced the simple undirected graph used here.
Learning goals
- State the sample space and preserved quantities of a null model.
- Distinguish (G(n,m)), (G(n,p)), and degree-preserving references.
- Use fixed seeds to reproduce simulations without treating one draw as inference.
- Compare a hand-checkable observed statistic with a small null ensemble.
Match the null to the question
The (G(n,m)) model samples uniformly from simple graphs with (n) nodes and exactly (m) edges. The (G(n,p)) model includes each possible edge independently with probability (p), so its edge count varies. A configuration-model family preserves a degree sequence more directly but may produce parallel edges or self-loops depending on the implementation.
For a triangle comparison, (G(n,m)) controls only node and edge counts. It does not preserve direction, event multiplicity, weights, isolates outside the selected population, degree sequence, time, or opportunities for interaction. That makes it a transparent first reference, not the universally correct null model.
Worked example
The example removes the isolate, self-loop, direction, weights, and multiplicity explicitly before comparing triangle counts. It then generates five (G(6,7)) graphs with fixed seeds.
import csv
from pathlib import Path
import networkx as nx
fixture = Path("tests/fixtures/graph-data-science")
observed = nx.Graph()
observed.add_nodes_from(["ada", "ben", "cy", "dia", "eli", "fox"])
with (fixture / "interaction-relationships.csv").open(encoding="utf-8") as handle:
for row in csv.DictReader(handle):
if row["record_status"] == "valid" and row["source"] != row["target"]:
observed.add_edge(row["source"], row["target"])
def triangle_count(graph):
return sum(nx.triangles(graph).values()) // 3
seeds = [52, 53, 54, 55, 56]
null_triangles = [
triangle_count(nx.gnm_random_graph(6, 7, seed=seed))
for seed in seeds
]
print(
f"observed_nodes={observed.number_of_nodes()} observed_edges={observed.number_of_edges()} "
f"observed_triangles={triangle_count(observed)}"
)
print(f"gnm_seeds={seeds} null_triangles={null_triangles}")
Expected output:
observed_nodes=6 observed_edges=7 observed_triangles=2
gnm_seeds=[52, 53, 54, 55, 56] null_triangles=[2, 3, 1, 1, 1]
The observed count falls inside these five draws. Five simulations are too few for a stable tail probability, and the result applies only to this stated statistic and null model.
Limitations
- A fixed seed supports reproduction; it does not remove Monte Carlo error or model mismatch.
- Choosing a null after seeing the desired result invites confirmation bias. Predeclare the statistic and preserved structure.
- Network observations are often dependent, sampled, temporal, and opportunity-constrained. An independent-edge null may be unrealistic.
- A surprising statistic under one null model does not identify the mechanism that produced the graph.
Practice
Explain which conclusion changes if the reference preserves the observed degree sequence instead of only (n) and (m). Plan at least 1,000 simulations, a tail definition, and a Monte Carlo uncertainty report before computing a p-value.
Next steps
Next, use traversal, components, and reachability to answer deterministic path-existence questions on the original directed graph.
Primary sources
Checked 2026-10-18: NetworkX, gnm_random_graph; NetworkX, random graph generators; NetworkX, configuration_model; Gilbert, “Random Graphs” (1959).