[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Roey Angel
Subject: Re: [igraph] Choosing between different methods of detecting communities
Date: Mon, 08 Oct 2012 20:46:57 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120912 Thunderbird/15.0.1

Hi Tamas,
apologies for the belated reply,
Your method seems very straightforward and effective at least for my needs (and I hope for others as well).
Two problems I had with it though:
1. This is rather technical and prob. stems from my lack of proper familiarity with igraph. In your minimal examples you generate a mock membership list mcs which you then parse into the function along with the graph object. I was unable to generate a similar list from the community object one gets from the community detection algorithm.
2. If I understood it correctly, your test tests each community individually and reports its statistic and p value. Following this logic, I guess one should: 1. only report significant communities and 2. choose the community detection method which yields the highest ratio of (sig. communities / total communities). Would you agree?

Thanks again for all the help!

On 09/28/2012 10:03 AM, Tamás Nepusz wrote:
Thanks for the correction -- I have added the updated version to the wiki for future reference:  



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.
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) })
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.
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:
Chen -- do you mean edge.betweenness.community()?
I tried it but then R hangs (haven't tried letting run for a few hours
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:
igraph-help mailing list
address@hidden (mailto:address@hidden)
- angel.vcf
igraph-help mailing list
address@hidden (mailto:address@hidden)
Gabor Csardi <address@hidden (mailto:address@hidden)> MTA KFKI RMKI
igraph-help mailing list
address@hidden (mailto:address@hidden)

igraph-help mailing list

Attachment: angel.vcf
Description: Vcard

reply via email to

[Prev in Thread] Current Thread [Next in Thread]