igraph-help
[Top][All Lists]

## Re: [igraph] cohesive blocks

 From: Gabor Csardi Subject: Re: [igraph] cohesive blocks Date: Fri, 25 Jan 2008 23:13:44 +0100 User-agent: Mutt/1.5.13 (2006-08-11)

```On Thu, Jan 24, 2008 at 11:17:42PM +0100, Simone Gabbriellini wrote:
> >>Second point: is it possible to underline in the plot the cut points
> >>of each block?
> >You mean to underline the labels? Theoretically possible, but i'm not
> >sure it is worth. You would need to generate the layout first,
> >and do the underlining via "segments" based on the sizes of the
> >labels.
> >It is an easier solution to set the fonts to italic and/or bold via
> >'vertex.label.font'. Unfortunately the white label color is hardwired
> >into plot.bgraph, this should be changed....
> >
> >G.
> >
> No, I just use the wrong word, you know, my english should be better..
> What I mean is to have something like: every cutpoints is a square and
> all the others are circle.. In the article by Moody I see that
> structural cohesion are the minimum number of nodes who, if removed
> from a group, would disconnect the group. I suppose the function
> cohesive.blocks() find those nodes, and I simply wonder if it is
> possible to see who they are...

Oh, ok. graph.cohesion() gives the cohesion, but not the cutset
(cutset=the vertices to be removed). Of course the cutset is not
neccessarily unique, usually it is not. igraph:::kCutsets() is
a private function which gives the cutsets of a given size.
It is not documented and the current implementation is quite slow.

Here is an example:

> g <- graph.full(4) %du% graph.empty(2, dir=FALSE)
> g <- g %du% g %du% g

> graph.cohesion(g)
[1] 1
> igraph:::kCutsets(g, k=1)
[1]  4 10 16 12  0

or a simpler one:

> g <- graph.ring(5)
> graph.cohesion(g)
[1] 2
> igraph:::kCutsets(g, k=1)
numeric(0)
> igraph:::kCutsets(g, k=2)
[[1]]
[1] 1 4

[[2]]
[1] 0 2

[[3]]
[1] 2 4

[[4]]
[1] 1 3

[[5]]
[1] 0 3

The cohesive.blocks function does a bit more than just finding these
nodes, it finds the hierarchical structure of the graph, defined
via cohesive blocks. Basically, a subgraph is a cohesive subgroup
it its cohesion is larger than the one of the original graph. (If i
understand everything correctly, i'm not the author of this piece of
code.)

G.

[...]

--