Re: [igraph] Choosing between different methods of detecting communities

[Tamás Nepusz]

Thanks for the correction -- I have added the updated version to the wiki for 
future reference:  

http://igraph.wikidot.com/community-detection-in-r#toc5  

--  
T.


On Friday, 28 September 2012 at 02:46, Gábor Csárdi wrote:

> On Thu, Sep 27, 2012 at 7:18 PM, Tamás Nepusz <address@hidden 
> (mailto:address@hidden)> wrote:
> > Hi Roey,
> >  
> > I've had a bit of free time tonight so here is a quick solution in R:
> >  
> > community.significance <- function(graph, vs, …) {
> > if (is.directed(graph)) {
> > error("The graph must be undirected")
> > }
> > sg <- induced.subgraph(graph, vs)
> > indeg <- degree(sg)
> > outdeg <- degree(graph, vs) - indeg
> > return(wilcox.test(indeg, outdeg, ….)$p.value)
> > }
>  
>  
>  
> A small correction, there is no error() function in R, you need
> stop("...") instead of error. stopifnot() might be even better,
> because it is very readable.
>  
> Plus, the return statement is redundant and is usually not used at the
> end of functions, because functions return the the value of the last
> expression anyway.
>  
> Also, it is best to return the whole object that is returned by
> wilcox.test(), because it contains more data about the test, e.g. the
> test statistic itself. But this is really nitpicking, sorry.
>  
> G.
>  
> > This will return a p-value corresponding to the null hypothesis that the 
> > distribution of the "internal" and "external" degrees of the vertices in 
> > the community are equal. Small p-values indicate significant communities. 
> > For example:
> >  
> > g <- graph.full(5) + graph.full(5)
> > g[1, 6] <- 1
> > mcs <- maximal.cliques(g)
> > sapply(mcs, function(vs) { community.significance(g, vs) })
> >  
> > --
> > T.
> >  
> >  
> > On Thursday, 27 September 2012 at 01:43, Roey Angel wrote:
> >  
> > > Hi Tamas,
> > > Thanks a lot for the help.
> > > I might try to write an R implementation myself or just wait for someone
> > > else to write them better than me.
> > >  
> > > Roey
> > >  
> > > On 09/26/2012 02:48 PM, Tamás Nepusz wrote:
> > > > > The papers look interesting. Has anyone implemented any of the methods
> > > > > into igraph (or any other library for that matter)?
> > > >  
> > > >  
> > > >  
> > > >  
> > > > I'm not aware of any such implementation but there was a thread on this 
> > > > mailing list some time earlier where I proposed a relatively simple 
> > > > method to assess the significance of a particular community. Given that 
> > > > you work in R, you should have all the necessary statistical tools 
> > > > (e.g., the Mann-Whitney U test) to implement it:
> > > >  
> > > > http://lists.gnu.org/archive/html/igraph-help/2012-06/msg00014.html
> > > >  
> > > > > Chen -- do you mean edge.betweenness.community()?
> > > > > I tried it but then R hangs (haven't tried letting run for a few hours
> > > > > though).
> > > >  
> > > >  
> > > >  
> > > >  
> > > > edge.betweenness.community() is slow so it isn't really useful for 
> > > > graphs that contain more than a few hundred vertices -- unless you have 
> > > > a day to spare or so :) I would probably try multilevel.community() 
> > > > and/or infomap.community(). There is a recent review of community 
> > > > detection algorithms that you might be interested in:
> > > >  
> > > > http://arxiv.org/abs/0906.0612
> > > >  
> > > > Best,
> > > > Tamas
> > > >  
> > > >  
> > > >  
> > > > _______________________________________________
> > > > igraph-help mailing list
> > > > address@hidden (mailto:address@hidden)
> > > > https://lists.nongnu.org/mailman/listinfo/igraph-help
> > >  
> > >  
> > >  
> > >  
> > >  
> > > Attachments:
> > > - angel.vcf
> >  
> >  
> >  
> >  
> >  
> >  
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden (mailto:address@hidden)
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>  
>  
>  
>  
>  
> --  
> Gabor Csardi <address@hidden (mailto:address@hidden)> MTA KFKI RMKI
>  
> _______________________________________________
> igraph-help mailing list
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help