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

[Tamás Nepusz]

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

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
>