edge.connectivity

0th

Percentile

Edge connectivity.

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

Keywords
graphs
Usage
edge.connectivity(graph, source=NULL, target=NULL, checks=TRUE)
edge.disjoint.paths(graph, source, target)
graph.adhesion(graph, checks=TRUE)
Arguments
graph
The input graph.
source
The id of the source vertex, for edge.connectivity it can be NULL, see details below.
target
The id of the target vertex, for edge.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 edge connecti
Details

The edge connectivity of a pair of vertices (source and target) is the minimum number of edges needed to remove to eliminate all (directed) paths from source to target. edge.connectivity calculates this quantity if both the source and target arguments are given (and not NULL).

The edge connectivity of a graph is the minimum of the edge connectivity of every (ordered) pair of vertices in the graph. edge.connectivity calculates this quantity if neither the source nor the target arguments are given (ie. they are both NULL).

A set of edge disjoint paths between two vertices is a set of paths between them containing no common edges. The maximum number of edge disjoint paths between two vertices is the same as their edge connectivity.

The adhesion of a graph is the minimum number of edges needed to remove to obtain a graph which is not strongly connected. This is the same as the edge connectivity of the graph.

The three functions documented on this page calculate similar properties, more precisely the most general is edge.connectivity, the others are included only for having more descriptive function names.

Value

  • A scalar real value.

concept

  • Edge connectivity
  • Edge-disjoint paths
  • Graph adhesion

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, vertex.connectivity, vertex.disjoint.paths, graph.cohesion

Aliases
  • edge.connectivity
  • edge.disjoint.paths
  • graph.adhesion
Examples
g <- barabasi.game(100, m=1)
g2 <- barabasi.game(100, m=5)
edge.connectivity(g, 99, 0)
edge.connectivity(g2, 99, 0)
edge.disjoint.paths(g2, 99, 0)

g <- erdos.renyi.game(50, 5/50)
g <- as.directed(g)
g <- subgraph(g, subcomponent(g, 1))
graph.adhesion(g)
Documentation reproduced from package igraph, version 0.5.2-2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.