Re: [igraph] cohesive blocks

[Gabor Csardi]

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 <- add.edges(g, c(3,4,4,5,4,2))
> g <- g %du% g %du% g
> g <- add.edges(g, c(0,6,1,7,0,12,4,0,4,1))

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

[...]

-- 
Csardi Gabor <address@hidden>    UNIL DGM