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

A network null model is an ensemble representing a specified baseline against which to assess an observed biological network. It should preserve the features that would otherwise confound the test: at least the number of vertices and edges, and often the degree sequence, direction, edge type, or relevant spatial constraints. It should randomize the feature whose biological organization is under investigation. An ensemble that preserves that very feature cannot test whether the feature is unusual.

For example, test whether a measured protein-protein interaction network contains more closed three-protein interaction groups than can be explained by the interaction counts of individual proteins. Define vertices as the measured proteins and an undirected edge as a reproducible detected interaction, using a fixed assay threshold and treatment of duplicates. Preselect the triangle count as the test statistic. Generate many simple random graphs by degree-preserving edge rewiring, rejecting self-loops and duplicate edges, with enough accepted swaps and separation to obtain a well-mixed reference sample. This retains the observed degree sequence while disrupting higher-order association.

Compute the same triangle count for every reference graph. Compare the observed count with this distribution; an empirical upper-tail p-value can be reported as $(1+\#\{T_{\mathrm{null}}\ge T_{\mathrm{obs}}\})/(M+1)$ for $M$ suitably sampled reference graphs. Report the size of the excess as well as its tail frequency, and check sensitivity to the assay threshold and any required connectivity constraint. A significant excess is evidence beyond the chosen degree baseline, while assay bias or spatial organization omitted from that baseline can still explain it.

A generative network model specifies a mechanism for producing networks, such as growth with preferential attachment, and asks what structures that mechanism creates. A network null model is defined by its role as a comparison baseline. These roles can overlap: the same random mechanism can be a proposed biological explanation in one analysis and a deliberately simplified null in another.

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]

The supplied adjacency matrix describes a four-vertex cycle graph, with every vertex degree equal to two. Degree-preserving edge rewiring is random, so it does not determine one unique labelled output adjacency matrix. For example, replace edges $AB$ and $CD$ by $AC$ and $BD$, retaining $AD$ and $BC$. This valid switch gives, in order $A,B,C,D$,Each row still sums to two. Under the simple graph convention, all allowed outputs have the same unlabelled four-cycle topology: there are three possible labelled four-cycles. A rejected switch or later return can also leave the original adjacency matrix.

It is not a scale-free network. Its degree distribution is concentrated entirely at degree two, with no power-law tail; degree-preserving edge rewiring cannot change that.

The diagram has all possible undirected edges except $AB$: it is a complete graph on five vertices with one edge removed. Therefore $A$ and $B$ each have three neighbours, while $C,D,E$ each have four.

The neighbours of $A$ and $B$ form a triangle, so their clustering coefficients equal one. Each of $C,D,E$ has five of the six possible neighbour–neighbour edges, giving $5/6$. The nodal average shortest path length is ${\ell }_i=\frac{1}{4}{\sum }_{j\ne i}d(i,j)$. All graph distances equal one except $d(A,B)=d(B,A)=2$, henceAveraging the nodal quantities givesThe ordered-pair distance sum is $22$, and the graph diameter is two.

If the intended unnormalized “small-worldness” is the ratio of clustering to path length, the computed quantities giveThat ratio has no universal threshold for identifying a small-world network. The standard reference-normalized small-worldness, $\sigma =(\bar{C}/C_{\mathrm{ref}})/(L/L_{\mathrm{ref}})$, cannot receive a numerical value when no reference is specified and the question forbids using a network null model.^[ref]

The graph has high clustering and short paths in the descriptive sense. With nine of ten possible edges, however, those properties follow directly from its near completeness; they do not by themselves establish small-world network structure relative to a reference. This distinguishes the metrics that can be computed directly from the stronger classification that requires a stated convention.