Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2025 / Paper 2 / 6

Average the four local clustering coefficients and the four supplied mean graph distances, using the same weighting convention for the reference networks:The two reference values average to $C_{\mathrm{rand}}=0.35$ and $L_{\mathrm{rand}}=3.6$. The normalized small-worldness is the relative clustering divided by the relative path length,This uses the standard ratio-of-ratios definition, with the supplied degree-matched random graphs as the chosen reference ensemble.^[ref]

Under the conventional $\sigma >1$ criterion, the supplied summaries classify it as a small-world network: clustering is about $2.071$ times the reference value, while path length is only about $1.021$ times the reference value. Two reference random graphs permit a numerical comparison but do not establish the variability or statistical significance of that classification.

There is a literal consistency problem with describing these summaries as those of a four-vertex simple unweighted graph. Any finite graph distance is at most three, whereas the supplied mean path lengths exceed three. A local clustering coefficient with at most three neighbours can only be $0$, $1/3$, $2/3$ or $1$ under the usual definition, not $0.7$ or $0.8$. Thus the result above is the intended calculation from the given summaries; they cannot all describe an ordinary four-node simple unweighted network. A larger network or a separately specified weighted convention would be needed for a literal network interpretation.

No. A scale-free network is characterized by an approximately power-law tail in its degree distribution, $P(k)\propto k^{-\gamma }$ over a meaningful range. clustering coefficients and mean graph distances do not supply that distribution. One would need the degrees of vertices, enough observations over a substantial range, and a fitted power-law model assessed against alternatives. Four vertices cannot establish such a tail, even if their degrees were supplied. small-worldness alone does not imply a scale-free network.

Use degree-preserving edge rewiring, often called a double-edge swap. Select two edges $(u,v)$ and $(x,y)$ with four distinct endpoints, then replace them by $(u,y)$ and $(x,v)$, choosing the reconnection symmetrically. Reject a proposal that would create a self-loop or an already present edge if the target is a simple graph. Each endpoint loses one edge and gains one, so every degree of a vertex, as well as the numbers of vertices and edges, is preserved exactly.

Repeat many such random proposals to generate reference networks. With symmetric proposals, retaining rejected steps as self-transitions, the uniform distribution on the reachable degree-preserving realizations is stationary. Adequate mixing must be checked; a few successful swaps do not establish an independent random sample. Degree preservation alone does not preserve connectedness, so impose and check that extra restriction if the graph distance comparison requires connected networks.

Factor the characteristic polynomial as ${\lambda }^2({\lambda }^2-3)$. The eigenvalues, with algebraic multiplicity, are thereforeThe adjacency matrix describes a star graph with node 1 as the hub. For the positive leading eigenvalue $\lambda =\sqrt{3}$, write the hub component as $h$. The leaf equations $h=\lambda v_i$, for $i=2,3,4$, give equal leaf components $\ell =h/\sqrt{3}$. The hub equation is $3\ell =\lambda h$, which is consistent precisely because ${\lambda }^2=3$. Thus an eigenvector is $(\sqrt{3},1,1,1{)}^{\mathsf{T}}$.

Normalizing its Euclidean norm to one gives the eigenvector centralityNumerically this is $(0.707107,0.408248,0.408248,0.408248{)}^{\mathsf{T}}$. It satisfies both $Av=\sqrt{3}v$ and $v^{\mathsf{T}}v=1$. If “normalized” instead means maximum component one, use $(1,1/\sqrt{3},1/\sqrt{3},1/\sqrt{3})$; if it means components summing to one, divide $(\sqrt{3},1,1,1)$ by $\sqrt{3}+3$. The hub-to-leaf ratio $\sqrt{3}$ is invariant under these conventions. The negative leading-magnitude eigenvalue also has an eigenvector, but its mixed signs do not define nonnegative eigenvector centrality.

The Louvain method approximately maximizes network modularity. Start with each vertex in its own community. Repeatedly visit each vertex, evaluate moving it into each neighbouring community, and accept the move with the greatest positive modularity gain. When no such local move improves the score, contract each community into a new weighted vertex, summing inter-community edge weights and retaining internal edges as self-loops. Repeat local optimization and contraction until no further gain is obtained, then map the communities back to the original vertices.^[ref]

For an undirected unweighted graph with $m$ edges, degrees of vertices $k_i$ and community labels $c_i$, the objective isThe term $k_i{k}_j/(2m)$ subtracts the expected connectivity in a degree-based network null model. If all vertices are put in one community, the observed and expected total weights cancel, so $Q=0$. A partition with excess internal connectivity can have $Q>0$, and merging away that structure reduces the score. The modularity objective and positive-gain rule prevent arbitrary merging merely to increase cluster size. They do not forbid a single community in every possible network: if there is no better modular partition, one community may be an appropriate result. The method is a greedy heuristic, so it does not guarantee the global maximum of $Q$.