EC-SBM v1

Follow the edges by ownership, not just by final count.

v1 is easiest to understand as a ledger. The profile records what the output should resemble; each generation phase spends part of that ledger; the last phase tries to patch whatever earlier phases lost through duplicate removal or gridlock. The sections below zoom into each line item.

Step 1. Profile first gives the protected clusters a clean contract. With outlier_mode=excluded, singleton outliers and every incident edge are removed before assignment.csv, degree.csv, edge_counts.csv, and mincut.csv are written. That keeps the mincut promise meaningful, but the outlier-incident degrees and block counts now have to be rebuilt later.

Step 2. The \(K_{k+1}\) core reserves the mincut floor. Nodes are ranked by target degree, the first \(k+1\) become a complete graph, and every seed edge immediately decrements the residual degree and block-count budget. When \(k\) is large, this clique can dominate the cluster's triangle count and consume most of its diagonal budget.

Step 3. The remaining clustered nodes attach by availability. Each arrival samples \(k\) processed partners without replacement, weighted by \(a_v=\max(\texttt{int_deg}[v],0)\). If fewer than \(k\) processed nodes have positive availability, the guarantee wins and ensure_edge_capacity inflates the residual ledger so the required edge can still be placed.

Step 4. The SBM overlay spends the mutated residual matrix. graph-tool samples from the leftover probs and deg arrays, then v1 overlays those sampled edges onto the already committed core. If the SBM hits a core pair, simplification drops the duplicate after the budget has already been charged.

Step 5. The outlier rescue re-reads the original edgelist and makes each outlier a singleton block. A second SBM runs only on outlier-incident cells, recovering clustered-outlier and outlier-outlier counts without giving those singletons any connectivity guarantee or shared outlier structure.

Step 6. combine_edgelists.py merges the clustered and outlier bands into one simple edge file. It canonicalizes undirected pairs, keeps the first copy it sees, and writes sources.json row ranges; those ranges record surviving ownership, not every duplicate proposal that lost.

Step 7. The final match_degree --algorithm greedy pass drains residual degree deficits. It pops the largest deficit, scans legal non-neighbours, and adds top-up edges until partners run out. If a node gridlocks, v1 leaves those stubs out of the graph without an explicit warning.

Shared input graph: 18 clustered + 2 singletons.

The 20-node synthetic this page builds on, drawn under the shared singleton view: C1 (8), C2 (6), C3 (4), plus outliers 19 + 20 each in their own 1-node cluster. EC-SBM v1 then forces outlier_mode=excluded in the next stage, dropping outliers and their incident edges before profile counts anything; this view is the universal baseline before that exclusion.

Per-node block label. v1 forces outliers out.

Profile reads the empirical edgelist + clustering and writes seven CSVs. Two are lookups (node_id.csv, cluster_id.csv). Four carry the quantities the gen stages try to match, one per subsection below: assignment.csv, degree.csv, edge_counts.csv, mincut.csv. The seventh, com.csv, is the full (node, cluster) ledger and passes through to the final output unchanged.

v1 forces outlier_mode=excluded at profile time: any node not in a size-2+ cluster drops out, along with every edge incident to it. Those nodes come back later through a separate SBM call. v2 folds them into one combined pseudo-block instead; the rest of this page follows v1.

Step 1. The profiler starts from the empirical edgelist and community assignment. At this point outliers are still visible because the graph is still the original input.

Step 2. The protected domain is then filtered down to size-2+ clusters. EC-SBM's connectivity guarantee is per real cluster, so edges touching outliers are not counted in these ledgers.

Step 3. The profile emits the four generation targets below. Everything after profiling either spends one of these ledgers or repairs a deficit caused by earlier spending.

Per-node target degree, counted on the post-exclusion graph.

The second vector is degree.csv: \(k_u\) per node. Because outliers were just dropped, the degrees counted here exclude outlier-incident edges (a node that had 3 neighbours, 2 clustered and 1 outlier, lands at \(k_u = 2\)). Hover a node to find its bar on the right, or a bar to find its node. Gen stages treat the sequence as a target, not a guarantee: dedup and match-degree gridlock can push the achieved degree below.

Edge count per block pair, 3x3 on the synthetic.

The third input is edge_counts.csv. Read it as a half-edge count: how many half-edges from block \(r\) land in block \(s\). For \(r \neq s\) that coincides with the number of edges between the two blocks; for \(r = s\), each intra-block edge contributes twice (both halves inside \(r\)):

With outliers excluded, v1's matrix is a compact 3x3. Hover an edge to find its cell, or a cell to light up every edge that contributes to the count.

One new scalar per cluster: \(k(C)\).

