Skip to main content

Module recent_degree

rust_igraph::algorithms::games

Module recent_degree 

Source
Expand description

Recent-degree game (ALGO-GN-019).

Counterpart of igraph_recent_degree_game() from references/igraph/src/games/recent_degree.c:32-186. Models a growing network where the probability of citing a vertex is proportional to the number of edges it received in the last time_window time steps, raised to power, plus a zero_appeal floor for never-recently-cited vertices.

§Algorithm

Every vertex v carries a weight in a prefix-sum tree: weight[v] = degree[v]^power + zero_appeal where degree[v] is the count of edges in the sliding window that pointed at v (and originated from v, when outpref = true).

The window itself is maintained by a deque (history). Entries ordered by time of creation, with a sentinel value separating each step’s contributions. On step i:

  1. Expire (only when i >= time_window): pop entries from the front of history until a sentinel is popped. For each popped vertex j, decrement degree[j] and refresh psumtree[j].
  2. Draw m (or outseq[i]) citations, each via psumtree.search(uniform(0, sum)) — with a uniform fallback over [0, i) when sum == 0. For each citation (src=i, dst=to): bump degree[to], push to to history, record the edge.
  3. Push a sentinel to history.
  4. Refresh psumtree entries for each cited vertex with its new degree.
  5. If outpref: bump degree[i] += m and refresh psumtree[i]; otherwise psumtree[i] = zero_appeal.

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. The psumtree only ranges over vertices [0, i); vertex i is added after its outgoing edges are drawn.
  • Multi-edges: yes, when m ≥ 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.

§Validation

  • power and zero_appeal must be finite and non-NaN.
  • zero_appeal >= 0.
  • outseq (when present) must have length nodes.
  • The first entry of outseq is conventionally 0 (matching the C reference, which drops outseq[0] from the edge total — vertex 0 has no preceding vertices to cite).

§References

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

Functions§

recent_degree_game
Recent-degree game. See module docs.