igraph-help
[Top][All Lists]

## Re: [igraph] help with cohesion.blocks (again...)

 From: Gabor Csardi Subject: Re: [igraph] help with cohesion.blocks (again...) Date: Sat, 2 Feb 2008 15:28:16 +0100 User-agent: Mutt/1.5.13 (2006-08-11)

```Peter, thanks, i'll read over the paper(s) and see what to do.

Btw. i found this while playing with the old implementation:

> example(cohesive.blocks)
> gBlocks\$blocks
[[1]]
[1]  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17

[[2]]
[1] 12 13 14 15 16

[[3]]
[1]  0  1  2  3  4  6  7  8  9 10

[[4]]
[1] 12 13 14 15

[[5]]
[1] 6 7 8 9

[[6]]
[1] 0 1 2 3 4
> gBlocks\$block.cohesion
[1] 1 2 2 3 3 4
> graph.cohesion( subgraph(g, gBlocks\$blocks[[2]]) )
[1] 2
> igraph:::kCutsets( subgraph(g, gBlocks\$blocks[[2]]), k=2 )
list()
> igraph:::kCutsets( subgraph(g, gBlocks\$blocks[[2]]), k=3 )
[[1]]
[1] 1 2 3

But, clearly, there is a 2-cutset:

> clusters( delete.vertices(subgraph(g, gBlocks\$blocks[[2]]), c(2,3) ) )\$no
[1] 2

Which means that i either misunderstood something, or there is a problem
with with kCutsets(). kCutsets2() seems to be better:

> kCutsets2( subgraph(g, gBlocks\$blocks[[2]]), k=2 )
[[1]]
[1] 2 3

G.

On Fri, Feb 01, 2008 at 12:30:53PM -0600, address@hidden wrote:
> Hi,
> I did some research into alternate cutset-finding algorithms and found
> this one from 1995:
> C. Patvardhan, V. C. Prasad, and V. P. Pyara. Vertex cutsets of
> undirected graphs. Reliability, IEEE
> Transactions on, 44(2):347–353, June 1995.
>
[...]

--