LFR

Fit shapes first; build a new graph second.

LFR is not a degree-sequence copier. It compresses the input into distribution parameters, draws a new synthetic instance, and then enforces the internal/external split implied by \(\mu\).

Step 1. Profile degrees without copying node identities. The wrapper keeps \(N\), \(\langle k\rangle\), \(k_{\max}\), and fitted \(t_1\) from degree.csv; small inputs make the power-law fit noisy, and output degrees are always a fresh sample.

Step 2. Profile community sizes under LFR's size floor. The fit keeps \(c_{\min} = \max(\min c, 3)\), \(c_{\max}\), and fitted \(t_2\); size-1/2 communities and singleton outliers cannot survive as generated communities.

Step 3. Compute \(\mu\) as the mean of node-level ratios \(d_i^{out}/d_i\). This is not ABCD's stub-weighted \(\xi\): leaves and hubs get equal votes.

Step 4. Draw a fresh benchmark instance from the fitted laws. Degree draws use inverse-CDF lookup, size draws run until their adjusted sum is \(N\), and a parity repair makes the degree sum pairable; IDs, exact degrees, and exact cluster sizes are intentionally not preserved.

Step 5. Reserve same-community and cross-community stubs before any edges exist. LFR stochastically rounds \(d_i^{int} \approx (1-\mu)d_i\) and sets \(d_i^{out}=d_i-d_i^{int}\), so low-degree nodes realise only coarse \(\mu_i\) ratios.

Step 6. Place nodes where their internal degree can fit. The assignment requires \(d_i^{int} \le c_q - 1\); independently sampled degrees and sizes can be incompatible, so the binary may resize and restart.

Step 7. Pair the legal stub bags: internal stubs inside each community, external stubs globally. Random pairings can create loops, parallels, and same-community external mates.

Step 8. Repair loops and duplicates by endpoint swaps that preserve degrees as much as possible. Irreparable collisions can still leave a small degree loss.

Step 9. Rewire mate edges so every external stub actually leaves its community. The operation swaps endpoints, not budgets, which is why final \(\mu_i\) values concentrate around \(\mu\) instead of matching it exactly node by node.

Shared input graph: 18 clustered + 2 singletons.

The 20-node synthetic LFR profiles to derive its scalars: C1 (8), C2 (6), C3 (4), plus outliers 19 + 20 each in their own 1-node cluster. Under the wrapper's outlier_mode=singleton, the cluster-size list reads [8, 6, 4, 1, 1]; the size-1 entries are below LFR's hard \(c_{\min} = 3\) floor and will not survive the resample.

Extract the shape; throw away the identity.

Profile writes degree.csv (per-node integer degrees) the same way ABCD does, but LFR's stage 2 reads only four derived scalars from it: \(N\), \(\langle k \rangle\), \(k_{\max}\), and the power-law exponent \(t_1\) from powerlaw.Fit with auto-selected \(x_{\min}\). The sequence itself is discarded.

On the synthetic the fit is coarse because only 20 points feed it; the curve below shows the degree histogram and the fitted \(k^{-t_1}\) line. On dnc the fit lands at \(t_1 \approx 1.45\) with auto \(x_{\min} = 1\), which is a poor fit by the strict-KS test but the best the powerlaw package can do.

What survives is the empirical scale and tail profile: \(N\), \(\langle k\rangle\), \(k_{\max}\), and \(t_1\). What disappears is identity. Node IDs and their original degrees are not carried forward, so a high-degree input vertex does not become a specific high-degree output vertex; the sampler reconstructs a new sorted sequence from the fitted law.

A second power law, with a size floor.

