cohesive.blocks
Calculate Cohesive Blocks
Calculates cohesive blocks for objects of class igraph
.
- Keywords
- graphs
Usage
cohesive.blocks(graph, labels = TRUE)blocks(blocks)
blockGraphs(blocks, graph)
cohesion(blocks)
hierarchy(blocks)
parent(blocks)
plotHierarchy(blocks,
layout=layout.reingold.tilford(hierarchy(blocks), root=1), ...)
exportPajek(blocks, graph, file, project.file = TRUE)
maxcohesion(blocks)
## S3 method for class 'cohesiveBlocks':
print(x, \dots)
## S3 method for class 'cohesiveBlocks':
summary(object, \dots)
## S3 method for class 'cohesiveBlocks':
length(x)
## S3 method for class 'cohesiveBlocks':
plot(x, y, colbar = rainbow(max(cohesion(x))+1),
col = colbar[maxcohesion(x)+1], mark.groups = blocks(x)[-1], ...)
Arguments
- graph
- For
cohesive.blocks
a graph object of classigraph
. It must be undirected and simple. (Seeis.simple
.)For
blockGraphs
andexportPajek
- labels
- Logical scalar, whether to add the vertex labels to the result object. These labels can be then used when reporting and plotting the cohesive blocks.
- blocks,x,object
- A
cohesiveBlocks
object, created with thecohesive.blocks
function. - file
- Defines the file (or connection) the Pajek file is
written to.
If the
project.file
argument isTRUE
, then it can be a filename (with extension), a file object, or in general any king of connection object. - project.file
- Logical scalar, whether to create a single Pajek project file containing all the data, or to create separated files for each item. See details below.
- y
- The graph whose cohesive blocks are supplied in the
x
argument. - colbar
- Color bar for the vertex colors. Its length should be
at least $m+1$, where $m$ is the maximum cohesion in the
graph. Alternatively, the vertex colors can also be directly
specified via the
col
argument. - col
- A vector of vertex colors, in any of the usual
formats. (Symbolic color names (e.g.
red ,blue , etc.) , RGB colors (e.g.#FF9900FF ), integer numbers referring to the current palette. By d - mark.groups
- A list of vertex sets to mark on the plot by circling them. By default all cohesive blocks are marked, except the one corresponding to the all vertices.
- layout
- The layout of a plot, it is simply passed on to
plot.igraph
, see the possible formats there. By default the Reingold-Tilford layout generator is used. - ...
- Additional arguments.
plotHierarchy
andplot
pass them toplot.igraph
.print
andsummary
ignore them.
Details
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
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. plot
plots the graph, showing one or more
cohesive blocks in it.
Value
cohesive.blocks
returns acohesiveBlocks
object.blocks
returns a list of numeric vectors, containing vertex ids.blockGraphs
returns a list of igraph graphs, corresponding to the cohesive blocks.cohesion
returns a numeric vector, the cohesion of each block.hierarchy
returns an igraph graph, the representation of the cohesive block hierarchy.parent
returns a numeric vector giving the parent block of each cohesive block, in the block hierarchy. The block at the root of the hierarchy has no parent and0
is returned for it.plotHierarchy
,plot
andexportPajek
returnNULL
, invisibly.maxcohesion
returns a numeric vector with one entry for each vertex, giving the cohesion of its most cohesive block.print
andsummary
return thecohesiveBlocks
object itself, invisibly.length
returns a numeric scalar, the number of blocks.
concept
Structurally cohesive blocks
References
J. Moody and D. R. White. Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review, 68(1):103--127, Feb 2003.
See Also
Examples
## The graph from the Moody-White paper
mw <- graph.formula(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7,
5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10,
10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16,
17-18:19:20, 18-20:21, 19-20:22:23, 20-21,
21-22:23, 22-23)
mwBlocks <- cohesive.blocks(mw)
# Inspect block membership and cohesion
mwBlocks
blocks(mwBlocks)
cohesion(mwBlocks)
# Save results in a Pajek file
exportPajek(mwBlocks, mw, file="/tmp/mwBlocks.paj")
# Plot the results
if (interactive()) {
plot(mwBlocks, mw)
}
## The science camp network
camp <- graph.formula(Harry:Steve:Don:Bert - Harry:Steve:Don:Bert,
Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat,
Holly - Carol:Pat:Pam:Jennie:Bill,
Bill - Pauline:Michael:Lee:Holly,
Pauline - Bill:Jennie:Ann,
Jennie - Holly:Michael:Lee:Ann:Pauline,
Michael - Bill:Jennie:Ann:Lee:John,
Ann - Michael:Jennie:Pauline,
Lee - Michael:Bill:Jennie,
Gery - Pat:Steve:Russ:John,
Russ - Steve:Bert:Gery:John,
John - Gery:Russ:Michael)
campBlocks <- cohesive.blocks(camp)
campBlocks
if (interactive()) {
plot(campBlocks, camp, vertex.label=V(camp)$name, margin=-0.2,
vertex.shape="rectangle", vertex.size=24, vertex.size2=8,
mark.border=1, colbar=c(NA, NA,"cyan","orange") )
}