Module hsbm 

Hierarchical Stochastic Block Model (ALGO-GN-011).

Counterparts of igraph_hsbm_game() and igraph_hsbm_list_game() from references/igraph/src/games/sbm.c:284-648. Both arrange n vertices into K macro-blocks. Each macro-block runs its own internal Stochastic Block Model over k_b micro-blocks; in addition every pair of macro-blocks is connected by a Bernoulli(p) sampler on the rectangular product of their vertex sets.

• hsbm_game — the uniform variant: every macro-block has the same size m, the same micro-block proportions rho, and the same internal preference matrix c. Requires n % m == 0 so the number of macro-blocks is exactly n / m.
• hsbm_list_game — the per-macro variant: each macro-block b carries its own size m_list[b], proportions rho_list[b], and preference matrix c_list[b]. The sizes must sum to n.

Both functions always produce an undirected, simple graph (no self-loops, no multi-edges) — matching the upstream C signatures, which fix directed=0 and do not expose a loops or multiple flag.

Algorithm

Each macro-block is sampled independently via the same Batagelj–Brandes geometric-skip path used by super::sbm, reused through crate::algorithms::games::sbm internals. The inter- macro layer adds, for every pair of macros, a single rectangular geometric-skip pass at rate p. Two fast paths:

• p == 1 emits the full bipartite edge set without consulting the RNG.
• p == 0 is skipped entirely.

Total cost is O(n + m + sum k_b² + K²) where m is the realised edge count and K is the number of macro-blocks.

Determinism

Given the same (args, seed) the output is bit-exact reproducible via the shared SplitMix64 PRNG.

References

• V. Batagelj and U. Brandes, “Efficient generation of large random networks”, Phys. Rev. E 71, 036113 (2005).
• Hierarchical-SBM literature, e.g. Lyzinski et al., “Community detection and classification in hierarchical stochastic blockmodels”, IEEE Trans. Net. Sci. Eng. 4 (2017), 13-26.

Functions

hsbm_game

Generate a graph from the uniform Hierarchical Stochastic Block Model: every macro-block is the same size m and shares the same internal preference matrix.

hsbm_list_game

Generate a graph from the per-macro Hierarchical Stochastic Block Model: every macro-block carries its own size, its own micro-block proportions, and its own internal preference matrix.