EC-SBM v3

v3 changes the cluster interior, then hands off to v2.

The page has two ideas to keep separate. Stage 2 is a per-cluster PSO learner for triangle density; stages 3 and 4 are the same residual accounting and matcher pipeline used by v2.

Step 1. Profile carries both the robustness floor and the triangle-density target for each real cluster. mincut.csv gives \(k(C)\); under --method pso, cluster_ccoeff.csv gives \(\hat c(C)\). Tiny or triplet-free clusters carry little shape information, so \(\hat c(C)\) is most useful where the induced cluster has enough internal paths.

Step 2. Stage 2 builds one hyperbolic disk per cluster. Degree rank fixes arrival order and \(r_i=2\log i\); iid angles locate nodes; PSO weights choose older partners. This replaces the fixed v2 core shape with geometry that can express different triangle densities, though each cluster realization is still a sample.

Step 3. \(m = \min(\max(k, m_\text{floor}), n-1)\) keeps the v1/v2 edge-connectivity guarantee while changing partner selection. The \(K_{m+1}\) seed and \(m\) back-attachments make the stage-2 cluster at least \(m\)-edge-connected; when \(k\) is large, \(m\) can still force a dense seed even if the cc search would prefer a sparser shape.

Step 4. The T search chooses the evaluated realization whose stage-2 cluster is closest to the empirical \(\hat c(C)\). Bisection/secant proposals stay inside the bracket, but the target is stochastic and per-cluster; it does not guarantee the final global cc.

Step 5. The downstream handoff is v2's ledger with a different debit. Stage 3 subtracts exactly the chosen PSO edges before building out_degs and probs; PSO can over- or under-spend a diagonal relative to v2, so the residual signs can change by block.

Step 6. The matcher is inherited too. v3 reuses v2's block-aware true_greedy acceptance checks and gridlock logging, so remaining degree deficits are repaired only where the block-pair budget permits.

Step 7. Provenance separates what changed in v3 from what was inherited. Stage colors and walker labels distinguish PSO, residual SBM, rewire partners, and matcher top-up edges; the rewire partner color is a diagnostic moment, while final ownership remains with the residual or matcher stage.

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 v2 then forces outlier_mode=excluded in the next stage, dropping outliers from the profile-time partition; stage 3 folds them back as a combined block. This view is the universal baseline before either move.

Per-node block label. Outliers excluded now, folded back at stage 3.

Profile writes the same seven CSVs as v1: node_id, cluster_id, assignment, degree, edge_counts, mincut, and com. v2 also forces outlier_mode=excluded, so profile's tables cover only the clustered sub-network. The difference shows up later: at stage 3, v2 re-reads the empirical edgelist and folds every outlier into one combined pseudo-block, while v1 creates one singleton block per outlier.

Per-node target degree, post-exclusion.

Same as v1: degree.csv carries \(k_u\) counted on the post-exclusion graph. The constructive phase uses these numbers; stage 3 then bumps per-node out_degs by each node's outlier-incident count after re-reading the original edgelist.

Edge count per block pair. 3x3 now, 4x4 at stage 3.

Same half-edge convention as v1 / SBM:

At profile time v2's matrix is the same compact 3x3 as v1 (outliers excluded). Stage 3 then rebuilds a 4x4 by re-reading the original edgelist and adding the combined outlier block on the fourth row/column.

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

Same profile addition as v1. mincut.csv records the minimum edge cut of each cluster's induced subgraph in the input, measured via pymincut's Nagamochi-Ono-Ibaraki algorithm with a bucket-queue heap. Singleton clusters get \(k = 0\).

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.

One new scalar per cluster: \(\hat c(C)\), the v3 stage-2 target.

v3's profile asks one extra question of every cluster: what is the global clustering coefficient of its intra-cluster induced subgraph? The pso method's stage-2 T-search drives the simulated cc toward this target, one cluster at a time.

where \(|\Delta(G[C])|\) is the triangle count and \(|\Lambda(G[C])|\) is the number of connected triplets (length-2 paths) of the induced subgraph \(G[C]\). The profile artifact is cluster_ccoeff.csv, one float per cluster iid, only emitted under --method pso.

