vertex.connectivity          package:igraph          R Documentation

_V_e_r_t_e_x _c_o_n_n_e_c_t_i_v_i_t_y.

_D_e_s_c_r_i_p_t_i_o_n:

     The vertex connectivity of a graph or two vertices, this is
     recently also called group cohesion.

_U_s_a_g_e:

     vertex.connectivity(graph, source=NULL, target=NULL, checks=TRUE)
     vertex.disjoint.paths(graph, source, target)
     graph.cohesion(graph, checks=TRUE)

_A_r_g_u_m_e_n_t_s:

   graph: The input graph.

  source: The id of the source vertex, for 'vertex.connectivity' it can
          be 'NULL', see details below.

  target: The id of the target vertex, for 'vertex.connectivity' it can
          be 'NULL', see details below.

  checks: Logical constant. Whether to check that the graph is
          connected and also the degree of the vertices. If the graph
          is not (strongly) connected then the connectivity is
          obviously zero. Otherwise if the minimum degree is one then
          the vertex connectivity is also one. It is a good idea to
          perform these checks, as they can be done quickly compared to
          the connectivity calculation itself.  They were suggested by
          Peter McMahan, thanks Peter.

_D_e_t_a_i_l_s:

     The vertex connectivity of two vertices ('source' and 'target') in
     a directed graph is the minimum number of vertices needed to
     remove from the graph to eliminate all (directed) paths from
     'source' to 'target'. 'vertex.connectivity'  calculates this
     quantity if both the 'source' and 'target' arguments are given and
     they're not 'NULL'.

     The vertex connectivity of a graph is the minimum vertex
     connectivity of all (ordered) pairs of vertices in the graph. In
     other words this is the minimum number of vertices needed to
     remove to make the graph not strongly connected. (If the graph is
     not strongly connected then this is zero.) 'vertex.connectivity'
     calculates this quantitty if neither the 'source' nor 'target'
     arguments are given. (Ie. they are both 'NULL'.)

     A set of vertex disjoint directed paths from 'source' to 'vertex'
     is a set of directed paths between them whose vertices do not
     contain common vertices (apart from 'source' and 'target'). The
     maximum number of vertex disjoint paths between two vertices is
     the same as their vertex connectivity. 

     The cohesion of a graph (as defined by White and Harary, see
     references), is the vertex connectivity of the graph. This is
     calculated by 'graph.cohesion'.

     These three functions essentially calculate the same measure(s),
     more precisely 'vertex.connectivity' is the most general, the
     other two are included only for the ease of using more descriptive
     function names.

_V_a_l_u_e:

     A scalar real value.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

     Douglas R. White and Frank Harary: The cohesiveness of blocks in
     social networks: node connectivity and conditional density, TODO:
     citation

_S_e_e _A_l_s_o:

     'graph.maxflow', 'edge.connectivity', 'edge.disjoint.paths',
     'graph.adhesion'

_E_x_a_m_p_l_e_s:

     g <- barabasi.game(100, m=1)
     g <- delete.edges(g, E(g)[ 99 %--% 0 ])
     g2 <- barabasi.game(100, m=5)
     g2 <- delete.edges(g2, E(g2)[ 99 %--% 0])
     vertex.connectivity(g, 99, 0)
     vertex.connectivity(g2, 99, 0)
     vertex.disjoint.paths(g2, 99, 0)

     g <- erdos.renyi.game(50, 5/50)
     g <- as.directed(g)
     g <- subgraph(g, subcomponent(g, 1))
     graph.cohesion(g)