For each cluster \(C\), the profile computes the minimum edge cut of \(C\)'s induced subgraph in the input. An edge cut for \(C\) is a set of edges whose removal disconnects \(C\); \(k(C)\) is the smallest such set's size. Measured via pymincut's Nagamochi-Ono-Ibaraki algorithm with a bucket-queue heap ("noi" / "bqueue"). Singleton clusters get \(k = 0\) by definition. Writes one integer per cluster to mincut.csv.

Each cluster's mincut on this synthetic, highlighted in red-dashed on the graph below. C1 has a non-trivial internal cut: two subsets of 4 nodes joined by a thin bridge of 2 edges. C2 and C3 isolate a single low-degree vertex.

Build a \(K_{k+1}\) seed clique. Attach the rest with \(k\) edges each.

Per cluster \(C\), sort nodes by target degree desc (id-asc tiebreak). Take the top \(k+1\) and wire them into a complete subgraph \(K_{k+1}\): that is \(\binom{k+1}{2}\) edges, with each node at degree exactly \(k\). A complete graph on \(k+1\) vertices is \(k\)-edge-connected, so any cluster that contains this \(K_{k+1}\) as a subgraph is \(k\)-edge-connected regardless of what the SBM layer does next.

Step 1. Rank by target degree using (-degree, node_id). The construction spends guaranteed edges on the nodes with the largest residual capacity first, and the id tie-break keeps the trace deterministic when degrees match.

Step 2. Emit every clique edge. When the processed set has at most \(k\) nodes, the new node connects to all processed nodes, so the first \(k+1\) arrivals form exactly \(K_{k+1}\).

Step 3. Charge the residual ledger as each constructive edge is placed: int_deg[u] -= 1, int_deg[v] -= 1, and the relevant probs[b_u,b_v] cell is decremented where possible. If a required edge has no remaining budget, v1 inflates the cell so the guarantee wins.