Step 1. \(k(C)\) remains a floor, not a shape. It measures the minimum number of intra-cluster edges whose removal can disconnect \(G[C]\), writes one row per cluster to mincut.csv, and prevents the generator from making a cluster easier to cut than the empirical one.

Step 2. \(\hat c(C)\) is the PSO target. It records the global clustering coefficient of the induced subgraph \(G[C]\); two clusters can have the same \(k(C)\) but very different triangle density, so v3 needs this second signal. cluster_ccoeff.csv is emitted only for --method pso, then each row feeds that cluster's T search.

Step 3. The old v2 ledger stays intact. node_id, assignment, degree, and edge_counts stay on the outlier-excluded clustered graph because stage 2 only needs real clusters; stage 3 later re-introduces outliers as one combined block. The same profile files become the index map for converting local PSO edges back to page/global node ids.

One PSO build per cluster. T tuned to match \(\hat c(C)\).

Stage 2 dispatches one independent PSO build per cluster. Each cluster's nodes are sorted by descending profile-time degree (id-asc tiebreak), giving each node a 1-based arrival rank that fixes its radial coordinate \(r_i = 2\log i\). Angular coordinates are drawn iid from \(\mathrm{Uniform}[0, 2\pi)\). Attachment count is \(m = \min(\max(k, m_\text{floor}), n - 1)\) with default \(m_\text{floor} = 1\), so \(m \ge k\) — the per-cluster mincut floor still holds.

The first \(m+1\) arrivals connect to all predecessors (a \(K_{m+1}\) clique seed). Each later arrival \(t\) computes hyperbolic distances \(d(t, j)\) to every \(j < t\) and picks \(m\) partners. At \(T = 0\) the picks are the \(m\) closest predecessors (deterministic). At \(T > 0\) the picks are an Efraimidis-Spirakis weighted draw from

where \(R_t\) is the temperature-dependent connection radius from the canonical PSO formula. Lower \(T\) concentrates picks on the closest predecessors (high cc); higher \(T\) flattens the distribution toward random (low cc).

Around the PSO build, stage 2 runs a 1-D bisection-and-secant search over \(T \in [t_\text{min}, t_\text{max}]\). Each iteration evaluates PSO at one \(T\), measures the cluster's induced global cc, and shrinks the bracket using the sign of \(c - \hat c(C)\). The walker below steps through every search iteration across every cluster; the chosen \(T\) per cluster is whichever evaluated PSO realisation came closest to \(\hat c(C)\).

PSO step 1. Sort nodes by profile degree; rank \(i\) fixes \(r_i = 2\log i\).

PSO step 2. The first \(m+1\) arrivals form \(K_{m+1}\), the durable base for the cluster.

PSO step 3. Every later arrival draws \(m\) older partners from PSO weights, then the realized cluster cc is measured against \(\hat c(C)\).

T-search step 1. Start at the initial candidate \(T\), then choose bisection or secant proposals inside the bracket. Each candidate runs the full cluster build at that \(T\) with the cluster's fixed rank order.

T-search step 2. Compute \(c - \hat c(C)\). The sign says which side of the bracket is too high or too low, and \([t_\text{min}, t_\text{max}]\) shrinks until error or step size is small enough.

T-search step 3. Keep the best evaluated realization even if the bracket stops early; the chosen stage-2 edge list is the one whose cc is closest to the target.

The proof is the same induction as the \(K_{k+1}\) pages. \(K_{m+1}\) has edge connectivity \(m\), adding a new vertex with \(m\) edges to an \(m\)-edge-connected graph keeps every cut at size at least \(m\), and \(m \ge k(C)\) makes the PSO interior satisfy the empirical mincut lower bound. The \(\min(\cdot, n-1)\) cap is harmless because no simple \(n\)-node cluster can have \(k(C) > n-1\).

Compute what the SBM still owes each block.

Stage 3 is unchanged from v2. Before the SBM call, prepare_sbm_inputs re-reads the original edgelist and rebuilds out_degs + probs on all four blocks (three real clusters + one combined outlier block). It subtracts the stage-2 PSO contribution from out_degs and populates probs inter-cells from the original edge list. Finally it reconciles each diagonal against the block's residual stub budget:

