Re: [igraph] community detection

[Vincent Matossian]

Gabor,

Yes it's  that one running recursively. I don't have a C implementation but I attached the R one below. I might be missing something but the community detection isn't fail proof from what I observed on other than tree graphs some nodes get improperly labeled. There's a part of the algorithm that I did not handle though, choosing the best split based on how much contribution modularity provides because I did not understand that clearly...

On another note, does anyone know of a quick way to convert GML to GraphML ?

Thanks

Vincent


## MARK NEWMAN'S ALGORITHM AS PROPOSED IN  ARXIV REF: physics/0605087

## RETURN THE MODULARITY MATRIX AS DEFINED BY NEWMAN
## Q = A - B WHERE B IS BASED ON A PROBABILITY OF EXISTENCE OF AN EDGE
## IN THIS CASE BASED ON THE CONFIGURATION MODEL
graph.modularity=function(g){
  d <- degree(g)
  m <- ecount(g)
  vcnt <- vcount(g)
  B<-matrix(0,nrow=vcnt,ncol=vcnt)
  for(i in 1:vcnt){
    for(j in 1:vcnt){
      B[i,j] <- d[i]*d[j]/(2*m)
    }
  }
  A <- get.adjacency(g)
  Q <- A-B
  return(Q)
}

## THE MAIN ROUTINE FROM WHERE COMMUNITIES ARE DETECTED USING THE MODULARITY MATRIX 
detect.communities=function(g,indvsbl=0){

  V(g)$lbl<-0:(vcount(g)-1)
  V(g)$cmn<-rep(-1,vcount(g))
  
  g <- modularity.partitioning(g,g,indvsbl)
  
  clrs<-rainbow(max(V(g)$cmn)+1)
  lay<-layout.kamada.kawai(g)
  plot(g,vertex.color=clrs[V(g)$cmn+1],vertex.size=10,layout=lay,labels=V(g)$cmn)
  
  membership <- V(g)$cmn
  csize <- c()
  for(i in 1:max(V(g)$cmn+1)){
    csize[i] <- length(which(V(g)$cmn==(i-1)))
  }
  ret <- list(g,membership,csize)
  names(ret) <- c("g","membership","csize")
  
  return(ret)
}
## THE RECURSIVE FUNCTION CALL STOPS WHEN A SUBDIVISION DOES
## NOT CONTRIBUTE TO THE MODULARITY (A NEGATIVE LARGEST EIGENVALUE)
modularity.partitioning=function(g,sg,indvsbl){
  ## MODULARITY MATRIX OF THE SUBGRAPH
  Q<-graph.modularity(sg)
  ## EIGENVALUES OF THE MODULARITY
  eg<-eigen(Q);
  evl<-eg$values
  max_eval<-sort(evl,decreasing=T,index.return=T)
  ## IF INDIVISIBLE THEN COLOR/TAG THE COMMUNITY AND RETURN THE CURRENT GRAPH
  if(round(max_eval$x[1],digits=2)<=indvsbl) {
    ## COLOR VERTICES IN THE COMMUNITY
    col<-max(V(g)$cmn)+1
    V(g)[V(sg)$lbl]$cmn <- col
    return(g)
  }
  ## ELSE GET PRINCIPAL EIGENVECTOR
  v<-eg$vectors[,max_eval$ix[1]]
  ## PARTITION THE VERTICES ACCORDING TO THE SIGNS OF THE EIGENVECTOR ELTS
  neg<-which(v<0)
  pos<-which(v>=0)
  ## COLOR VERTICES IN THE COMMUNITY
  ## RECURSIVELY EXPLORE THE PARTITION OF NEGATIVE EIGENVECTOR CONTRIBUTIONS
  g <- modularity.partitioning(g,subgraph(g,V(sg)$lbl[neg]),indvsbl)
  ## RECURSIVELY EXPLORE THE PARTITION OF POSITIVE EIGENVECTOR CONTRIBUTIONS
  g <- modularity.partitioning(g,subgraph(g,V(sg)$lbl[pos]),indvsbl)
  return(g)
}

