cohesive.blocks {igraph} | R Documentation |
Calculates cohesive blocks for objects of class igraph
.
cohesive.blocks(graph, db=NULL, useDB=(vcount(graph)>400 && require(RSQLite)), cutsetHeuristic=TRUE, verbose=igraph.par("verbose")) is.bgraph(graph)
graph |
A graph object of class |
db |
An optional |
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 |
cutsetHeuristic |
Logical scalar. TODO |
verbose |
Level of console output. Supply |
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.
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.
Peter McMahan peter.mcmahan@gmail.com
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.
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.
## 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: ## Not run: plot(gBlocks, vertex.size=7, layout=layout.kamada.kawai) ## End(Not run) ## Save the results as Pajek ".net" and ".clu" files: ## Not run: write.pajek.bgraph(gBlocks,file="gBlocks") ## End(Not run) ## An example that works better with the "kanevsky" cutset algorithm ## Not run: g <- read.graph(file="http://intersci.ss.uci.edu/wiki/Vlado/SanJuanSur.net", format="pajek") gBlocks <- cohesive.blocks(g, cutsetAlgorithm="kanevsky") ## End(Not run)