Have you looked at the documentation in `psumtree.c`

? Most of is it actually included in the HTML documentation of the C library, and describes the key part of the method.

https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph-Partial-prefix-sum-trees

Ultimately, it is important to distinguish between *what* the function produces, and *how* it does it. One only needs to understand what it does in order to use it.

**What does it do?**

New vertices are added to the graph in discrete steps. In each step, we assign a weight w_i = (d_i+A)^\beta to each existing vertex i. d_i denotes its degree. We select m existing vertices according to probabilities proportional to the weights, p_i = w_i / \sum_i w_i, and connect the new vertex to them.

There are variations on the generation procedure depending on how d is interpreted (in-degee or total degree) and whether parallel edges are allowed (sampling m vertices with or without replacement).

**How does it work?**

To implement this, we simply need a method to sample from discrete distributions. There are many such methods, not all equally efficient. Notice that here the distribution changes in each step. Thus we need an algorithm that can (1) generate samples efficiently, but also (2) update the distribution efficiently. The data structure whose description I linked to provides this. Please check the description and let me know if it is insufficiently clear.

Thereās one more trick to be mentioned: In order to select m *distinct* vertices, we can first select one, then set its probability (actually: weight) to zero before selecting the next. And so on, until m have been selected.

In comparison, the ābagā method only works for integer weights w and does not support sampling without replacement.

I donāt know if this method is published anywhere. It seems too simple to warrant publication. Effectively, we have a binary search tree where each node is annotated with the total weight of its subtree. To perform sampling, you descend from the root, choosing the left or right child node randomly, with probabilities proportional to their weights.