Skip to main content

Module preference

rust_igraph::algorithms::games

Module preference 

Source
Expand description

Preference-based block model (ALGO-GN-014).

Counterparts of igraph_preference_game() and igraph_asymmetric_preference_game() from references/igraph/src/games/preference.c:83 and references/igraph/src/games/preference.c:381.

The symmetric variant is essentially the non-growing version of the establishment game / a stochastic block model with a randomly assigned per-vertex type:

  1. Each vertex draws a type from the categorical distribution type_dist, or — when fixed_sizes = true — gets pinned to a deterministic block-by-position assignment.
  2. Per type-pair (i, j), edges are sampled with probability pref_matrix[i][j] over the rectangular |V_i| × |V_j| (or triangular) slot space using Batagelj–Brandes geometric skip, then mapped back to global vertex IDs through vids_by_type.

The asymmetric variant gives every vertex an (out_type, in_type) pair drawn jointly from type_dist_matrix. Sampling is per (out_type i, in_type j) cell of the connection matrix; with loops = false the sampler subtracts the count of vertices that appear in both vids_by_outtype[i] and vids_by_intype[j] from the local maxedges, then uses an end-corner remap to reroute any sampled diagonal slot to a unique non-loop slot.

Both variants share PairShape::decode and the geometric-skip pattern with the SBM module (crate::algorithms::games::sbm); the only addition is the indirection through vids_by_type (since same-type vertices are not contiguous in vertex-id space) and the intersection-based loop handling for the asymmetric path.

§Determinism

Reproducible given the inputs and seed against the shared SplitMix64 PRNG. The stream is not portable to upstream igraph’s GLIBC RNG, so conformance assertions are structural (vertex/edge counts, type-vector range, loops respect, pref-matrix support) rather than bit-exact.

§References

  • 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.
  • K. Faust and S. Wasserman, “Blockmodels: Interpretation and evaluation”, Social Networks 14 (1992), 5–61.

Functions§

asymmetric_preference_game
Generate a random directed graph with asymmetric vertex types and connection preferences.
preference_game
Generate a random graph from a type-aware preference (block) model.