Module lastcit 

Last-citation game (ALGO-GN-018).

Counterpart of igraph_lastcit_game() from references/igraph/src/games/citations.c:91-209. Models an evolving citation network where a vertex’s attractivity decays with the time elapsed since its last citation, binned into agebins age buckets.

Algorithm

Time is measured by vertex arrival; binwidth = nodes / agebins + 1. Every vertex v carries a weight in a prefix-sum tree:

1. Vertex 0 enters with the “never-cited” weight preference[agebins].
2. For each step i ∈ [1, nodes):
   • For each of edges_per_node outgoing edges, draw u ∈ [0, sum) uniformly and psumtree.search(u) returns the cited vertex to. Record lastcit[to] = i + 1, bump to’s weight to preference[0] (just-cited bucket).
   • When sum == 0 (no positive weight anywhere — only possible if preference[agebins] and all preference[..agebins] happen to be zero, but the validator already rejects that), the C reference falls back to RNG_INTEGER(0, i-1); we mirror it.
   • Insert vertex i with weight preference[agebins].
   • Age sweep: for each k ≥ 1 such that shnode = i - k·binwidth ≥ 1, walk shnode’s emitted citations and, for every cited vertex c whose lastcit[c] == shnode + 1 (i.e. its last citation really was at shnode), demote its weight to preference[k].

The structure is a binary-indexed (Fenwick) tree with binary-lifting prefix-search, giving O(log n) per update / search.

Self-loops & multi-edges

• Self-loops: impossible. psumtree.search and the sum=0 fallback both operate over the [0, i) index range; vertex i is added after its outgoing edges are drawn, so it cannot be picked.
• Multi-edges: yes, when edges_per_node ≥ 2. Two draws at the same step can land on the same target. Caller should simplify() if simple output is required (matches upstream behaviour).

Determinism

Reproducible against the shared SplitMix64 PRNG. Not bit-portable to upstream igraph’s GLIBC RNG; conformance asserts structural invariants only.

References

• Upstream igraph C igraph_lastcit_game, MIT-licensed reference port.

Functions

lastcit_game

Last-citation citation-network game. See module docs.