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

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.

Value

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

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 which are not unilaterally connected with one another. Consider, for instance, the graph $a->b<-c<-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.

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

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)

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$

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$

recursive: $v_1$ is connected to $v_2$ iff there exists a vertex sequence $v_a,...,v_z$ such that $v_1,v_a,...,v_z,v_2$ and $v_2,v_z,...,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.

Examples

Run this code

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

Run the code above in your browser using DataLab