[igraph] community detection

[Vincent Matossian]

 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 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