cohesive.blocks

0th

Percentile

Calculate Cohesive Blocks

Calculates cohesive blocks for objects of class igraph.

Keywords
graphs
Usage
cohesive.blocks(graph, db=NULL,
                useDB=(vcount(graph)>400 && require(RSQLite)),
                cutsetHeuristic=TRUE,
                verbose=igraph.par("verbose"))
is.bgraph(graph)
Arguments
graph
A graph object of class igraph.
db
An optional RSQLite connection to an existing SQLite database (see details). Ignored if NULL.
useDB
Logical. Whether to use an external SQLite database instead of internal R datastructures (see details). By default an SQLite database is used if the graph has more than 400 vertices and the RSQLite package is installed.
cutsetHeuristic
Logical scalar. TODO
verbose
Level of console output. Supply TRUE here to follow the progress of the computation.
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.

For certain larger graphs this algorithm can be quite memory-intensive due to the number of vertex subsets that are examined. In these cases it is worthwhile to use a database to keep track of this data, specified by the useDB argument. If useDB is TRUE, then either a temporary SQLite database is created, or the RSQLite connection specified in db is used. In either case the package RSQLite will be required.

structurally.cohesive.blocks is an alias to cohesive.blocks.

is.bgraph decides whether its argument is a bgraph object.

Value

  • cohesive.blocks returns a graph of class c(bgraph,igraph), with four (new) graph attributes:
  • blocksA list with one element for each cohesive block found. The elements are numeric vectors listing the indices of the nodes within that block.
  • block.cohesionA numeric vector with length equal to the number of cohesive blocks found, listing the cohesion of those blocks.
  • treeThe hierarchical tree of the cohesive blocks. Each node of this graph represents a cohesive block, and directed edges represent inclusion as proper subset.
  • dataA list containing supplementary data from the calculation.
  • is.bgraph returns a logical scalar.

concept

Structurally cohesive blocks

References

A. Kanevsky. On the number of minimum size separating vertex sets in a graph and how to find all of them Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms San Francisco, California, United States. 411--421, 1990. 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

graph.cohesion, plot.bgraph for plotting graphs together with their block hierarchy, write.pajek.bgraph for a writing graphs and cohesive blocks information to Pajek files. See attributes for handling graph attributes.

Aliases
  • cohesive.blocks
  • structurally.cohesive.blocks
  • is.bgraph
Examples
## Create a graph with an interesting structure:
g <- graph.disjoint.union(graph.full(4), graph.empty(2,directed=FALSE))
g <- add.edges(g,c(3,4,4,5,4,2))
g <- graph.disjoint.union(g,g,g)
g <- add.edges(g,c(0,6,1,7,0,12,4,0,4,1))

## Find cohesive blocks:
gBlocks <- cohesive.blocks(g)

## Examine block membership and cohesion:
gBlocks$blocks
gBlocks$block.cohesion

## Plot the resulting graph with its block hierarchy:
plot(gBlocks, vertex.size=7, layout=layout.kamada.kawai)

## Save the results as Pajek ".net" and ".clu" files:
write.pajek.bgraph(gBlocks,file="gBlocks")

## An example that works better with the "kanevsky" cutset algorithm
g <- read.graph(file="http://intersci.ss.uci.edu/wiki/Vlado/SanJuanSur.net", format="pajek")
gBlocks <- cohesive.blocks(g, cutsetAlgorithm="kanevsky")
Documentation reproduced from package igraph, version 0.5.5-3, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.