[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 withou

From: Gábor Csárdi
Subject: Re: [igraph] how to properly generate a barabasi graph in Python without multi-edges
Date: Wed, 23 Dec 2009 14:55:52 +0100

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


I hope this one is alright. Best,

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]