Hey all,

I would like to build a custom random graph model for which I would like to use the partial sum trees provided by igraph to draw from a discrete probability distribution (in the same way it is used for i.e. the barabasi aging model).

Now, I am not an expert in partial sum trees and so I have one question about the way it works. The documentation says:

Each leaf contains the probability corresponding to the items. […]

Samples can be drawn from the probability distribution represented by

the tree by generating a uniform random number between 0 (inclusive) and the

value of the root of the tree (exclusive), and then following the branches

of the tree as follows. In each step, the value in the current node is

compared with the generated number. If the value in the node is larger,

the left branch of the tree is taken; otherwise the generated number is

decreased by the value in the node and the right branch of the tree is

taken, until a leaf node is reached.

Note that the sampling process works only if all the values in the tree

are non-negative. This is enforced by the object; in particular, trying to

set a negative value for an item will produce an igraph error.

I understand that negative values are a problem. But what will happen if I draw a uniform random number that is zero and I have a vertex that I want to choose with probability zero but not all vertices have probability zero? From my understanding, the search will start in the root and continually go down the left path until it reaches a leaf, which would then be my vertex with probability zero.

Most likely my understanding is incorrect, but what am I missing? If I am not missing anything, what steps do I need to take to ensure that probability-zero-vertices can not be chosen? (The vertices in my model might decrease in being-chosen-probability, down to zero).

Thank you for your help!