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

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.