Introduction

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.

Try It

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.

<!-- Degree-preserving rewiring demo: two canvases (original vs rewired) -->
<p class="hint">Each node shows its <b>degree</b> (edge count). Click <b>Rewire once</b> to swap two edges at random — every degree stays the same. Compare the rewired network (right) with the original (left).</p>
<div class="panels">
  <div class="panel">
    <div class="panel-label">Original</div>
    <canvas id="cvOrig" width="220" height="200"></canvas>
  </div>
  <div class="panel">
    <div class="panel-label">Rewired</div>
    <canvas id="cvCurr" width="220" height="200"></canvas>
  </div>
</div>
<div class="status" id="status">Ready — click Rewire to start.</div>
<div class="btns">
  <button id="btnOne" type="button">Rewire once</button>
  <button id="btnMany" type="button">Rewire ×10 edges</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* Layout: side-by-side canvas panels with status bar and buttons */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Degree-preserving rewiring: pick two edges (a-b) and (c-d),
// swap to (a-d)(b-c) or (a-c)(b-d) if no self-loop or multi-edge results.

// Node positions (x,y) for a 6-node graph on a 220x200 canvas
const NODES = [
  { x: 110, y: 30 },
  { x: 200, y: 90 },
  { x: 175, y: 185 },
  { x: 60,  y: 185 },
  { x: 30,  y: 90 },
  { x: 110, y: 110 }
];

// Initial edge list — 8 edges, degrees: [2,3,2,3,3,3]
const ORIG_EDGES = [[0,1],[0,4],[1,2],[1,5],[2,3],[3,4],[3,5],[4,5]];

let edges = ORIG_EDGES.map(e => [...e]); // working copy that gets rewired
let rewireCount = 0;

// Compute degree of each node from edge list
function degrees(edgeList) {
  const d = new Array(NODES.length).fill(0);
  for (const [u, v] of edgeList) { d[u]++; d[v]++; }
  return d;
}

const origDeg = degrees(ORIG_EDGES);

// Draw graph on canvas: edges first, then node circles with degree labels
function drawGraph(canvas, edgeList, highlight) {
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // Draw each edge; highlight recently swapped edges in red
  for (let i = 0; i < edgeList.length; i++) {
    const [u, v] = edgeList[i];
    const isHl = highlight && (highlight[0] === i || highlight[1] === i);
    ctx.beginPath();
    ctx.moveTo(NODES[u].x, NODES[u].y);
    ctx.lineTo(NODES[v].x, NODES[v].y);
    ctx.strokeStyle = isHl ? '#e63946' : '#8fa8c0';
    ctx.lineWidth = isHl ? 2.5 : 1.5;
    ctx.stroke();
  }

  // Draw node circles with degree numbers inside
  const deg = degrees(edgeList);
  for (let i = 0; i < NODES.length; i++) {
    const { x, y } = NODES[i];
    ctx.beginPath();
    ctx.arc(x, y, 16, 0, 2 * Math.PI);
    ctx.fillStyle = '#1d3557';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(deg[i], x, y);
  }
}

// Attempt one degree-preserving rewiring step; return swapped indices or null
function tryRewire() {
  const m = edges.length;
  // Pick two distinct edge indices
  const i = Math.floor(Math.random() * m);
  let j = Math.floor(Math.random() * (m - 1));
  if (j >= i) j++;

  const [a, b] = edges[i];
  const [c, d] = edges[j];

  // Build current edge set string (for fast lookup), remove the two candidate edges
  const newEdgeSet = new Set(edges.map(([u, v]) => u + ',' + v).concat(edges.map(([u, v]) => v + ',' + u)));
  newEdgeSet.delete(a + ',' + b); newEdgeSet.delete(b + ',' + a);
  newEdgeSet.delete(c + ',' + d); newEdgeSet.delete(d + ',' + c);

  // Check swap variant 1: (a,d) and (b,c) — no self-loop, no multi-edge
  const ok1 = a !== d && b !== c && !newEdgeSet.has(a + ',' + d) && !newEdgeSet.has(d + ',' + a)
                                  && !newEdgeSet.has(b + ',' + c) && !newEdgeSet.has(c + ',' + b);

  if (ok1) {
    edges[i] = [a, d];
    edges[j] = [b, c];
    rewireCount++;
    return [i, j];
  }

  // Check swap variant 2: (a,c) and (b,d)
  const ok2 = a !== c && b !== d && !newEdgeSet.has(a + ',' + c) && !newEdgeSet.has(c + ',' + a)
                                  && !newEdgeSet.has(b + ',' + d) && !newEdgeSet.has(d + ',' + b);
  if (ok2) {
    edges[i] = [a, c];
    edges[j] = [b, d];
    rewireCount++;
    return [i, j];
  }
  return null; // swap rejected — try again
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

function redraw(highlight) {
  drawGraph(document.getElementById('cvOrig'), ORIG_EDGES, null);
  drawGraph(document.getElementById('cvCurr'), edges, highlight);
}

document.getElementById('btnOne').addEventListener('click', () => {
  // Attempt up to 20 times to find a valid rewiring
  let hl = null;
  for (let attempt = 0; attempt < 20; attempt++) {
    hl = tryRewire();
    if (hl) break;
  }
  redraw(hl);
  setStatus(i18nFmt('Rewired %n% time(s) — degrees unchanged.', { n: rewireCount }), 'ok');
});

document.getElementById('btnMany').addEventListener('click', () => {
  // Perform 10*m successful rewirings (standard Q*m heuristic)
  const target = edges.length * 10;
  let done = 0;
  for (let attempt = 0; attempt < target * 5 && done < target; attempt++) {
    if (tryRewire()) done++;
  }
  redraw(null);
  setStatus(i18nFmt('Rewired %n% time(s) — degrees unchanged.', { n: rewireCount }), 'ok');
});

document.getElementById('btnReset').addEventListener('click', () => {
  edges = ORIG_EDGES.map(e => [...e]);
  rewireCount = 0;
  redraw(null);
  setStatus('Ready — click Rewire to start.', 'info');
});

// Initial render on page load
redraw(null);
setStatus('Ready — click Rewire to start.', 'info');
Result
Console

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 Real Complexity

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)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(mlog⁡m)O(m \log m) steps, where mm 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 did_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⋅mQ \cdot m steps (where Q≈100Q \approx 100 is a standard heuristic) produces samples that are indistinguishable from uniform in real-world experiments.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/degree-preserving-rewiring/Content licensed under CC BY-NC 4.0.