Calculate Cohesive Blocks
Calculates cohesive blocks for objects of class
cohesive.blocks(graph, db=NULL, useDB=(vcount(graph)>400 && require(RSQLite)), cutsetHeuristic=TRUE, verbose=igraph.par("verbose")) is.bgraph(graph)
- A graph object of class
- An optional
RSQLiteconnection to an existing SQLite database (see details). Ignored if
- 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
RSQLitepackage is installed.
- Logical scalar. TODO
- Level of console output. Supply
TRUEhere to follow the progress of the computation.
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
useDB argument. If
TRUE, then either a
temporary SQLite database is created, or the
db is used. In either case the package
RSQLite will be required.
structurally.cohesive.blocks is an alias to
is.bgraph decides whether its argument is a
cohesive.blocksreturns 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.bgraphreturns a logical scalar.
Structurally cohesive blocks
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.
plotting graphs together with their block hierarchy,
write.pajek.bgraph for a writing graphs and cohesive
blocks information to Pajek files. See
handling graph attributes.
## 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")