[R] community finding in a graph and heatplot

[Gábor Csárdi]

On Sun, Jun 3, 2012 at 4:11 PM, Aziz, Muhammad Fayez <aziz4 at illinois.edu> wrote:
>
> Hmm interesting. To come to think of it there could be many disconnected components in the graph and thus there should be a generic way to either mitigate the disconnectedness in the dendrogram or in the original graph. I had no luck in finding such a trick though google search. I then ran the script on minute-scale graphs and have following results:
>
> 1) disconnected graph with three modules:
>
> *Vertices 9
> *Edges
> 1 2 1
> 2 3 1
> 3 1 1
> 4 5 1
> 5 6 1
> 6 4 1
> 7 8 1
> 8 9 1
> 9 7 1
>
> corresponding fgc$merges matrix:
>
>     [,1] [,2]
> [1,]    1    0
> [2,]    2    9
> [3,]    7    6
> [4,]    8   11
> [5,]    4    3
> [6,]    5   13
>
> 2) connected graph by adding links 1-2 and 4-7 in graph 1):
>
> *Vertices 9
> *Edges
> 1 2 1
> 2 3 1
> 3 1 1
> 4 5 1
> 5 6 1
> 6 4 1
> 7 8 1
> 8 9 1
> 9 7 1
> 1 4 1
> 4 7 1
>
> corresponding fgc$merges matrix:
>
>     [,1] [,2]
> [1,]    2    1
> [2,]    0    9
> [3,]    8    7
> [4,]    6   11
> [5,]    5    4
> [6,]    3   13
> [7,]   14   12
> [8,]   15   10
>
> There needs to be a generic way to get fgc$merges of the form 2) from 1). Hints please.

Well, how do you merge the unconnected components? I guess you could
come up with an order based on modularity, or just merge them in
arbitrary order. The following is from igraph 0.6, and I haven't tried
it on your data, but it might just work. It merges the individual
subtrees in arbitrary order.

complete.dend <- function(comm) {
  merges <- comm$merges
  if (nrow(merges) < comm$vcount-1) {
    miss <- seq_len(comm$vcount + nrow(merges))[-as.vector(merges)]
    miss <- c(miss, seq_len(length(miss)-2) + comm$vcount+nrow(merges))
    miss <- matrix(miss, byrow=TRUE, ncol=2)
    merges <- rbind(merges, miss)
  }
  storage.mode(merges) <- "integer"

  merges
}

Best,
Gabor

[...]