vertex.connectivity

0th

Percentile

Vertex connectivity.

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

Keywords
graphs
Usage
vertex.connectivity(graph, source=NULL, target=NULL, checks=TRUE)
vertex.disjoint.paths(graph, source, target)
graph.cohesion(graph, checks=TRUE)
Arguments
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 connec
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 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.

Value

  • A scalar real value.

concept

  • Vertex connectivity
  • Vertex-disjoint paths
  • Graph cohesion

References

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

See Also

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

Aliases
  • vertex.connectivity
  • vertex.disjoint.paths
  • graph.cohesion
Examples
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)
Documentation reproduced from package igraph, version 0.5.5-3, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.