On Wed, Oct 3, 2012 at 11:01 PM, 凌琛 <[email protected]> wrote: > Hi Gabor, > > Many thanks. I got it. So if I want to use unweighted version to cluster the > graph into communities. It is better to sort the edges by weights, and only > use the top weighted edges, and discard the remaining. Then it is not a full > graph, and the unweighted method can detect different communities.
Yes, that is one approach if you really want to use the unweighted method. The problem with it is that it is usually hard to come up with a sensible threshold to discard the edges. I think it is probably better to use the weighted version of the algorithm, or another community structure detection algorithm that also supports weights. But it all depends on your application. Gabor > Best Regards, > chen > > > On Thu, Oct 4, 2012 at 10:44 AM, Gábor Csárdi <[email protected]> wrote: >> >> Hi Chen, >> >> you did not do anything wrong. But igraph is not wrong, either. Your >> graph is a full graph. In other words, it contains all possible edges. >> For this graph, zero modularity is actually really the maximum you can >> get. If you split the graph into two (or more) groups, the modularity >> always gets negative. The best is to keep them in a single community. >> This is very easy to show analytically, and you can try it using the >> modularity() function as well, see below. Also, 'ec' contains all >> modularity values for the different splits along the edge-betweenness >> splits and they are all negative: >> >> graph.isomorphic(graph.full(vcount(G)), G) >> # TRUE >> >> modularity(G, membership=sample(1:2, vcount(G), rep=TRUE), weight=NULL) >> # [1] -0.01278846 >> modularity(G, membership=sample(1:2, vcount(G), rep=TRUE), weight=NULL) >> # [1] -0.01278846 >> modularity(G, membership=sample(1:2, vcount(G), rep=TRUE), weight=NULL) >> # [1] -0.01269231 >> >> ec$modularity >> # [1] -0.025000000 -0.024967949 -0.024903846 -0.024807692 -0.024679487 >> # [6] -0.024519231 -0.024326923 -0.024102564 -0.023846154 -0.023557692 >> # [11] -0.023237179 -0.022884615 -0.022500000 -0.022083333 -0.021634615 >> # [16] -0.021153846 -0.020641026 -0.020096154 -0.019519231 -0.018910256 >> # [21] -0.018269231 -0.017596154 -0.016891026 -0.016153846 -0.015384615 >> # [26] -0.014583333 -0.013750000 -0.012884615 -0.011987179 -0.011057692 >> # [31] -0.010096154 -0.009102564 -0.008076923 -0.007019231 -0.005929487 >> # [36] -0.004807692 -0.003653846 -0.002467949 -0.001250000 0.000000000 >> >> If you use edge weights, then things are different, of course, as some >> parts in your graph will be denser (unless all the edge weighs are >> equal, but this is not true for your graph), and you'll get "real" >> communities. >> >> Best, >> Gabor >> >> On Wed, Oct 3, 2012 at 10:24 PM, 凌琛 <[email protected]> wrote: >> > Hi Gabor, >> > >> > Sorry, I went to sleep last night. >> > >> > I attached the codes and results here. >> > >> >> G = read.graph("D:/text mining project/term lists/40 core term >> >> list/GraphML/50w_lift.graphml", "graphml") >> >> ec <- edge.betweenness.community(G, E(G)$weight, FALSE) >> >> ec >> > Graph community structure calculated with the edge betweenness algorithm >> > Number of communities (best split): 15 >> > Modularity (best split): 0.02788969 >> > Membership vector: >> > [1] 1 2 3 4 5 2 2 2 6 7 2 8 2 2 2 2 2 2 2 9 2 2 >> > 2 2 >> > 2 2 2 10 11 2 12 2 13 2 2 14 2 2 15 2 >> >> ec <- edge.betweenness.community(G, NULL, FALSE) >> >> ec >> > Graph community structure calculated with the edge betweenness algorithm >> > Number of communities (best split): 1 >> > Modularity (best split): 0 >> > Membership vector: >> > [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 >> > 1 1 >> > 1 1 1 1 >> >> >> > >> > Did I do something wrong here? The source data is in the attachment. >> > Thanks. >> > >> > Best Regards, >> > chen >> > >> > On Wed, Oct 3, 2012 at 11:44 PM, Gábor Csárdi <[email protected]> >> > wrote: >> >> >> >> If you get just one community, then you are surely doing something >> >> wrong (or there is a bug in igraph). >> >> >> >> edge.betweenness.community is working fine for our test cases, so >> >> you'll need to show us a reproducible example that does not work the >> >> way you expect it to. >> >> >> >> Gabor >> >> >> >> On Wed, Oct 3, 2012 at 11:34 AM, 凌琛 <[email protected]> wrote: >> >> > yes, maximun the modularity. >> >> > >> >> > Actually when the result is only one community, the modularity is 0. >> >> > >> >> > SNAP is a small library developed by Stanford. You can take a look >> >> > when >> >> > you >> >> > have time. Igraph is much more complete, thanks for the development >> >> > and >> >> > sharing. >> >> > >> >> > Regards, >> >> > chen >> >> > >> >> > On Oct 3, 2012 11:14 PM, "Tamás Nepusz" <[email protected]> wrote: >> >> >> >> >> >> > I know that the algorithm is not deterministic. In my case, the >> >> >> > graph >> >> >> > only have tens of nodes, while the results are very different. >> >> >> > In igraph, the unweighted version results in only one community; >> >> >> > in >> >> >> > SNAP, there are quite a few communities. >> >> >> >> >> >> How does SNAP select the number of communities for the edge >> >> >> betweenness >> >> >> method? This is not specified in the original algorithm; igraph just >> >> >> cuts >> >> >> the community dendrogram at the point where the modularity is >> >> >> maximal. >> >> >> Is it >> >> >> the same for SNAP? >> >> >> >> >> >> Cheers, >> >> >> T. >> >> >> >> >> >> >> >> >> >> >> >> _______________________________________________ >> >> >> igraph-help mailing list >> >> >> [email protected] >> >> >> https://lists.nongnu.org/mailman/listinfo/igraph-help >> >> > >> >> > >> >> > _______________________________________________ >> >> > igraph-help mailing list >> >> > [email protected] >> >> > https://lists.nongnu.org/mailman/listinfo/igraph-help >> >> > >> >> >> >> >> >> >> >> -- >> >> Gabor Csardi <[email protected]> MTA KFKI RMKI >> >> >> >> _______________________________________________ >> >> igraph-help mailing list >> >> [email protected] >> >> https://lists.nongnu.org/mailman/listinfo/igraph-help >> > >> > >> > >> > _______________________________________________ >> > igraph-help mailing list >> > [email protected] >> > https://lists.nongnu.org/mailman/listinfo/igraph-help >> > >> >> >> >> -- >> Gabor Csardi <[email protected]> MTA KFKI RMKI >> >> _______________________________________________ >> igraph-help mailing list >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > -- Gabor Csardi <[email protected]> MTA KFKI RMKI _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
