Random networks
A random-network model treats some aspect of network structure as probabilistic. Instead of fixing every edge, we specify rules that generate a distribution over possible graphs.
Erdős–Rényi model
In the \(G(n,p)\) model, there are \(n\) nodes and every unordered pair of distinct nodes is connected independently with probability \(p\).
For each possible edge,
\[A_{ij}\sim\operatorname{Bernoulli}(p),\qquad iNumber of possible edges
A simple undirected graph with \(n\) nodes has
\[\boxed{\binom n2=\frac{n(n-1)}2}\]possible edges.
Because each is present independently with probability \(p\), the total number of edges satisfies
\[\boxed{|E|\sim\operatorname{Binomial}\left(\binom n2,p\right)}.\]Expected number of edges
Therefore
\[\boxed{E[|E|]=p\binom n2=\frac{pn(n-1)}2}.\]The expected mean degree follows from the handshaking identity:
\[\boxed{E[\langle k\rangle]=(n-1)p}.\]Degree distribution
Each node has \(n-1\) possible neighbours, with each edge present independently with probability \(p\). Hence
\[\boxed{K\sim\operatorname{Binomial}(n-1,p)}.\]Thus
\[E[K]=(n-1)p,\]and
\[\operatorname{Var}(K)=(n-1)p(1-p).\]Poisson approximation
Suppose \(n\) is large and \(p\) is small while
\[z=(n-1)p\]remains finite. Then
\[K\approx\operatorname{Poisson}(z),\]so
\[\boxed{P(K=k)\approx e^{-z}\frac{z^k}{k!}}.\]This is why Poisson degree distributions appear naturally in sparse Erdős–Rényi networks.
Sparse versus dense networks
If \(p\) stays fixed as \(n\) grows, expected degree grows like \(n\) and the network becomes dense.
If instead
\[p\approx\frac{z}{n},\]the expected degree remains approximately constant and the network is sparse.
Many biological networks are more naturally modelled in a sparse regime.
Independent edges
The defining assumption of \(G(n,p)\) is edge independence. Knowing that \(i\) is connected to \(j\) tells us nothing about whether \(i\) is connected to \(k\).
This makes the model mathematically convenient but can be biologically unrealistic when households, communities or spatial constraints create dependent edges.
Clustering in Erdős–Rényi graphs
If two nodes are both neighbours of a focal node, the probability that they are also connected is still \(p\). Therefore the expected local clustering coefficient is approximately
\[\boxed{C\approx p}.\]In sparse networks with \(p\sim z/n\), clustering tends to zero as \(n\) grows.
Real biological networks can have much stronger clustering than this.
Connected components
A connected component is a maximal set of nodes linked by paths. As mean degree increases, Erdős–Rényi graphs undergo a structural transition.
When
\[z=(n-1)p<1,\]components are typically small in the large-network limit.
When
\[z>1,\]a giant component containing a positive fraction of all nodes appears with high probability.
Giant-component equation
In a large Poisson random graph with mean degree \(z\), let \(S\) be the fraction of nodes in the giant component. Then
\[\boxed{S=1-e^{-zS}}.\]The solution \(S=0\) always exists. A positive solution appears when
\[\boxed{z>1}.\]This threshold is a structural property of the random graph.
Why giant components matter biologically
If transmission can travel only along network paths, an epidemic cannot reach more nodes than belong to the connected component containing the initial infection.
A giant connected component therefore creates the possibility of population-scale spread, although epidemic transmission also depends on transmissibility and recovery.
Bond percolation connection
Suppose each edge successfully transmits infection with probability \(T\). Retaining each edge independently with probability \(T\) creates a percolated network.
Large SIR outbreaks on locally tree-like random networks can often be related to giant components in this transmission network.
For a Poisson network with mean degree \(z\), the branching factor becomes approximately
\[Tz.\]A large transmission cluster becomes possible when
\[\boxed{Tz>1}.\]Configuration model
The Erdős–Rényi model does not allow us to specify an arbitrary degree distribution. The configuration model does.
We begin with a degree sequence
\[k_1,k_2,\ldots,k_n,\]whose sum must be even:
\[\sum_i k_i=2|E|.\]Each node receives \(k_i\) half-edges, or stubs, and these stubs are paired randomly.
What the configuration model preserves
The configuration model preserves the specified degree sequence, or asymptotically the specified degree distribution, while randomising which nodes are connected.
This makes it useful when degree heterogeneity is important but other structural information is unavailable or deliberately removed.
Configuration-model excess degree
If the degree distribution is \(P(k)\), following a random edge reaches degree \(k\) with probability
\[\frac{kP(k)}{\langle k\rangle}.\]The mean number of remaining edges is
\[\boxed{\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}}.\]A giant component is possible when this mean excess degree exceeds one:
\[\boxed{\frac{\langle k^2\rangle-\langle k\rangle}{\langle k\rangle}>1}.\]Equivalently,
\[\langle k^2\rangle-2\langle k\rangle>0.\]Self-loops and multiple edges
Random stub pairing can create self-loops or repeated edges between the same pair of nodes.
For many large sparse networks these may be rare enough to ignore, or one can condition on obtaining a simple graph. The modelling convention should be stated.
Random regular networks
A random regular graph fixes every node degree to the same value \(k_0\) and randomises the connections.
Its degree distribution is
\[P(k)=\begin{cases}1,&k=k_0,\\0,&k\ne k_0.\end{cases}\]This provides a useful contrast with heterogeneous configuration-model networks.
Small-world networks
Some random-network models are designed to combine high local clustering with relatively short path lengths.
Small-world constructions often begin with a locally structured network and randomly rewire or add a fraction of edges.
These models can be useful when biological contacts have strong local organisation but occasional long-range connections.
Community-structured random networks
Random networks can also include groups with different within-group and between-group connection probabilities.
In a stochastic block model, for example,
\[P(i\sim j)=p_{ab}\]when node \(i\) belongs to group \(a\) and node \(j\) to group \(b\).
This allows community structure and assortative mixing to be represented probabilistically.
Spatial random networks
If nodes have positions, connection probability can depend on distance:
\[P(i\sim j)=f(d_{ij}).\]Usually \(f\) decreases with distance. Such random geometric or spatial networks are useful for dispersal, local contact and habitat-connectivity problems.
Null models
A random-network model is often used as a null model. We compare an observed biological network with random networks that preserve selected features.
For example, a configuration-model null can preserve the degree sequence while randomising other structure. Differences in clustering or motif counts can then be assessed relative to this baseline.
Random does not mean biologically unstructured
A network can be generated probabilistically while still incorporating biological constraints such as degree distributions, communities, space or interaction types.
The word random describes uncertainty in network realisation, not absence of modelling assumptions.
Ensemble averages
A random-network model defines a distribution over graphs. Quantities such as mean degree, component size or epidemic probability can therefore be averaged over the network ensemble.
This differs from measuring the same quantity on one fixed observed graph.
Why model choice matters
Erdős–Rényi graphs assume independent edges and produce narrow degree distributions. Configuration models preserve degree heterogeneity but typically have weak clustering. Small-world and block models preserve different features.
A random-network model should therefore be chosen according to the biological structure relevant to the question.
Transition to epidemics on networks
The next lesson fixes or generates a network and then places infection and recovery dynamics on top of it. The focus shifts from network structure itself to how epidemic processes propagate through that structure.