cohesive.blocks: Calculate Cohesive Blocks

Description

Calculates cohesive blocks for objects of class igraph.

Usage

cohesive.blocks(graph, db=NULL,
                useDB=(vcount(graph)>400 && require(RSQLite)),
                verbose=igraph.par("verbose"))
is.bgraph(graph)

Arguments

graph

A graph object of class igraph.

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.

verbose

Level of console output. Supply TRUE here to follow the progress of the computation.

concept

Structurally cohesive blocks

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 $SV(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.

cohesive.blocks returns a graph of class c(bgraph,igraph), with four (new) graph attributes:

blocks

{A list with one element for each cohesive block found. The elements are numeric vectors listing the indices of the nodes within that block.} block.cohesion{A numeric vector with length equal to the number of cohesive blocks found, listing the cohesion of those blocks.} tree{The hierarchical tree of the cohesive blocks. Each node of this graph represents a cohesive block, and directed edges represent inclusion as proper subset.} data{A list containing supplementary data from the calculation.}

is.bgraph returns a logical scalar.

References

C. Patvardhan, V. C. Prasad, V. Prem Pyara. Vertex Cutsets of Undirected Graphs. IEEE Transactions on Reliability, 44(2):347--353, June, 1995. 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.

Examples

Run this code

## 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")

Run the code above in your browser using DataCamp Workspace