cohesive.blocks            package:igraph            R Documentation

_C_a_l_c_u_l_a_t_e _C_o_h_e_s_i_v_e _B_l_o_c_k_s

_D_e_s_c_r_i_p_t_i_o_n:

     Calculates cohesive blocks for objects of class 'igraph'.

_U_s_a_g_e:

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

_A_r_g_u_m_e_n_t_s:

   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.

_D_e_t_a_i_l_s:

     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.

_V_a_l_u_e:

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

_A_u_t_h_o_r(_s):

     Peter McMahan peter.mcmahan@gmail.com

_R_e_f_e_r_e_n_c_e_s:

     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.

_S_e_e _A_l_s_o:

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

_E_x_a_m_p_l_e_s:

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

