Module chung_lu 

Chung–Lu expected-degree random graph generator (ALGO-GN-012).

Counterpart of igraph_chung_lu_game() from references/igraph/src/games/chung_lu.c:193.

Given a per-vertex weight vector w (and, in the directed case, a separate in-weight vector with the same total mass), every pair (i, j) is connected independently with probability p_ij depending on the chosen variant. All three variants share the “expected-degree base form” q_ij = w_i · w_j / S where S = Σ w_k.

Variants

• ChungLuVariant::Original — p_ij = min(q_ij, 1). The original Chung–Lu (2002) construction. When q_ij > 1 a single warning is emitted (via tracing-style eprintln! if the verbose-warnings feature ever lands; today the variant is silently clamped) and the pair is still sampled — but in that regime expected degrees no longer match the input weights.
• ChungLuVariant::Maxent — p_ij = q_ij / (1 + q_ij). The “generalised random graph” / maximum-entropy model with fixed expected degrees (Park & Newman 2004, Britton–Deijfen–Martin-Löf 2006).
• ChungLuVariant::Nr — p_ij = 1 - exp(-q_ij). The simple-graph projection of Norros & Reittu’s (2006) conditionally Poissonian multigraph model.

All three are equivalent in the sparse-graph limit q_ij → 0.

Algorithm

Implements the Miller–Hagberg (2011) O(|V| + |E|) sampler used by upstream igraph. The vertices are sorted by in-weight descending to obtain a permutation idx, then for each origin i:

1. Walk the target index j (starting at 0 for directed, at i for undirected).
2. Maintain a running upper-bound probability p (starts at 1). Draw gap ~ Geom(p) and skip past it; the geometric skip is the same primitive used by the Batagelj–Brandes ER samplers.
3. Compute the true probability q for the pair, accept the edge with probability q / p, then set p ← q.
4. Because the sort is descending and w_i is fixed, q is monotonically non-increasing as j grows, so q / p ≤ 1.

The geometric-skip + accept/reject combination is mathematically identical to Bernoulli sampling each pair independently with the variant-specific probability, but only the accepted edges incur work.

Determinism

Reproducible given (out_weights, in_weights, loops, variant, seed) against the shared SplitMix64 PRNG.

References

• Chung F, Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125–145 (2002).
• Miller JC, Hagberg A: Efficient generation of networks with given expected degrees (2011).
• Park J, Newman MEJ: Statistical mechanics of networks. Phys. Rev. E 70, 066117 (2004).
• Norros I, Reittu H: On a conditionally Poissonian graph process. Adv. Appl. Probab. 38, 59–75 (2006).

Enums

ChungLuVariant

Variant of the Chung–Lu connection-probability formula.

Functions

chung_lu_game

Sample a random graph from the Chung–Lu expected-degree model.