Re: [igraph] i can't find it, but there must be an easy was to reduce a graph

[Yannick Rochat]

Dear Tamas and all,

I'm pleased to read that you've already been thinking of this. Following your advice, I've written an horrible function that works and uses the 'weighted' option from graph.adjacency. You can see the result on a ~1000 nodes graph. And the code just below. Thank you for your answer.

Best,

Yannick


ebc <- edge.betweenness.community(g)
adj <- get.adjacency(g)

mods <- sapply(0:ecount(g), function(i) {                   # Gábor's code
g2 <- delete.edges(g, ebc$removed.edges[seq(length=i)])
cl <- clusters(g2)$membership
modularity(g, cl)
})

g2 <- delete.edges(g, ebc$removed.edges[1:(which.max(mods)-1)])
V(g)$clus <- clusters(g2)$membership

adj2 <- matrix(ncol=max(V(g)$clus+1),nrow=max(V(g)$clus+1)) # Adjacency matrix of the reduced graph
for (i in 1:max(V(g)$clus+1)) {
    for (j in 1:max(V(g)$clus+1)) {
        adj2[i,j] <- sum(adj[V(g)[clus==i-1]+1,V(g)[clus==j-1]+1])
        }
    }
diag(adj2) <- 0

g.reduit <- graph.adjacency(adj2,mode="undirected",weighted=TRUE) # The resulting graph can be weighted (it counts the number of links between two communities)

2010/3/8 Tamas Nepusz <address@hidden>

> What I call "reduced graph" in this context is a graph g' whose nodes are the communities of g and an edge exist between two nodes of g' if there is at least one edge between the two correspondent communities.

There is no such function in igraph yet, and the reason is that it is very hard to decide what to do with the vertex and edge attributes after collapsing the vertices of the same community into a single vertex. It is probably not meaningful to keep the vertex attributes, but keeping the edge attributes may make sense; i.e., when there is more than a single edge between communities, one may wish to add up the numeric attributes of the edges before collapsing them. We haven't really figured it out how a generic solution should behave, so you should try and do it by implementing a function for that in R. Maybe Gabor can conjure up an efficient solution using only a few lines of code in R.

--
Tamas

_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help

reducedgraph.pdf
Description: Adobe PDF document