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