[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Randomizing graph while maintaining some properties
From: |
Gábor Csárdi |
Subject: |
Re: [igraph] Randomizing graph while maintaining some properties |
Date: |
Mon, 13 Jul 2009 21:21:00 +0200 |
Hi Steve,
for keeping the degree distribution see ?degree.sequence.game,
especially with method="vl". This is a "good way", in the sense that
it is a uniform sampler, but it always generates connected graphs and
works only for undirected ones.
Best,
Gabor
On Mon, Jul 13, 2009 at 8:42 PM, Steve Lianoglou<address@hidden> wrote:
> Hi all,
>
> I was curious if there was a good way to randomize an input graph
> while keeping some things constant (like degree distro on edges, for
> one).
>
> I wrote a naive/convoluted method that I'm using to attempt to do this
> on undirected graphs (pasted below), but it really fails to do it
> properly, though I guess it's ok for my requirements. Is there a
> better way to go?
>
> Thanks,
> -steve
>
> graph.randomize.edges <- function(graph, attr=NULL, do.test=TRUE) {
> # Randomizes the connections in the graph keeping the same degree/
> node
> #
> # NOTE: All graph attributes will be stripped, it's your job to use
> # the *.annotate.* functions to put the ones back that you
> want.
> warning(paste("This method doesn't keep the exact degree
> distributions",
> "as the original graph, even though it's trying to!"))
> mode <- ifelse(is.directed(graph), 'directed', 'upper')
> adj <- get.adjacency(graph, attr=attr)
> new.adj <- matrix(0, nrow(adj), ncol(adj), dimnames=dimnames(adj))
> degrees <- rowSums(adj)
>
> if (mode == 'directed') {
> for (i in 1:nrow(adj)) {
> new.adj[i,] <- sample(adj[i,])
> }
> } else {
> weights <- adj[upper.tri(adj, diag=TRUE)] # Use the same weights
> from old
> weights <- weights[weights != 0] # graph on new random
> edges
> so.far <- 0
> idxs <- upper.tri(adj, diag=TRUE)
> for (i in 1:nrow(adj)) {
> if (so.far >= length(weights)) {
> break
> }
> already.connected <- which(new.adj[,i] != 0)
> n.to.put <- degrees[i] - length(already.connected)
> # cat("[", i, "]: ", n.to.put, '\n', sep='')
> if (n.to.put > 0) {
> take.start <- so.far + 1
> take.weights <- weights[take.start:(take.start + n.to.put -
> 1)]
> so.far <- so.far + length(take.weights)
> n.zeros <- ncol(adj) - (i-1) - length(take.weights)
> edge.weights <- sample(c(take.weights, rep(0, n.zeros)))
> if (any(is.na(edge.weights))) {
> # oversampled the edges, the loop will break in the next
> iter
> warning("NA/NA/NA")
> }
> new.adj[i,i:ncol(adj)] <- edge.weights
> }
> }
> new.adj[is.na(new.adj)] <- 0 # correction for
> oversampling
>
> d <- diag(new.adj)
> new.adj <- new.adj + t(new.adj)
> diag(new.adj) <- d
> }
>
> g.rand <- graph.adjacency(new.adj, mode=mode, weighted=TRUE)
>
> if (do.test) {
> # Checks that graph has same number of edges
> n.edges <- sum(degree(graph)) == sum(degree(g.rand))
> if (!n.edges) {
> warning("Not the same number of edges")
> }
>
> eq <- all(degree(graph) == degree(g.rand))
> if (!all(eq)) {
> warning("Degrees for each node don't match")
> }
>
> # Check for broken pieces
> if (no.clusters(graph) != no.clusters(g.rand)) {
> warning("Number of pieces in graphs don't match!")
> }
> }
>
> g.rand
> }
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
--
Gabor Csardi <address@hidden> UNIL DGM