1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/flow.R
\name{vertex_connectivity}
\alias{vertex_connectivity}
\alias{cohesion}
\alias{vertex_disjoint_paths}
\alias{cohesion.igraph}
\title{Vertex connectivity}
\usage{
vertex_connectivity(graph, source = NULL, target = NULL, checks = TRUE)
vertex_disjoint_paths(graph, source = NULL, target = NULL)
\method{cohesion}{igraph}(x, checks = TRUE, ...)
}
\arguments{
\item{graph, x}{The input graph.}
\item{source}{The id of the source vertex, for \code{vertex_connectivity()} it
can be \code{NULL}, see details below.}
\item{target}{The id of the target vertex, for \code{vertex_connectivity()} it
can be \code{NULL}, see details below.}
\item{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.}
\item{...}{Ignored.}
}
\value{
A scalar real value.
}
\description{
The vertex connectivity of a graph or two vertices, this is recently also
called group cohesion.
}
\details{
The vertex connectivity of two vertices (\code{source} and \code{target}) in
a graph is the minimum number of vertices that must be deleted to
eliminate all (directed) paths from \code{source} to \code{target}.
\code{vertex_connectivity()} calculates this quantity if both the
\code{source} and \code{target} arguments are given and they're not
\code{NULL}.
The vertex connectivity of a pair is the same as the number
of different (i.e. node-independent) paths from source to
target, assuming no direct edges between them.
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.)
\code{vertex_connectivity()} calculates this quantity if neither the
\code{source} nor \code{target} arguments are given. (I.e. they are both
\code{NULL}.)
A set of vertex disjoint directed paths from \code{source} to \code{vertex}
is a set of directed paths between them whose vertices do not contain common
vertices (apart from \code{source} and \code{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
\code{cohesion()}.
These three functions essentially calculate the same measure(s), more
precisely \code{vertex_connectivity()} is the most general, the other two are
included only for the ease of using more descriptive function names.
}
\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)
vertex_connectivity(g2, 100, 1)
vertex_disjoint_paths(g2, 100, 1)
g <- sample_gnp(50, 5 / 50)
g <- as_directed(g)
g <- induced_subgraph(g, subcomponent(g, 1))
cohesion(g)
}
\references{
White, Douglas R and Frank Harary 2001. The Cohesiveness of
Blocks In Social Networks: Node Connectivity and Conditional Density.
\emph{Sociological Methodology} 31 (1) : 305-359.
}
\seealso{
Other flow:
\code{\link{dominator_tree}()},
\code{\link{edge_connectivity}()},
\code{\link{is_min_separator}()},
\code{\link{is_separator}()},
\code{\link{max_flow}()},
\code{\link{min_cut}()},
\code{\link{min_separators}()},
\code{\link{min_st_separators}()},
\code{\link{st_cuts}()},
\code{\link{st_min_cuts}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{flow}
\keyword{graphs}
|
