Cohesive blocking is a method of determining hierarchical subsets of
graph vertices based on their structural cohesion (or vertex
connectivity). For a given graph $G$, a subset of its vertices
$S\subset V(G)$ is said to be maximally $k$-cohesive if there is
no superset of $S$ with vertex connectivity greater than or equal to
$k$. Cohesive blocking is a process through which, given a
$k$-cohesive set of vertices, maximally $l$-cohesive subsets are
recursively identified with $l>k$. Thus a hiearchy of vertex subsets
is found, whith the entire graph $G$ at its root.
The function cohesive.blocks implements cohesive blocking.
It returns a cohesiveBlocks object. cohesiveBlocks
should be handled as an opaque class, i.e. its internal structure
should not be accessed directly, but through the functions listed
here. The function length can be used on cohesiveBlocks
objects and it gives the number of blocks.
The function blocks returns the actual blocks stored in the
cohesiveBlocks object. They are returned in a list of numeric
vectors, each containing vertex ids.
The function blockGraphs is similar, but returns the blocks as
(induced) subgraphs of the input graph. The various (graph, vertex and
edge) attributes are kept in the subgraph.
The function cohesion returns a numeric vector, the cohesion of
the different blocks. The order of the blocks is the same as for
the blocks and blockGraphs functions.
The block hierarchy can be queried using the hierarchy
function. It returns an igraph graph, its vertex ids are ordered
according the order of the blocks in the blocks and
blockGraphs, cohesion, etc. functions.
parent gives the parent vertex of each block, in the block
hierarchy, for the root vertex it gives 0.
plotHierarchy plots the hierarchy tree of the cohesive blocks
on the active graphics device, by calling igraph.plot.
The exportPajek function can be used to export the graph and
its cohesive blocks in Pajek format. It can either export a single
Pajek project file with all the information, or a set of files,
depending on its project.file argument. If project.file
is TRUE, then the following information is written to the file
(or connection) given in the file argument: (1) the input
graph, together with its attributes, see write.graph for
details; (2) the hierarchy graph; and (3) one binary partition for
each cohesive block. If project.file is FALSE, then the
file argument must be a character scalar and it is used as the
base name for the generated files. If file is
basename, then the following files are created: (1)
basename.net for the original graph; (2)
basename_hierarchy.net for the hierarchy graph; (3)
basename_block_x.net for each cohesive block, where
x is the number of the block, starting with one.
maxcohesion returns the maximal cohesion of each vertex,
i.e. the cohesion of the most cohesive block of the vertex.
The generic function summary works on cohesiveBlocks
objects and it prints a one line summary to the terminal.
The generic function print is also defined on
cohesiveBlocks objects and it is invoked automatically if the
name of the cohesiveBlocks object is typed in. It produces
an output like this: Cohesive block structure:
B-1 c 1, n 23
'- B-2 c 2, n 14 oooooooo.. .o......oo ooo
'- B-4 c 5, n 7 ooooooo... .......... ...
'- B-3 c 2, n 10 ......o.oo o.oooooo.. ...
'- B-5 c 3, n 4 ......o.oo o......... ...
The left part shows the block structure, in this case for five
blocks. The first block always corresponds to the whole graph, even if
its cohesion is zero. Then cohesion of the block and the number of
vertices in the block are shown. The last part is only printed if the
display is wide enough and shows the vertices in the blocks,
ordered by vertex ids. o means that the vertex is included,
a dot means that it is not, and the vertices are shown in groups of
ten.
The generic function plot plots the graph, showing one or more
cohesive blocks in it.