component.dist {sna} | R Documentation |
Calculate the Component Size Distribution of a Graph
Description
component.dist
returns a list containing a vector of length n
such that the i
th element contains the number of components of graph 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 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, |
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 |
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
:is connected to
iff there exists a semi-path from
to
(i.e., a path in the weakly symmetrized graph)
-
unilateral
:is connected to
iff there exists a directed path from
to
or a directed path from
to
-
strong
:is connected to
iff there exists a directed path from
to
and a directed path from
to
-
recursive
:is connected to
iff there exists a vertex sequence
such that
and
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 . In this case, the maximal unilateral components are
and
, with vertex
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 buttsc@uci.edu
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"))