Module barabasi_aging 

Barabási–Albert preferential-attachment with aging (ALGO-GN-021).

Counterpart of igraph_barabasi_aging_game() in references/igraph/src/games/barabasi.c (lines ~606-841).

Each step i ≥ 1 adds a fresh vertex and attaches m (or outseq[i]) outgoing edges. Targets are drawn from a Fenwick BIT (PsumTree) weighted by a product of a degree term and an age term:

weight(v) = (deg_coef · pow(deg(v), pa_exp) + zero_deg_appeal)
          · (age_coef · pow(age(v), aging_exp) + zero_age_appeal)

age(v) = (i − v) / binwidth + 1 where binwidth = nodes / aging_bins + 1 (the C special case is pow(0, 0) == 1, preserved here).

Mechanics

• Sampling: each of the m draws independently picks against the current BIT (the C source does NOT zero picks within a step, so within-step multi-edges are possible — matching upstream).
• Refresh chosen weights: after the m draws, every chosen vertex has its weight refreshed to the new degree.
• New-vertex weight: vertex i is inserted into the BIT with age 1 (the newest bin) and degree either 0 (if outpref = false) or no_of_neighbors (if outpref = true).
• Age sweep: for every k ≥ 1 such that k · binwidth ≤ i, the vertex at position i − k · binwidth has its weight refreshed with age k + 2 (it just crossed a bin boundary). This matches the C loop at lines 817-829.

Parameters

• nodes — vertex count.
• m — per-step out-degree when outseq is None.
• outseq — optional length-nodes vector of per-step out-degrees (the first entry is ignored, matching upstream).
• outpref — when true, the new vertex’s own emitted citations feed back into its degree at end-of-step (and therefore into its weight when it becomes a target in subsequent steps).
• pa_exp — preferential-attachment exponent on degree.
• aging_exp — aging exponent on age bin (usually negative — younger vertices are favoured).
• aging_bins — must be ≥ 1. Sets binwidth = nodes / aging_bins + 1.
• zero_deg_appeal — additive degree term so zero-degree vertices have non-zero weight. Must be non-negative.
• zero_age_appeal — additive age term so oldest vertices retain non-zero weight when aging_exp < 0. Must be non-negative.
• deg_coef — multiplicative degree coefficient. Must be non-negative.
• age_coef — multiplicative age coefficient. Must be non-negative.
• directed — emit directed edges (newer → older convention).
• seed — initialises an internal SplitMix64.

Construction guarantees

• No self-loops by construction — the new vertex i is added to the BIT after its m outgoing draws, and search_bounded(_, i) prevents binary-lifting from over-advancing to position i.
• Multi-edges allowed when m ≥ 2 — independent draws against the same snapshot of the BIT can collide. Matches upstream’s behaviour (no within-step zeroing).
• Zero-sum fallback: when the BIT total is zero, the draw falls back to a uniform sample over [0, i). This only fires at the start of the run when the seed vertex’s age has already pushed its weight to zero (e.g. aging_exp = -∞ is forbidden by validation, but aging_exp very negative + zero_age_appeal = 0 makes it possible).

Cost

O((n + n / aging_bins) · log n + |E|) — each step does O(m · log n) for the draws and refresh, plus an amortized O((n / aging_bins) · log n) for the age sweep across the run.

Notes on the C special case

attraction_aging in C uses dp = (pa_exp == 0.0) ? 1.0 : pow(deg, pa_exp) — i.e. pow(0, 0) == 1 is special-cased only for the degree term and only when the exponent is exactly zero. The age term always evaluates pow(age, aging_exp) directly (and since age ≥ 1 after the +1 shift, there is no pow(0, *) edge case for age).

Functions

barabasi_aging_game

Preferential attachment with vertex aging.