Phase 2 walks the remaining cluster nodes in descending target-degree order. Each new node \(u\) draws exactly \(k\) already-processed partners in one weighted-without-replacement sample, with each candidate \(v\) weighted by its availability \(a_v = \max(\texttt{int\_deg}[v], 0)\), the remaining residual degree. This is gen_kec_core.sample_by_availability: it picks \(\min(k,\,\#\{a_v > 0\})\) partners by weight, then if fewer than \(k\) candidates still have positive availability it fills the remainder uniformly from the exhausted ones (capacity inflation lets those edges still go in). There is no greedy "take the top-\(k\)" rule: a high-availability node is more likely to be picked, not certain to be. During the first \(k+1\) arrivals \(|N_0| \le k\), so the new vertex joins everything already processed, and the result of those arrivals is the \((k+1)\)-clique.

Attach step 1. Look only backward. The arriving node may connect only to nodes already processed in its cluster, which keeps the proof simple: each new node receives \(k\) independent paths into the already protected component.

Attach step 2. Sample by availability, not rank. Positive-residual candidates are in the weighted pool, while exhausted candidates enter only as a uniform fallback if too few positive candidates remain. A candidate with twice the availability is twice as likely in a single draw, but not guaranteed.

Attach step 3. Inflate only when forced. If the sampled partner would violate residual degree or block budget, v1 increases that residual budget by one and still places the edge. This preserves edge-connectivity but weakens exact degree matching.

When a partner's residual or the block-pair budget would block a required edge, ensure_edge_capacity inflates both by 1 so the edge can still go in:

Inflation is the only reason the output's degree sequence ends up approximate. The walker below mirrors gen_kec_core.generate_cluster arrival by arrival, in the same cluster-major order the shipped Python uses (clusters by size desc, nodes within each by post-exclusion target degree desc, id-asc tiebreak).

At each arrival the caption lists every already-processed candidate's availability \(a_v\) with the picked partners marked. Phase-1 arrivals (those with \(|V_t| \leq k\)) auto-attach to every predecessor and grow the \(K_{k+1}\) seed; phase-2 arrivals draw \(k\) partners by the availability-weighted sample above. The shipped Python draws from np.random.choice (MT19937); the walker reproduces the same weighting with a seeded LCG, so the marginals match but the exact picks are one realisation among many. random step re-samples the draw at the current arrival and downstream, leaving the locked prefix frozen; random all re-spins every phase-2 arrival.

Sample an SBM on the mutated residual, overlay the cores, drop duplicates.

After the constructive pass, probs and deg have been decremented by every edge the core + attach placed and inflated wherever the budget was too tight. v1 feeds those mutated arrays to graph-tool, overlays the constructive edges on top, and simplifies:

Step 1. Freeze the constructive band. The \(K_{k+1}\) core and attach edges are already committed; they are not suggestions to the SBM.

Step 2. Sample the residual SBM using the mutated deg vector, the mutated probs matrix, and graph-tool's micro_ers + micro_degs constraints. This restores remaining block-pair counts without reasoning about the mincut proof.

Step 3. Simplify after overlay. Dedup makes the final graph simple, but it can erase an edge the residual SBM already charged to the ledger; that is the v1 source of under-spent cells.

Step through the two phases and press random for a different SBM realization. The residual on this synthetic has 1 intra-C2 + 1 intra-C3 budget + 8 inter (4 C1-C2 + 2 C1-C3 + 2 C2-C3). Whether each intra sample lands on a fresh pair or duplicates a constructive edge depends on which slot the SBM picks; the dedup pass collapses any duplicates.

Outliers get their own SBM pass.

The constructive + overlay phase never saw outliers because the profile excluded them. This phase re-reads the original (pre-exclusion) edgelist, flags every node that is in the edgelist but not in the clustering, and treats each outlier as a size-1 block of its own. It then samples an SBM on the outlier-incident edges only (--scope outlier-incident); the SBM does not touch clustered-side pairs.

Step 1. Return to the original graph. The stage reads the pre-exclusion edge list so it can recover edges touching nodes 19 and 20 in this toy graph; the clustered-only profile no longer contains those edges.

Step 2. Make singleton blocks. Clustered nodes keep C1, C2, or C3, while outliers 19 and 20 each become a new one-node block. That converts "unclustered" vertices into ordinary SBM blocks for this pass.

Step 3. Sample only incident cells. The second SBM is scoped to cells with at least one singleton endpoint, and it does not resample any clustered-clustered pair that the previous stages already handled.

Merge sampled bands into one simple edge file and keep provenance.

At this point v1 has two independently sampled bands: the clustered band (constructive core, attach, residual SBM, and its dedup) and the outlier SBM band. combine_edgelists.py concatenates them in that order, applies undirected first-seen-wins dedup, then writes the final edge.csv plus sources.json.

Step 1. Canonicalize every row as \((\min(u,v), \max(u,v))\), so 7,19 and 19,7 are the same candidate edge.

Step 2. Keep the first copy. The clustered band is input 1, so it has priority if a later outlier-band row repeats an existing pair; the target is a simple graph, not a multigraph.

Step 3. Record row ownership. sources.json maps each generator band to an inclusive 1-based row interval in the final file, which lets diagnostics separate clustered, outlier, and degree-matching edges.

Heap-greedy top-up. The deficit accumulates; match_degree drains it.

Dedup and the outlier pass together remove some edges from each node's degree. The final phase tops that shortfall back up with src/match_degree.py --algorithm greedy (hardcoded in v1):

Step 1. Compute residual stubs: for each node, subtract its current degree after combine from the original degree.csv target, then keep max(target-current, 0) as the heap load.

Step 2. Pop the largest deficit. The heap prioritizes nodes with the most missing stubs, with node id as the deterministic tie-break; this is local repair, not a global matching solver.

Step 3. Add legal non-neighbour edges. The matcher scans candidates that are not already adjacent and adds edges until the popped node is satisfied or no legal partner remains.

Step 4. Accept gridlock silently. If legal partners run out, v1 drops the leftover stubs without a warning, which is why the bars below show both placed top-up and any remaining red deficit.

1. Build a max-heap of (-residual, node_id) over nodes still short of their target.
2. Pop \(u\). Compute \(u\)'s non-neighbours (live nodes minus \(u\) and its current neighbours).
3. Drain partners from \(u\)'s non-neighbour set in id-ascending order (canonical sorts the candidate set explicitly so the result does not depend on Python's set hash order) until \(u\)'s residual hits zero or candidates run out. Each pair becomes an edge; decrement both sides.
4. If \(u\) ran out of partners first, the remaining stubs are silently dropped. No log line, no warning.

Toggle apply match_degree to watch the deficit pile (the faint-red tail on each bar) drain. Click random for a different matcher realization.

What you get on the shipped example.

Default run on dnc + sbm-flat-best+cc at --seed 1:

The 87 clusters cover 551 nodes; the remaining 355 are outliers that excluded drops in profile. Mincuts on this input skew small: 60 clusters have \(k = 1\), 9 have \(k = 2\), 8 have \(k = 3\). A handful of larger clusters carry most of the construction load: \(k = 49\) on the biggest (50-node) cluster, \(k = 18\) on the 36-node one, \(k = 14\) and \(k = 13\) on the next two.

Provenance from sources.json, inclusive row ranges. The constructive + overlay band dominates; the outlier rescue is a thin strip; match_degree makes up the dedup shortfall.