sna (version 2.7)

component.dist: Calculate the Component Size Distribution of a Graph

Description

component.dist returns a list containing a vector of length n such that the ith element contains the number of components of graph \(G\) having size i, and a vector of length n giving component membership (where n is the graph order). Component strength is determined by the connected parameter; see below for details.

component.largest identifies the component(s) of maximum order within graph G. It returns either a logical vector indicating membership in a maximum component or the adjacency matrix of the subgraph of \(G\) induced by the maximum component(s), as determined by result. Component strength is determined as per component.dist.

Usage

component.dist(dat, connected=c("strong","weak","unilateral",
     "recursive"))
component.largest(dat, connected=c("strong","weak","unilateral",
     "recursive"), result = c("membership", "graph"), return.as.edgelist =
     FALSE)

Value

For component.dist, a list containing:

membership

A vector of component memberships, by vertex

csize

A vector of component sizes, by component

cdist

A vector of length |V(G)| with the (unnormalized) empirical distribution function of component sizes

If multiple input graphs are given, the return value is a list of lists.

For component.largest, either a logical vector of component membership indicators or the adjacency matrix/edgelist of the subgraph induced by the largest component(s) is returned. If multiple graphs were given as input, a list of results is returned.

Arguments

dat

one or more input graphs.

connected

a string selecting strong, weak, unilateral or recursively connected components; by default, "strong" components are used.

result

a string indicating whether a vector of membership indicators or the induced subgraph of the component should be returned.

return.as.edgelist

logical; if result=="graph", should the resulting structure be returned in edgelist form?

Author

Carter T. Butts

Details

Components are maximal sets of mutually connected vertices; depending on the definition of ``connected'' one employs, one can arrive at several types of components. Those supported here are as follows (in increasing order of restrictiveness):

1. weak: \(v_1\) is connected to \(v_2\) iff there exists a semi-path from \(v_1\) to \(v_2\) (i.e., a path in the weakly symmetrized graph)

2. unilateral: \(v_1\) is connected to \(v_2\) iff there exists a directed path from \(v_1\) to \(v_2\) or a directed path from \(v_2\) to \(v_1\)

3. strong: \(v_1\) is connected to \(v_2\) iff there exists a directed path from \(v_1\) to \(v_2\) and a directed path from \(v_2\) to \(v_1\)

4. recursive: \(v_1\) is connected to \(v_2\) iff there exists a vertex sequence \(v_a,\ldots,v_z\) such that \(v_1,v_a,\ldots,v_z,v_2\) and \(v_2,v_z,\ldots,v_a,v_1\) are directed paths

Note that the above definitions are distinct for directed graphs only; if dat is symmetric, then the connected parameter has no effect.

References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.

See Also

components, symmetrize, reachability geodist

Examples

g<-rgraph(20,tprob=0.06)   #Generate a sparse random graph

#Find weak components
cd<-component.dist(g,connected="weak")
cd$membership              #Who's in what component?
cd$csize                   #What are the component sizes?
                           #Plot the size distribution
plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h")  
lgc<-component.largest(g,connected="weak")  #Get largest component
gplot(g,vertex.col=2+lgc)  #Plot g, with component membership
                           #Plot largest component itself 
gplot(component.largest(g,connected="weak",result="graph"))

#Find strong components
cd<-component.dist(g,connected="strong")
cd$membership              #Who's in what component?
cd$csize                   #What are the component sizes?
                           #Plot the size distribution
plot(1:length(cd$cdist),cd$cdist/sum(cd$cdist),ylim=c(0,1),type="h")
lgc<-component.largest(g,connected="strong")  #Get largest component
gplot(g,vertex.col=2+lgc)  #Plot g, with component membership
                           #Plot largest component itself 
gplot(component.largest(g,connected="strong",result="graph"))