Profile writes cluster_sizes.csv the same way ABCD does. Stage 2 derives \(c_{\min}, c_{\max}\), and the exponent \(t_2\) fitted with xmin = max(min(cluster_sizes), 3). The floor of 3 is a hard LFR requirement: the C++ binary refuses to build clusters smaller than 3. If the input has size-1 or size-2 clusters (such as the wrapper's singleton outliers), the floor absorbs them; the fitted exponent is estimated only from sizes \(\ge 3\).

On the synthetic: cluster_sizes = [8, 6, 4, 1, 1] → \(c_{\min} = 3\) (floor applies), \(c_{\max} = 8\), \(t_2 \approx 2.23\). On dnc: 374 entries, 309 of them singletons → \(c_{\min} = 3\), \(c_{\max} = 78\), \(t_2 \approx 1.72\).

The generator keeps only a distributional profile: \(c_{\min}\), \(c_{\max}\), and \(t_2\), with \(c_{\min}\) clipped to 3. A community of size 1 or 2 cannot host many internal stubs, so LFR refuses to generate it; stage 2 ignores those below-floor sizes and draws new sizes until their adjusted total is exactly \(N\).

One number: \(\mu\) (node-mean, not stub-weighted).

LFR writes mixing_parameter.txt, a single float. Unlike ABCD's stub-weighted \(\xi\), LFR uses the mean of per-node ratios:

Each node contributes equally regardless of degree. A degree-1 node with one inter-cluster edge contributes \(1/1 = 1\); a degree-1000 hub with 500 inter-cluster edges contributes \(500/1000 = 0.5\). On skewed degrees the two conventions drift by a few percent. On dnc LFR's \(\mu = 0.622\) while ABCD's \(\xi = 0.718\); they are close but not equal.

Draw fresh sequences from the fitted power laws.

The C++ binary samples a new degree sequence from \(P(k) \propto k^{-t_1}\) truncated to \([d_{\min}, k_{\max}]\), where \(d_{\min}\) is chosen by a bisection (solve_dmin + integer-average parity) so the distribution's mean lands at \(\langle k \rangle\) in expectation. It then draws \(N\) degrees in one pass via inverse-CDF lookup (no rejection loop), sorts them, and decrements the single largest if the total is odd so the configuration model can close. Cluster sizes come from a second power law \(P(c) \propto c^{-t_2}\) with floor \(c_{\min}\); they are drawn until they sum past \(N\), then the smallest entry absorbs the remainder so the total is exactly \(N\). The upper cap \(c_{\max}\) only bounds the sampler's range and is best-effort: when the fitted exponent is poor, output sizes can drift above \(c_{\max}\). Both samples differ from the input.

Press re-roll sequences to draw a new pair. The bars below overlay input (azure) vs resampled (plum) for each rank position. On the synthetic the resampled degree sequence tends to have a flatter tail: with only 20 points, the single-pass sampler rarely reproduces the input's heavy hubs.

Step 1. Solve \(d_{\min}\), build the truncated CDF once, and use lower-bound lookup for each random degree draw. Step 2. If the sampled degree sum is odd, decrement the largest degree by one so stubs can be paired. Step 3. Draw community sizes from \(c^{-t_2}\), then adjust the smallest entry so the sizes sum to exactly \(N\).

Convert the target \(\mu\) into integer stub counts.

After resampling degrees, LFR decides each node's internal budget before it knows the final edge set. For node \(i\), the target is \(d_i^{int} \approx (1-\mu)d_i\); a stochastic rounding step handles fractional values, and the external budget is whatever remains. This is why the final \(\mu_i\) distribution is spread around \(\mu\): integer stubs are coarse, especially on low-degree nodes.

The split turns each degree into two coloured piles: internal stubs reserved for same-community edges and external stubs reserved for cross-community edges. Assignment and rewiring both need those counts fixed; later swaps can move endpoints, but they cannot change a node's total internal/external budget. In code, sampleInternalDegrees rounds \((1-\mu)d_i\), then balances excess or defect so the requested split is feasible.

Iterate until no homeless node remains.

The paper's step 4: walk the degree sequence and place each node in a random community whose remaining slot count exceeds the node's internal degree \(d^{\text{int}} = (1-\mu) d\). If the binary fails to place a node within \(3N\) retries, it calls change_community_size to reshuffle the cluster-size sequence and restarts the assignment from scratch. Most realistic parameter settings converge on the first attempt.

Step through the iterations below. Home position is random each time; re-roll draws a new permutation.

A node assigned to community \(q\) must satisfy \(d_i^{int} \le c_q - 1\); otherwise it asks for more internal neighbours than exist. Degree and size sequences are sampled independently, so a hub can be too large for the first sampled community layout. The binary handles that by building a node-community bipartite assignment, running swap passes, and remapping nodes by degree feasibility.

Configuration model to seed, targeted rewire to match \(\mu_i\).

With assignment fixed, the binary builds the edge set in two halves: a per-cluster configuration model on the internal-degree sub-sequence in each cluster, then a cross-cluster configuration model on the leftover external stubs. The external config model is blind to cluster membership, so some external edges land between two nodes of the same cluster (a "mate" edge). After the seed, a mate-rewire phase walks every such edge and swaps an endpoint with a random outside node, so the external edge truly leaves the cluster while each node keeps its pre-set internal/external split. Every swap preserves node degrees, only re-pairing endpoints.

The walker below decomposes the seed phase: each step pairs two stubs uniformly at random; collisions (self-loops, parallels) flag red-dashed and feed a 2-opt cleanup pass that swaps endpoints with a random valid edge. Highlighted nodes mark the up to 4 endpoints touched by each swap; everything else dims. The distribution of \(\mu_i\) at the end is bell-shaped around \(\mu\), not a delta: small-degree nodes have few possible ratios (degree-1 only 0 or 1; degree-2 only 0, 0.5, 1) so they cluster at discrete points. The bars below the walker plot the \(\mu_i\) distribution from a finalised sample; the slider moves the target \(\mu\), re-roll resamples the edge generation.

Step 1. Randomly pair stubs while keeping each node's sampled degree budget fixed; internal and external stubs are paired in different bags. Step 2. Repair self-loops and parallel edges with endpoint swaps that preserve degrees. Step 3. When an external pair accidentally stays inside one community, the mate pass swaps one endpoint outward while preserving every node's split.

Before the mate-rewire kicks in, each cluster runs its own configuration-model build via buildSubgraph: a deterministic multimap seed places intra-cluster edges first, then 10 randomization passes 4-way-swap the local adjacency, and finally a multi-edge rewire breaks any duplicates that surface when each cluster is merged into the global edge set. The walker below steps through every Phase-2 swap and every Phase-3 multi-edge rewire across all clusters in cluster order. Each step boldfaces the up to 4 endpoints touched, dims everything else, then animates the cut + place.

Step 1. Place a simple internal scaffold inside each community using the assigned nodes and their internal-degree targets. Step 2. Randomize the local adjacency by cutting two internal edges and placing two replacement edges that keep degrees unchanged. Step 3. When duplicate internal edges appear after merging clusters into the global set, repair them with another degree-preserving swap.

The mate-rewire phase is what turns LFR's μ from a target into the bell-shaped distribution above. After per-cluster internal edges are placed, the binary builds a global external-edge config model and runs a phase-3 loop: for any same-cluster external edge, pick a random outside node, do a 4-way swap that pulls one endpoint out of the cluster. The walker below steps op-by-op through that loop on the current sample. Per-cluster internal edges render as faded backdrop; mate edges still inside a cluster surface red-dashed; each step ghost-flashes the cuts before settling on the placements.

Step 1. Scan the external-edge set for a pair whose endpoints are assigned to the same community; that pair is a mate violation. Step 2. Cut the bad external edge and one other external edge, then reconnect crosswise through an outside endpoint. Step 3. Keep the budgets fixed: the operation changes edge partners, not degrees or internal/external counts.

What you get on the shipped example.

Default run on dnc + sbm-flat-best+cc at --seed 1 (\(N = 906\), \(\langle k \rangle = 23.02\), \(t_1 = 1.45\), \(t_2 = 1.72\), \(c_{\min} = 3\), \(c_{\max} = 78\), \(\mu = 0.622\)):