Re: [igraph] biconnected.components vs cohesive.blocks

[Gábor Csárdi]

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 <address@hidden> 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 <address@hidden> 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
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help