test.modularity=function(){
  tree100 <- 
graph.tree(100,mode="undirected")
  cmn1 <- detect.communities(tree100,0)
  x11();
  cmn2 <- detect.communities(tree100,2)
}

On 3/29/07, Gabor Csardi <address@hidden> wrote:

Vincent,

oh yes, i know this algorithm, i actually implemented it -- incorrectly though --
on my laptop once in five minutes while listening MEJN's talk and making quick
notes of his slides. :) It is something like

community.newman <- function(g) {
  deg <- degree(g) ; ec <- ecount(g)
  B <- get.adjacency(g) - outer(deg, deg, function(x,y) x*y / 2 / ec)
  diag(B) <- 0
  Re(eigen(B)$vectors[,1])
}

am i right? (slide 24 of http://cneurocvs.rmki.kfki.hu/igraph/doc/iccs06.pdf
has a complete example, hopefully the code still works with the current version).

This is a very nice and clean algorithm. The C implementation introduces some
concerns however, because we need an eigenvector algorithm. It is not very hard
to find and borrow an implementation from (say) GSL, however, i'm a little
worried whether this would be the correct solution or igraph should simply depend
on GSL (or another numerical library dealing with matrices). As soon as i decide
this (any opinions?) i can incorporate the eigenvector based community
detection algorithm in igraph.

Thanks again, please keep sending suggestions, Best,
Gabor

On Tue, Mar 27, 2007 at 09:56:24PM -0500, Vincent Matossian wrote:
>     Hi,
>
>    Gabor, I was wondering what is the status of the development on
>    alternatives to the spinglass based implementation for community
>    detection? I noticed that the community files are still experimental and
>    not recommended to be used.
>
>    I just implemented in igraph-R the algorithm proposed in
>    [1]http://arxiv.org/pdf/physics/0605087 and found that it gives very good
>    results and faster than the Spinglass community detection (although the
>    threshold for community detection has to be played with to avoid detecting
>    too many smaller communities).
>
>    Here are the timings on my machine (Athlon 64 Xp2 &Windows XP) for a 100
>    node graph.tree
>
>    > system.time(spinglass.community (tree100))
>    [1] 7.67 0.00 7.67   NA   NA
>
>    > system.time(g<-detect.communities (tree100,2))
>    [1] 0.79 0.02 0.81   NA   NA
>
>    Spinglass.community finds the communities:
>
>    $membership
>      [1]  4  4  4  8  7  2  4  8  9  7  0  2 11  3  4  8  5  9  1 12  7  0
>    0  6  2
>     [26] 11 11  3  3 10  4  8  8  5  5  9  9  1  1 12 12  7  7  0  0  0  0
>    6  6  2
>     [51]  2 11 11 11 11  3  3  3  3 10 10  4  4  8  8  8  8  5  5  5  5  9
>    9  9  9
>     [76]  1  1  1  1 12 12 12 12  7  7  7  7  0  0  0  0  0  0  0  0  6  6
>    6  6  2
>
>    $csize
>     [1] 15  7  6  7  8  7  7  9  9  8  3  7  7
>
>    While detect.communities (based on modularity) finds:
>
>    $membership
>      [1] 3 6 3 6 4 2 3 7 6 4 5 1 2 3 3 7 7 6 6 4 4 5 5 1 1 2 2 3 3 3 3 7 7 7
>    7 6 6
>     [38] 6 6 4 4 4 4 5 5 5 5 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 7 7 7 7 7 7 7 7
>    6 6 6
>     [75] 6 6 6 6 6 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 1 1 1 1 1
>
>    $csize
>    [1] 12  8 17 16 15 17 15
>
>    So I was wondering if you think a C implementation would be relevant.
>    Newman uses the Lanczos algorithm to compute the eigenvectors which I
>    guess would yet speed up the computation. I'll forward the few lines of R
>    code if interested.
>
>    Thanks again for making igraph available to the community!!
>
>    Cheers,
>
>    Vincent
>
> References
>
>    Visible links
>    1. http://arxiv.org/pdf/physics/0605087

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


--
Csardi Gabor < address@hidden>    MTA RMKI, ELTE TTK


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