[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] how to properly generate a barabasi graph in Python without
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] how to properly generate a barabasi graph in Python without multi-edges |
Date: |
Wed, 23 Dec 2009 13:39:00 +0000 |
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