ABCD

Shared input graph: 18 clustered + 2 singletons.

The 20-node synthetic this page builds on: C1 (8), C2 (6), C3 (4), plus outliers 19 + 20. ABCD requires \(\sum_j s_j = n\), so our wrapper's outlier_mode=singleton wraps each unclustered node in its own 1-node cluster. The graph below shows the resulting 5-cluster partition; ABCD's later sections all operate on this view.

Every node's degree, copied verbatim.

The profile is a deterministic function of the input; it does not change on re-roll. Profile writes three things. The first is degree.csv, the integer degree \(d_u\) per node, sorted desc. The Julia sampler reads the list unchanged and uses it as the exact degree target.

One integer per cluster, sum to \(n\).

The second file is cluster_sizes.csv, an integer size per cluster, sorted size desc. The paper requires \(\sum_j s_j = n\), so every input node lands in exactly one cluster. Our wrapper satisfies this via outlier_mode=singleton: every unclustered input node becomes a 1-node pseudo-cluster (ID __outlier_<id>__), so the size list sums to \(n\). Real clusters sort to the top; singletons tail. The next two sections show how the sampler uses this list to assign vertices and draw intra-cluster edges; output cluster sizes match the input verbatim.

One number: \(\xi\).

The third file is mixing_parameter.txt, a single float. Let \(E_{\text{out}}\) be the number of edges crossing cluster boundaries under the profile's clustering (singletons count, so outlier-incident edges are "inter" when the other endpoint is a different cluster). Then

The paper reads \(\xi\) as the expected fraction of each vertex's degree that the model routes to the background graph: \(\xi d_u\) background stubs, \((1 - \xi) d_u\) cluster-graph stubs. The realised inter-cluster fraction on output hits \(\xi\) only in expectation; on small graphs it drifts by a few percent seed-to-seed.

Big nodes to big clusters; small nodes fill the rest.

The sampler assigns each vertex to exactly one cluster before any edges are drawn. The paper frames this as a uniform draw from the admissible permutations; the Julia code uses a sequential proxy that walks vertices in descending \(d_u\) and at each step samples one cluster from the admissible set with probability proportional to its remaining capacity. A vertex \(u\) is admissible for cluster \(j\) iff \(x_u \le s_j - 1\), where \(x_u\) is the per-vertex bound below: the expected number of neighbours of \(u\) that will end up in \(u\)'s own cluster.

Vertices are processed by \(d_u\) desc, so admissibility only loosens as the walk proceeds: once a cluster fits a vertex, it fits every later vertex too. The sequential procedure is not equivalent to a uniform draw over admissible permutations: earlier high-\(d_u\) picks bias which clusters retain capacity for later vertices.

\(\phi\) is the probability that two nodes drawn uniformly at random fall in different clusters, with \(\phi \in [0, 1)\): one mega-cluster gives \(\phi = 0\), and evenly-sized clusters push \(\phi \to 1\). It enters the bound because not all of \(u\)'s \(\xi d_u\) background-routed half-edges actually leave the cluster; only the \(\phi\) fraction does, and the remaining \((1-\phi)\xi d_u\) lands back inside \(u\)'s own cluster by chance. \(u\)'s expected intra-degree is therefore \((1-\xi)d_u + (1-\phi)\xi d_u = (1-\xi\phi)d_u\), and \(x_u\) is the integer ceiling of that quantity.

The inequality \(\phi < 1\) is what keeps the post-split degree inside the cluster: since \(1 - \xi\phi \ge 1 - \xi\), the bound \(x_u \ge \lceil y_u \rceil \ge \hat y_u\), where \(y_u = (1-\xi)d_u\) is the intra-funded degree and \(\hat y_u\) is its integer realisation after the stochastic rounding the next stage performs. Combined with \(x_u \le s_j - 1\) under admissibility, this gives \(\hat y_u \le s_j - 1\), so the node's intra degree fits inside its cluster's other-member count.

Spend part of each degree on intra-cluster edges.

With the cluster assignment fixed, each vertex sets aside a portion of its degree for intra-cluster edges. The target portion is

and \(y_u\) funds the cluster graph \(G_{c(u)}\). Both that cluster graph and the later background graph are sampled by the configuration model (our default), which pairs integer stub counts exactly, rather than Chung-Lu, which only matches the degree sequence in expectation. Configuration-model pairing requires an integer \(\hat y_u\), so each cluster member rounds \(y_u\) to its floor and adds a Bernoulli bump with probability equal to the fractional part:

