The vertex connectivity of a graph or two vertices, this is recently also called group cohesion.
Usage
vertex_connectivity(graph, source = NULL, target = NULL, checks = TRUE)
vertex_disjoint_paths(graph, source = NULL, target = NULL)
# S3 method for igraph
cohesion(x, checks = TRUE, ...)
Arguments
- graph, x
The input graph.
- source
The id of the source vertex, for
vertex_connectivity()
it can beNULL
, see details below.- target
The id of the target vertex, for
vertex_connectivity()
it can beNULL
, 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.
- ...
Ignored.
Details
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 quantity if neither the
source
nor target
arguments are given. (I.e. 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 in most cases (if the two vertices are not connected by an
edge).
The cohesion of a graph (as defined by White and Harary, see references), is
the vertex connectivity of the graph. This is calculated by
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.
References
White, Douglas R and Frank Harary 2001. The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density. Sociological Methodology 31 (1) : 305-359.
See also
Other flow:
dominator_tree()
,
edge_connectivity()
,
is_min_separator()
,
is_separator()
,
max_flow()
,
min_cut()
,
min_separators()
,
min_st_separators()
,
st_cuts()
,
st_min_cuts()
Author
Gabor Csardi csardi.gabor@gmail.com
Examples
g <- sample_pa(100, m = 1)
g <- delete_edges(g, E(g)[100 %--% 1])
g2 <- sample_pa(100, m = 5)
g2 <- delete_edges(g2, E(g2)[100 %--% 1])
vertex_connectivity(g, 100, 1)
#> [1] 1
vertex_connectivity(g2, 100, 1)
#> [1] 5
vertex_disjoint_paths(g2, 100, 1)
#> [1] 5
g <- sample_gnp(50, 5 / 50)
g <- as.directed(g)
g <- induced_subgraph(g, subcomponent(g, 1))
cohesion(g)
#> [1] 2