Module static_fitness 

Static-fitness random graph generator (ALGO-GN-013).

Counterpart of igraph_static_fitness_game() from references/igraph/src/games/static_fitness.c:110 and the power-law shaping convenience igraph_static_power_law_game() from line 387 of the same file.

The model (Goh–Kahng–Kim 2001) starts from n disconnected vertices, each carrying a non-negative fitness value. For each of the m desired edges:

1. Sample the source vertex i with probability proportional to fitness_out[i] (cumulative-sum + binary search).
2. Sample the target vertex j with probability proportional to fitness_in[j] (or fitness_out[j] when undirected).
3. Skip if it is a self-loop and loops = false. Skip and retry if the edge already exists and multiple = false. Otherwise commit.

The “no-multi” mode uses a per-source HashSet of accepted neighbours to detect duplicates in O(1) amortised — upstream uses per-vertex sorted vectors, which gives O(log d_i) lookups; both choices land at the same asymptotic O(|V| + |E| log |E|) overall.

Two public entry points

• static_fitness_game — the primitive: caller supplies the per-vertex fitness vector(s) directly.
• static_power_law_game — convenience that builds power-law fitness vectors i^α (with optional Cho et al. finite-size correction) and forwards to static_fitness_game.

Difference from Chung–Lu (ALGO-GN-012)

Chung–Lu fixes the expected degree of every vertex but the realised edge count fluctuates with the variant. Here we instead fix the edge count exactly at m and only the shape of the degree distribution is controlled by the fitness vector. The two samplers are also algorithmically distinct: Chung–Lu uses Miller–Hagberg geometric skip, this one uses cumulative-sum + binsearch.

Determinism

Reproducible given the inputs and seed against the shared SplitMix64 PRNG. The stream is not portable to upstream igraph’s GLIBC-style RNG, so conformance assertions are structural (vertex/edge counts, validation rules, expected degree-fitness correlation) rather than bit-exact.

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys. Rev. Lett. 87(27):278701 (2001).
• Chung F, Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125–145 (2002).
• Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys. Rev. Lett. 103:135702 (2009).

Functions

static_fitness_game

Sample a random graph from the static-fitness model (Goh–Kahng–Kim 2001).

static_power_law_game

Sample a random graph whose degree distribution follows a power law of prescribed exponent(s) (Goh et al. 2001).