Module barabasi 

Barabási–Albert preferential-attachment random graph (ALGO-GN-002, BAG variant).

Counterpart of the IGRAPH_BARABASI_BAG branch of igraph_barabasi_game() in references/igraph/src/games/barabasi.c:67-178.

The “bag” mechanism (Newman 2003, originally implemented by Albert and Barabási themselves) maintains a multiset whose multiplicity of vertex v equals deg(v) + 1. Drawing a vertex uniformly from the bag therefore yields a vertex proportional to its degree — the preferential-attachment kernel of the classical BA model with power = 1 and constant attractiveness A = 1.

Algorithm:

1. Initial bag = [0] (vertex 0 is the seed).
2. For each new vertex i = 1 .. n:
   • Draw m neighbours from the bag uniformly with replacement.
   • Emit (i, to) for each neighbour.
   • Push i onto the bag once (so the new vertex itself is sample-able next round).
   • Push each chosen neighbour back onto the bag (their degree just went up by one).
   • If outpref, also push m copies of i (so the new vertex’s out-degree also drives future sampling).

Because draws are with replacement, two of the m neighbours of a given vertex can collide → the BAG variant can produce multi-edges and (when i itself is in the bag at sampling time, only possible with outpref=true) self-loops. Use the PSUMTREE variant (crate::erdos_renyi_gnp is not a substitute) once that AWU lands if a simple graph is required.

Total cost: O(n · m) work, O(n · m) memory for the bag and edge list.

Scope

MVP scope only covers the most-used dispatch path:

• power = 1, A = 1 (hardcoded — the BAG model only supports these per upstream barabasi.c:567-574).
• m is constant across all new vertices (no outseq).
• No start_from graph — we always seed with the singleton [0].
• outpref defaults to false for directed graphs, and is forced to true for undirected graphs (matching upstream barabasi.c:83-85).

Functions

barabasi_game_bag

Generate a graph with n vertices via Barabási–Albert preferential attachment, using the original “bag” mechanism (BAG variant).