Re: [igraph] community detection

[Gabor Csardi]

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