
From:  Roey Angel 
Subject:  Re: [igraph] Choosing between different methods of detecting communities 
Date:  Mon, 08 Oct 2012 20:46:57 +0200 
Useragent:  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! Roey 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: http://igraph.wikidot.com/communitydetectioninr#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 pvalue corresponding to the null hypothesis that the distribution of the "internal" and "external" degrees of the vertices in the community are equal. Small pvalues 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 MannWhitney U test) to implement it: http://lists.gnu.org/archive/html/igraphhelp/201206/msg00014.htmlChen  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 _______________________________________________ igraphhelp mailing list address@hidden (mailto:address@hidden) https://lists.nongnu.org/mailman/listinfo/igraphhelpAttachments:  angel.vcf_______________________________________________ igraphhelp mailing list address@hidden (mailto:address@hidden) https://lists.nongnu.org/mailman/listinfo/igraphhelp Gabor Csardi <address@hidden (mailto:address@hidden)> MTA KFKI RMKI _______________________________________________ igraphhelp mailing list address@hidden (mailto:address@hidden) https://lists.nongnu.org/mailman/listinfo/igraphhelp_______________________________________________ igraphhelp mailing list address@hidden https://lists.nongnu.org/mailman/listinfo/igraphhelp 
angel.vcf
Description: Vcard
[Prev in Thread]  Current Thread  [Next in Thread] 