Module barabasi_psumtree 

Barabási–Albert preferential-attachment random graph — PSUMTREE variants (ALGO-GN-020).

Counterparts of the IGRAPH_BARABASI_PSUMTREE and IGRAPH_BARABASI_PSUMTREE_MULTIPLE branches of igraph_barabasi_game() in references/igraph/src/games/barabasi.c (igraph_i_barabasi_game_psumtree_multiple at lines ~166-294 and igraph_i_barabasi_game_psumtree at lines ~296-414).

Both variants attach m (or outseq[i]) outgoing edges from every new vertex i, choosing destinations weighted by attraction(deg(v)) = pow(deg(v), power) + A (with the C-style special case pow(0, 0) == 1). Sampling uses a Fenwick BIT (PsumTree) shared with crate::lastcit_game / crate::recent_degree_game for O(log n) point-set + binary-lifted prefix-search.

Variants

• barabasi_game_psumtree — simple variant. Each of the m draws temporarily zeros the chosen vertex’s weight in the BIT so that the same target cannot be picked twice within the same step. After the m draws complete, the weights of the chosen vertices are refreshed back to their proper attraction(deg(v)). No within-step multi-edges by construction. (Cross-step duplicates are impossible too because the source vertex is fresh each step, and the simple-graph guarantee is the contract.)

• barabasi_game_psumtree_multiple — multi-edge variant. The BIT prefix-sum is snapshotted once at the start of each step, and all m draws sample against the unchanged tree. The same target may therefore be drawn twice within one step, producing multi-edges. After all draws, the affected vertices’ weights are refreshed in batch.

Common parameters

• nodes — vertex count. nodes = 0 returns the empty graph.
• power — exponent in pow(deg, power). Negative values are permitted only when there are no zero-degree vertices being sampled (the upstream contract is that A > 0 rules that out — we forward the same rule).
• m — constant per-step out-degree, used when outseq = None.
• outseq — when provided, must have length nodes. The first entry is ignored (vertex 0 has no outgoing edges per the seed convention). For i ≥ 1, outseq[i] overrides m.
• outpref — when true the new vertex’s own out-degree counts toward its attraction (total-degree model). Forced to true when directed = false.
• a — constant attractiveness term added to every weight. When outpref = false, must be strictly positive so that zero-degree vertices have non-zero probability. When outpref = true, may be zero but must be non-negative.
• directed — emit directed edges (older → newer convention matches BAG variant).
• seed — initialises an internal SplitMix64; the output is deterministic for fixed parameters and seed.

Construction guarantees

• No self-loops by construction — the new vertex i is added to the BIT after its m outgoing draws complete.
• No cross-step multi-edges: source i is unique each step, so all duplicates can only land within a single step. The simple variant rules those out; the multiple variant allows them.
• Always-cite fallback: when m ≥ i, all i previously-added vertices are cited (deterministically), matching upstream’s no_of_neighbors >= i branch (multiple variant only — the simple variant cannot satisfy m ≥ i without running out of distinct targets, which the BIT-zeroing scheme also handles implicitly).
• Zero-sum fallback: when the BIT total is zero, the sample falls back to a uniform draw over [0, i). With outpref = true and A > 0, this branch only fires in the very first step (where the seed vertex’s weight is set to 1.0, so the sum is positive).

Cost

O(n · m · log n) for the BIT searches/updates; O(n + m·(n-1)) memory for the edge list. Compares favourably to the BAG variant’s O(n · m) for small m, and is asymptotically better than O(n²) naive cumulative-sum sampling.

Functions

barabasi_game_psumtree

PSUMTREE (simple) variant — no within-step multi-edges.

barabasi_game_psumtree_multiple

PSUMTREE_MULTIPLE variant — within-step multi-edges allowed.