Step 1. Re-read all nodes. The stage switches from the profile's three real clusters to a four-block universe because outlier edges were excluded from stage 2 but still belong in the final graph. Every outlier is folded into one combined pseudo-block before probs is built.

Step 2. Subtract PSO first. Every stage-2 edge is charged against endpoint degrees and its diagonal block-pair budget; the residual SBM should sample only edges that are still owed. The PSO edge list is passed as exist_edgelist, the same handoff v2 used for its constructive core.

Step 3. Reconcile each block. The code compares remaining stub mass with inter-block commitments and sets probs[k,k] from \(\text{diff}_k\), using the same evenness and overspend fixes as v2 so gt.generate_sbm receives a consistent half-edge ledger.

\(D_k\) is "residual half-edges block \(k\) still owes", \(E^{\text{inter}}_k\) is "inter-block half-edges block \(k\) is already committed to". The intra-block budget the SBM still needs to sample is

If \(\text{diff}_k \ge 0\), set \(\texttt{probs}[k, k] = \text{diff}_k\) (bump by 1 if odd, to satisfy graph-tool's even-half-edges-per-block rule, and add the bump back to one node's out_degs). If \(\text{diff}_k < 0\), the construction already over-spent the block's out-budget; add \(|\text{diff}_k|\) back to out_degs and set \(\texttt{probs}[k, k] = 0\) (the SBM can only add, never subtract).

On the synthetic, after the live stage-2 PSO build, the residual looks like (numbers reflect whatever PSO realisation the search settled on; the diffs depend on each cluster's stage-2 spend):

Wherever a cluster's PSO build ended up placing more intra edges than the empirical count (a lower-T realisation will tend to do this), \(\text{diff}_k\) goes to zero and the over-spent stubs are added back to out_degs. The residual SBM still sees a proper bipartite-ish problem; v3 just hands it a different stage-2 budget than v2 would.

One SBM call. Block-preserving swaps repair invalid edges without losing the block count.

With the residual probs, out_degs, and the combined-outlier block assignment ready, v2 calls gt.generate_sbm(b, probs, out_degs, micro_ers=True, micro_degs=True) once. The sampler can still emit self-loops (two of a node's stubs pair together) and parallel edges (the same pair drawn twice). v1 dedupped both and accepted the degree loss. v2 tries to fix each one via a block-preserving 2-opt swap.

The swap: bucket every valid edge by its unordered block-pair \((A, B)\); for each invalid edge, pick a random valid edge in the same bucket and swap endpoints so each node stays in its home block. That preserves both the block-pair count and every node's block membership. Up to 10 retry passes with a stagnation detector. Edges still invalid after that are dropped with a WARN.

Step through; hit random to resample stage 3.

Block-aware top-up by default. Logs gridlock; does not silently drop.

After the residual SBM + rewire, some nodes may still be short of their target. v2 hands the leftovers to a block-aware top-up that spends edges out of a per-block-pair budget read from the reference clustering, rather than letting stubs leak across cluster boundaries. Anything still unplaced is logged, never silently dropped the way v1's plain greedy does. The viz below runs the simpler global sibling so the heap mechanics stay readable; see the degree matcher page for the full menu.

Toggle apply match_degree to watch the per-node deficit pile shrink. Click random for a different realization.

Same downstream stages, different stage-2 family.

v3's pipeline diverges from v2 only in stage 2 (and the matching profile artifact). Everything that follows — residual SBM, block-preserving rewire, block-aware degree matcher — is the same code under the same flags. What changes is the stage-2 budget v3 hands stage 3: PSO can place more or fewer intra-cluster edges than v2's \(K_{k+1}\) + greedy attach, depending on the chosen \(T\) and on each cluster's empirical cc target.

The cluster-level effect is that v3's intra-cluster triangle distribution tracks the input's, while v2's is fixed by \(k(C)\) alone. The block-pair-level effect on the residual-SBM is harder to read: v3 may underspend or overspend each diagonal relative to v2, and the resulting \(\text{diff}_k\) can flip sign per block. The downstream rewire + matcher then absorb whatever stage 2 left on the table.