Module establishment 

Establishment / sample-traits game (ALGO-GN-015).

Counterpart of igraph_establishment_game() from references/igraph/src/games/establishment.c:57. Models a growing graph with vertex types: a single vertex is added at each step and tries to connect to k already-present vertices, with each candidate edge accepted independently with probability pref_matrix[type_new][type_old].

Algorithm

1. Build a cumulative distribution from type_dist (or the uniform [1, 1, …, 1] distribution when type_dist == None).
2. Assign every vertex v ∈ [0, nodes) a type by drawing a uniform sample in [0, total) and binary-searching the cumulative table.
3. For each v ∈ [k, nodes), draw k distinct previous vertices [0, v) via Floyd’s distinct-sample. For each picked neighbour u, accept the edge (v, u) with probability pref_matrix[type[v]][type[u]] using a single uniform draw.

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, support of the preference matrix) rather than bit-exact.

References

• G. Caldarelli, A. Capocci, P. De Los Rios, and M. A. Muñoz, “Scale-free networks from varying vertex intrinsic fitness”, Phys. Rev. Lett. 89, 258702 (2002).

Functions

establishment_game

Generates a random graph with vertex types via the establishment model.