|
From: | Vincent Matossian |
Subject: | Re: [igraph] community detection |
Date: | Thu, 29 Mar 2007 15:39:59 -0500 |
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
[Prev in Thread] | Current Thread | [Next in Thread] |