Degree-Preserving Rewiring

Every real network — a social graph, a protein-interaction map, the web — carries more than just a list of who is connected to whom. It carries structure: clusters, hubs, motifs, short paths. But is that structure really surprising, or is it just a side-effect of the fact that some nodes happen to have many more connections than others?

To answer that question, scientists build a null model: a random version of the network that keeps one chosen property fixed while shuffling everything else. For networks, the property that matters most is the degree sequence — the exact list of how many edges each node has.

Degree-preserving rewiring is the standard algorithm for that task. Pick two edges at random, swap their endpoints, and repeat. After enough swaps the network is thoroughly randomized — yet every single node still has exactly the same number of connections it started with. Any structure that survives or disappears in the comparison is genuinely meaningful, not a trivial consequence of node degree.

The technique was popularized by Maslov and Sneppen in their 2002 study of protein interaction networks, and it has since become the default starting point for testing structural hypotheses in graph theory and computational biology.

The demo below shows a small network. Each node displays its degree (number of edges). Click Rewire once to perform a single edge-swap: two edges are chosen at random, their endpoints are exchanged, and the network is redrawn. Every node's degree stays exactly the same throughout.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="panels">
  <div class="panel">
    <div class="panel-label">{{label_original}}</div>
    <canvas id="cvOrig" width="220" height="200"></canvas>
  </div>
  <div class="panel">
    <div class="panel-label">{{label_current}}</div>
    <canvas id="cvCurr" width="220" height="200"></canvas>
  </div>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btnOne" type="button">{{btn_rewire_one}}</button>
  <button id="btnMany" type="button">{{btn_rewire_many}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.panels { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .5rem; }
.panel { display: flex; flex-direction: column; align-items: center; }
.panel-label { font-size: .78rem; font-weight: 600; color: #555; margin-bottom: .25rem; letter-spacing: .04em; text-transform: uppercase; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fb; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0 .6rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d5a9e; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

After many rewirings the edge arrangement looks completely different, but the degree of every node is identical to the original. That is the whole point: the degree sequence is an invariant of the rewiring process. Compare the rewired network to the original to spot structure that is genuinely non-random.

The rewiring step itself is trivial — pick two edges, check the swap does not create a self-loop or duplicate edge, swap, done. Each step runs in $O(1)$. The hard question is subtler: does the Markov chain mix?

• Markov chain view. The set of all graphs with a fixed degree sequence forms a state space. Each rewiring step is a random move. After enough steps, the chain should converge to the uniform distribution over that space — every valid graph equally likely.
• Mixing time. How many steps are enough? For most degree sequences the chain mixes in $O(m \log m)$ steps, where $m$ is the number of edges, but tight bounds are hard to prove in general and remain an active research question.
• Forbidden swaps. Not every pair of edges can be swapped: the swap is rejected if it would create a multi-edge (two edges between the same pair of nodes) or a self-loop. In dense or irregular graphs, rejection rates can be high, slowing mixing.
• Configuration model shortcut. An alternative is to generate a random graph with the same degree sequence from scratch using the configuration model — assign each node $d_i$ stubs, then pair stubs uniformly at random. This is fast but may produce multi-edges, which are usually discarded, introducing a small bias.

Neither approach is perfectly uniform in general, but for most practical purposes rewiring with $Q \cdot m$ steps (where $Q \approx 100$ is a standard heuristic) produces samples that are indistinguishable from uniform in real-world experiments.

Degree-preserving rewiring is the workhorse behind nearly every claim that a network has "interesting" structure:

• Clustering coefficient. Real social networks cluster far more than their rewired counterparts. That excess clustering is genuine evidence of community structure, not just a side-effect of popular nodes having many friends.
• Network motifs. Alon and colleagues (2002) defined motifs as small subgraphs that appear significantly more often in a real network than in rewired controls. Every motif study depends on this null model.
• Degree–degree correlations (assortativity). Do high-degree nodes connect to other high-degree nodes? The rewired baseline tells you what to expect by chance, so any deviation is a real signal.
• Biological networks. Maslov and Sneppen's original application showed that protein hubs in yeast avoid connecting to each other — a pattern invisible without the rewired null.
• Robustness and epidemics. Epidemic-spread models on rewired networks isolate how the degree sequence alone controls outbreak size, separate from clustering or other structural features.

Rewiring also connects to broader themes: the configuration model underpins much of modern random graph theory, and the question of uniform sampling touches deep combinatorial questions about counting and approximate counting — topics at the heart of complexity theory.

Degree-preserving rewiring is one of those ideas that looks almost too simple — swap two edges, check nothing breaks, repeat — yet it gives network scientists their most reliable scientific tool: a null model that controls for the one structural property that dominates almost everything else.

Every time a biologist says a protein network is unusually clustered, or a sociologist says communities are more cohesive than chance, they are comparing to a rewired baseline. Without it, every observation risks being nothing but a reflection of degree.

In that sense, the algorithm is not just about graphs. It is about the scientific habit of asking: what would we see if only the simplest constraint were satisfied, and nothing else? The answer to that question is where real discovery begins.