component.dist {sna} | R Documentation |
component.dist
returns a list containing a vector of length n such that the ith element contains the number of components of G having size i, and a vector of length n giving component membership. Component strength is determined by the connected
parameter; see below for details.
component.dist(dat, connected=c("strong","weak","unilateral", "recursive"))
dat |
one or more input graphs. |
connected |
a string selecting strong, weak, unilateral or recursively connected components; by default, "strong" components are used. |
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.
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.
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.
Carter T. Butts buttsc@uci.edu
West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.
components
, symmetrize
, reachability
geodist
g<-rgraph(20,tprob=0.075) #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") #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")