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

[Arun]

Thank you, Tamas and Gabor for the answers and revised code.  I will
try implementing Gabor's (new) function in Python, since I am not
using R.

I was going to add a bug in launchpad for this so that future releases
might include support for generating Barabasi graphs without
multi-edges (since other users seem to have also encountered this
issue), but it appears there is already a bug report for it:

https://bugs.launchpad.net/igraph/+bug/409346

Thanks so much for the help.






On Wed, Dec 23, 2009 at 7:55 AM, Gábor Csárdi <address@hidden> wrote:
> I have no idea what I did one year ago with the cited code, but it is
> awfully wrong. Maybe I copy-pasted the wrong function. Anyway, here is
> how to do it properly:
>
> barabasi.game2 <- function(n, m) {
>
>  edges <- numeric()
>  deg <- rep(0, n)
>  for (i in 2:n) {
>   deg[i-1] <- 1
>   no.neis <- min(i-1, m)
>   neis <- rbind( i, sample(1:(i-1), no.neis, prob=deg[1:(i-1)]) )
>   edges <- c(edges, neis)
>   deg[neis] <- deg[neis]+1
>  }
>
>  graph(edges-1)
> }
>
> I hope this one is alright. Best,
> G.
>
> On Wed, Dec 23, 2009 at 2:39 PM, Tamas Nepusz <address@hidden> wrote:
>> 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:
> [...]
>>
>> 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
>>
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
>
>
> --
> Gabor Csardi <address@hidden>     UNIL DGM
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>