Re: [igraph] how to properly generate a barabasi graph in Python without multi-edges

[Tamas Nepusz]

So, here's the problem. In every step during the generation process, we have to 
do a weighted sampling without replacement -- each existing node is weighted by 
its degree plus one, and we have to ensure that no node appears twice in the 
result while still obeying the prescribed probability distribution. I'm not 
sure how to do that correctly (if it is possible to do it correctly). Suppose 
you have three nodes, the first having an in-degree of 2, the second having an 
in-degree of 1, the third having zero in-degree. (This can happen after the 
first two steps with m = 2). The corresponding probability distribution from 
which we are sampling is then as follows:

[1/2, 1/3, 1/6]

Suppose we are adding a new node that must connect to two of the existing ones. 
Thus, we have the following three possibilities to choose from:

selecting node 1 and node 2
selecting node 2 and node 3
selecting node 1 and node 3

Suppose p12 is the probability of selecting node 1 and node 2, p23 is the 
probability of selecting node 2 and 3, p13 is the probability of selecting node 
1 and node 3. The probability of selecting node 1 among the two is then equal 
to p12+p23 and so on. We know that p12 + p13 = 1/2, p12 + p23 = 1/3, p13 + p23 
= 1/6, p12 + p13 + p23 = 1, and each probability is between zero and one. Now, 
the problem is that there is no solution for this equation system, so you 
cannot satisfy the prescribed probability distribution if you are sampling 
without replacement. So, in general, you cannot sample without replacement if 
you prescribe the probability of each element appearing in the final result.

(Note: I googled for "weighted sampling without replacement", but it appears 
that this is something different: the weights describe the probability 
distribution of drawing the first element from the set, and the probabilities 
are recalculated every time an element is drawn: the remaining probabilities 
are rescaled to sum up to 1 again).

Therefore, I guess your best bet is to generate a BA graph is still by using 
igraph's built-in generator and then simplifying the graph.

-- 
Tamas