Module callaway_traits 

Callaway-Hopcroft-Kleinberg-Newman-Strogatz traits game (ALGO-GN-016).

Counterpart of igraph_callaway_traits_game() from references/igraph/src/games/callaway_traits.c:71. Models a growing graph with vertex types: at each step a new vertex is added, then edges_per_step candidate edges are generated by picking two uniformly random vertices from those already added (including the new one) and accepting the edge with probability pref_matrix[type1][type2].

Algorithm

1. Build a cumulative distribution from type_dist (or the uniform distribution when type_dist == None). Reject if maxcum <= 0.
2. Pre-assign every vertex v ∈ [0, nodes) a categorical type by drawing a uniform sample in [0, maxcum) and binary-searching the cumulative table.
3. For each step i ∈ [1, nodes) and each _ ∈ [0, edges_per_step), draw node1, node2 uniformly in [0, i] (inclusive — both can equal i, the just-added vertex). Accept the candidate edge (node1, node2) with probability pref_matrix[type[node1]][type[node2]].

Self-loops & multi-edges

Unlike establishment_game, this generator can return self-loops (node1 == node2) and parallel edges (the same (node1, node2) pair drawn twice). The output is therefore not simple by construction.

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

• D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman, and S. H. Strogatz, “Are randomly grown graphs really random?”, Phys. Rev. E 64, 041902 (2001).

Functions

callaway_traits_game

Generates a random graph with vertex types via the Callaway et al. (2001) growing model.