It is actually not a bug. If you read the cohesive blocking algorithm in the Moody-White paper ( http://www.chssp.columbia.edu/events/documents/MoodyandWhite.pdf), Appendix A, then this will be apparent.
In the cohesive blocking algorithm, you find all minimal vertex separators of the graph, and the remove _all_ of them to identify the (more) cohesive subgroups. What we do is, we remove all cut vertices, then find the connected components in the remainder, and add back the cut vertices to all components we found. (Because the paper says they should belong to "both sides of the cut", it however does not specify what happens if the graph has multiple minimal separators and/or it falls apart to many components and we don't just have "both" sides, but many sides. We interpreted "both" as "all" in this case. So, in summary, the description of the algorithm is not quite clear. So if you think our interpretation is wrong, I can be convinced. :) Gabor On Thu, Jul 4, 2013 at 10:25 AM, Gábor Csárdi <[email protected]>wrote: > Seems to be a cohesive blocking bug, I reported it: > https://github.com/igraph/igraph/issues/505 > > G. > > > On Thu, Jul 4, 2013 at 9:44 AM, Massimo Franceschet < > [email protected]> wrote: > >> [Using igraph ‘0.6.5.1’ under R] >> >> I noticed that cohesive blocks (with cohesion equal to 2) and biconnected >> components of a graph might differ (to my knowledge, they should be the >> same). Here's an example: >> >> # Load Newman's network science collaboration graph >> # (http://www-personal.umich.edu/~mejn/netdata/netscience.zip) >> g = read.graph(file="netscience.gml", format="gml") >> >> # Get the giant component of the graph >> cl = clusters(g) >> g = induced.subgraph(g, which(cl$membership == which.max(cl$csize))) >> >> # Get cohesive blocks >> cb = cohesive.blocks(g) >> b = blocks(cb) >> >> # Get the largest cohesive block with cohesion 2 (number 69, should be >> the largest biconnected component) >> g1 = induced.subgraph(g, b[[69]]) >> >> # Get biconnected components >> bc = biconnected.components(g) >> c = bc$components >> # Get the largest biconnected component (number 86) >> g2 = induced.subgraph(g, c[[86]]) >> >> > graph.cohesion(g1) >> [1] 2 >> >> > graph.cohesion(g2) >> [1] 2 >> >> >> Now, g1 and g2 should be the same graph, but: >> >> > g1 >> IGRAPH U--- 56 171 -- >> + attr: id (v/n), label (v/c), value (e/n) >> >> > g2 >> IGRAPH U--- 134 372 -- >> + attr: id (v/n), label (v/c), value (e/n) >> >> Thanks, >> >> Massimo Franceschet >> _______________________________________________ >> 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
