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

[Gábor Csárdi]

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