sna (version 0.41)

component.dist: Calculate the Component Size Distribution of a Graph

Description

component.dist returns a data frame 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.

Usage

component.dist(dat, connected=c("strong","weak","unilateral",
     "recursive"))

Arguments

dat

A single nxn adjacency matrix

connected

A string selecting strong, weak, unilateral or recursively connected components; by default, "strong" components are used.

Value

• A data frame 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

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 \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.

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$ora 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$anda 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.

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