component.dist {sna}

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)

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?

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.

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.

Note

Unilaterally connected component partitions may not be well-defined, since it is possible for a given vertex to be unilaterally connected to two vertices that are not unilaterally connected with one another. Consider, for instance, the graph a \rightarrow b \leftarrow c \rightarrow d. In this case, the maximal unilateral components are ab and bcd, with vertex b properly belonging to both components. For such graphs, a unique partition of vertices by component does not exist, and we “solve” the problem by allocating each “problem vertex” to one of its components on an essentially arbitrary basis. (component.dist generates a warning when this occurs.) It is recommended that the unilateral option be avoided where possible.

Do not make the mistake of assuming that the subgraphs returned by component.largest are necessarily connected. This is usually the case, but depends upon the uniqueness of the largest component.

Author(s)

Carter T. Butts [e-mail]

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"))