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
hierarchy of vertex subsets is found, with 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 graphs_from_cohesive_blocks
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 graphs_from_cohesive_blocks
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 graphs_from_cohesive_blocks
, cohesion
,
etc. functions.
parent
gives the parent vertex of each block, in the block hierarchy,
for the root vertex it gives 0.
plot_hierarchy
plots the hierarchy tree of the cohesive blocks on the
active graphics device, by calling igraph.plot
.
The export_pajek
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.
max_cohesion
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.