The leader (the cluster's largest-degree member, lowest vertex id on ties) is handled separately. It takes the deterministic floor \(\lfloor y_\ell \rfloor\) and adds 0 or 1 by parity: the bump fires when the sum of non-leader \(\hat y_u\) is odd and the floor is even, or vice versa, so the cluster's total internal stub count ends up even. Without that fixup, the cluster's configuration model would be one stub short of a clean pairing.

The leftover degree, \(\hat z_u = d_u - \hat y_u\), is the portion routed to the background graph. The background pool inherits any rewire residue from the cluster phase too, but that comes later; here it is enough to read \(\hat z_u\) off as the complement of \(\hat y_u\).

Pair \(\hat y_u\) stubs inside each cluster.

Each cluster graph \(G_j\) is a configuration model on its members' \(\hat y_u\) stubs. Each node \(u\) with \(c(u) = j\) contributes \(\hat y_u\) stubs as spokes around the node; they shuffle within the cluster and pair adjacent. Self-loops and parallels are flagged solid red; the next stage rewires them.

A note on layout. This page splits the inner loop by op-type: this stage walks every cluster's pairs, then the next stage walks every cluster's rewires. The Julia code finishes each cluster's pair-then-rewire pass before moving on, so the kernel narrative is by-cluster. Output is the same; the by-op-type split keeps the pairing and rewire mechanisms each in their own focused walker.

Cut the collisions, swap into valid edges.

Cluster-graph collisions (self-loops and parallels) move to a recycle list. Each recycle edge \(\{u_1, v_1\}\) is paired with a random other cluster edge \(\{u_2, v_2\}\) to make the swap (into \(\{u_1, u_2\}\) and \(\{v_1, v_2\}\), or \(\{u_1, v_2\}\) and \(\{v_1, u_2\}\)) and accepted if both new edges are simple. The rewire loop runs until the cluster graph is collision-free or runs out of moves; whatever is still on the recycle list at the end is dropped as an intra edge.

The dropped edges are not gone for good. For each leftover collision \(\{u, v\}\), one stub at each endpoint never paired inside the cluster. Those stubs are forwarded to the background pool, joining whatever the bg-split already allocated, and re-pair anonymously in the next stage. The specific intra edge is gone; the stubs survive and may form new bg edges with anyone.

Pair background stubs across the whole vertex set.

The background graph \(G_0\) is one global pool: every node drops its background stubs into the same urn and the configuration model pairs them without regard for cluster membership. Two members of the same cluster can pair; the resulting edge counts as intra-cluster on the output even though it came from the background. A bg edge that duplicates an existing cluster edge flags for rewire alongside the usual self-loops and parallels.

Same swap, global pool now.

Same recycle-and-rewire loop as the cluster phase, but the swap partners are drawn from every bg edge instead of one cluster's edges. Each new half is checked against the existing bg edges and the cluster output: if it would land as a self-loop or duplicate either set, it stays on the recycle list and remains visible as a solid-red bad edge until a later op clears it. Anything still on the recycle list when the loop stops is forwarded to the cross-cluster final swap stage; nothing is dropped here.

One last swap pass over the union.

If the background rewire loop finishes with a non-empty recycle list, a final fallback stage runs. It pulls each leftover bad edge \(\{u_1, v_1\}\) and tries to swap it against a partner \(\{u_2, v_2\}\) drawn uniformly from the union of cluster output and background output (intra + inter pooled together). The same two swap variants apply (\(\{u_1, u_2\} + \{v_1, v_2\}\) or \(\{u_1, v_2\} + \{v_1, u_2\}\)). Each new half is checked: if it is a self-loop or duplicates an existing edge in the union, that half goes back on the recycle list; otherwise it is added to the union and the original partner is removed. The loop runs until the recycle list is empty or stops shrinking.

Whatever bad edges remain after the loop are dropped from the output. This is the only place in the pipeline where a residue actually leaves the model.

Output degree multiset almost matches input.

Stubs only truly leave the model at the cross-cluster final swap's drop-stale step. Cluster-rewire residue forwards to the bg pool; bg-rewire residue forwards to the cross-cluster final swap; only what the final swap cannot resolve is dropped.

What you get on the shipped example.

Default run on dnc + sbm-flat-best+cc at --seed 1, every input outlier wrapped as its own singleton cluster:

The degree multiset and the cluster-size multiset pass through verbatim (modulo a handful of dropped edges in the cross-cluster final swap). Triangle-driven structure does not: \(cc\) lands at 0.307 against the 0.548 input. Random-walk dynamics shift in the same direction as SBM's top-up phase, but more sharply: bg pairing alone funds about \(\xi |E|\) cross-cluster edges, all drawn between high-degree hubs by stub probability, so the output is far better connected than the input even before any rewire.