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

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.

For the Watts-Strogatz model, choose $n$ vertices on a ring, an even initial vertex degree $K<n$, and a rewiring probability $p$. Connect each vertex to its $K/2$ nearest neighbours on each side. Consider each original clockwise edge once: with probability $p$, retain its starting endpoint and replace its other endpoint uniformly, excluding self-loops and duplicate edges. The edge count remains $nK/2$, although individual vertex degrees change.

Increasing $n$ at fixed $K$ lengthens unrewired-ring graph distances. Increasing $K$ adds edges and shortens distances. Increasing $p$ introduces shortcuts, sharply reducing average shortest path length at first, then progressively reducing the clustering coefficient by destroying local triangles.

The small-world network regime occurs at intermediate $p$ with sufficient shortcuts, substantial clustering, and $K\ll n$. At $p=0$ distances are long; near $p=1$ the clustering advantage disappears. The degree distribution remains concentrated around $K$, so this is not a scale-free network.^[ref]

For the Barabási-Albert model, choose a connected seed graph on $m_0$ vertices, the number $m\le m_0$ of new edges per added vertex, and a final size $n$. A complete seed with $m_0\ge 2$ suffices. Add one vertex at a time, attaching it to $m$ distinct existing vertices selected with weights proportional to their current vertex degrees. Exclude duplicate edges and self-loops.

Increasing $n$ creates a larger network and permits older hubs to grow. Increasing $m$ makes the graph denser, with asymptotic average vertex degree $2m$, and tends to shorten graph distances. The seed affects early structure and the oldest hubs; standard linear preferential attachment gives a robust large-size tail exponent.

Its asymptotic degree distribution is $P(k)\propto k^{-3}$, so it is a scale-free network. Hubs produce short average shortest path length, but elevated clustering coefficients are not automatic: $m=1$ with a tree seed gives a triangle-free tree, and clustering decreases with size in the standard model. The strict clustered small-world network property is therefore not guaranteed.^[ref]