Module sbm 

Stochastic Block Model (ALGO-GN-010).

Counterpart of igraph_sbm_game() from references/igraph/src/games/sbm.c:78 — the canonical community-aware generalisation of Erdős–Rényi G(n,p).

Given a k × k preference matrix P and a k-vector of block_sizes summing to n, every pair (u, v) is connected independently with probability P[block(u)][block(v)] (or, in multigraph mode, with Pascal-distributed multiplicity of mean P[..][..]). The vertex order is determined by block_sizes: the first block_sizes[0] vertices form block 0, the next block_sizes[1] form block 1, and so on.

Each block-pair is sampled independently with Batagelj–Brandes geometric skip over the local pair-index space; total cost is O(n + m + k²) where m is the realised edge count and k is the block count.

Scope

Ports the full igraph_sbm_game surface:

• directed: directed vs undirected graph. When false, P must be symmetric.
• loops: when true, self-loops are allowed within blocks.
• multiple: when true, pref-matrix entries are expected edge multiplicities (each pair may receive multiple edges following a geometric distribution); when false, entries are connection probabilities in [0, 1].

The hierarchical variants igraph_hsbm_game and igraph_hsbm_list_game are deferred to a follow-up AWU.

Determinism

The output is fully reproducible given (pref_matrix, block_sizes, directed, loops, multiple, seed) via the shared SplitMix64 PRNG.

References

• K. Faust and S. Wasserman, “Blockmodels: Interpretation and evaluation”, Social Networks 14 (1992), 5-61.
• V. Batagelj and U. Brandes, “Efficient generation of large random networks”, Phys. Rev. E 71, 036113 (2005) — the geometric-skip sampler reused for each block-pair.

Functions

sbm_game

Generate a random graph from the Stochastic Block Model.