|
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/community-detection-in-r#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 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 (mailto:address@hidden)
https://lists.nongnu.org/mailman/listinfo/igraph-help
--
Gabor Csardi <address@hidden (mailto:address@hidden)> MTA KFKI RMKI
_______________________________________________
igraph-help mailing list
address@hidden (mailto:address@hidden)
https://lists.nongnu.org/mailman/listinfo/igraph-help
_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help
|
angel.vcf