Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 1 / D6 / b / i / Solution

For the Erdős-Rényi model $G(n,p)$, choose the number $n$ of vertices and an edge probability $0\le p\le 1$. Visit every unordered pair of distinct vertices once and include its edge independently with probability $p$. This construction gives a simple graph with expected edge count $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and mean vertex degree $p(n-1)$.

Increasing $p$ at fixed $n$ makes the graph denser, increases typical vertex degree and local clustering coefficient, and tends to shorten graph distances and improve connectivity. Increasing $n$ at fixed $p$ also increases the mean vertex degree; to retain a sparse comparison one instead decreases $p$ approximately as $1/n$.

Its degree distribution is binomial distribution, approximately Poisson distribution in the sparse large-$n$ regime, so it is not a scale-free network. Connected realizations can have short average shortest path length, but their clustering coefficients are not elevated above the random baseline they themselves define. Thus they are not small-world networks under the high-clustering convention, although “small world” is sometimes used more loosely to mean only short distances.