[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Gábor Csárdi
Subject: Re: [igraph] biconnected.components vs cohesive.blocks
Date: Thu, 4 Jul 2013 10:47:44 -0400

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. :)


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:


On Thu, Jul 4, 2013 at 9:44 AM, Massimo Franceschet <address@hidden> wrote:
[Using igraph ‘’ 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)


Massimo Franceschet
igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]