cohesive.blocks {igraph} | R Documentation

## Calculate Cohesive Blocks

### Description

Calculates cohesive blocks for objects of class `igraph`.

### 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 Ssubset 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:

`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.

### Author(s)

Peter McMahan peter.mcmahan@gmail.com

### 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.

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

[Package igraph version 0.5.2 Index]