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

[Gábor Csárdi]

On Thu, Sep 27, 2012 at 7:18 PM, Tamás Nepusz <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
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI