Calculate the Component Size Distribution of a Graph
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.
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)dat |
one or more input graphs. |
connected |
a string selecting strong, weak, unilateral or recursively connected components; by default, |
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 |
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.
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.
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->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.
Carter T. Butts buttsc@uci.edu
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
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"))Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.