igraph-help
[Top][All Lists]

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

 From: Tamás Nepusz Subject: Re: [igraph] Choosing between different methods of detecting communities Date: Fri, 28 Sep 2012 01:18:25 +0200

```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
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> Attachments:
> - angel.vcf
>

```