cutpoints: Identify the Cutpoints of a Graph or Digraph

In sna: Tools for Social Network Analysis

Identify the Cutpoints of a Graph or Digraph

Description

cutpoints identifies the cutpoints of an input graph. Depending on mode, either a directed or undirected notion of “cutpoint” can be used.

Usage

cutpoints(dat, mode = "digraph", connected = c("strong","weak","recursive"),
    return.indicator = FALSE)

Arguments

dat	one or more input graphs.
mode	"digraph" for directed graphs, or "graph" for undirected graphs.
connected	string indicating the type of connectedness rule to apply (only relevant where mode=="digraph").
return.indicator	logical; should the results be returned as a logical (TRUE/FALSE) vector of indicators, rather than as a vector of vertex IDs?

Details

A cutpoint (also known as an articulation point or cut-vertex) of an undirected graph, G is a vertex whose removal increases the number of components of G. Several generalizations to the directed case exist. Here, we define a strong cutpoint of directed graph G to be a vertex whose removal increases the number of strongly connected components of G (see component.dist). Likewise, weak and recursive cutpoints of G are those vertices whose removal increases the number of weak or recursive cutpoints (respectively). By default, strong cutpoints are used; alternatives may be selected via the connected argument.

Cutpoints are of particular interest when seeking to identify critical positions in flow networks, since their removal by definition alters the connectivity properties of the graph. In this context, cutpoint status can be thought of as a primitive form of centrality (with some similarities to betweenness).

Cutpoint computation is significantly faster for the undirected case (and for the weak/recursive cases) than for the strong directed case. While calling cutpoints with mode="digraph" on an undirected graph will give the same answer as mode="graph", it is thus to one's advantage to use the latter form. Do not, however, employ mode="graph" with directed data, unless you enjoy unpredictable behavior.

Value

A vector of cutpoints (if return.indicator==FALSE), or else a logical vector indicating cutpoint status for each vertex.

Author(s)

Carter T. Butts [e-mail]

References

Berge, Claude. (1966). The Theory of Graphs. New York: John Wiley and Sons.

See Also

component.dist, bicomponent.dist, betweenness

Examples

#Generate some sparse random graph
gd<-rgraph(25,tp=1.5/24)                               #Directed
gu<-rgraph(25,tp=1.5/24,mode="graph")                  #Undirected

#Calculate the cutpoints (as an indicator vector)
cpu<-cutpoints(gu,mode="graph",return.indicator=TRUE)
cpd<-cutpoints(gd,return.indicator=TRUE)

#Plot the result
gplot(gu,gmode="graph",vertex.col=2+cpu)
gplot(gd,vertex.col=2+cpd)

#Repeat with alternate connectivity modes
cpdw<-cutpoints(gd,connected="weak",return.indicator=TRUE)
cpdr<-cutpoints(gd,connected="recursive",return.indicator=TRUE)

#Visualize the difference
gplot(gd,vertex.col=2+cpdw)
gplot(gd,vertex.col=2+cpdr)

sna documentation built on Sept. 11, 2024, 8:45 p.m.