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 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` | one or more input graphs.
`connected` | a string selecting strong, weak, unilateral or recursively connected components; by default, `"strong"` components are used.

### 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 or a 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 and a 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,...,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.

### Value

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.

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

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

[Package sna version 1.1 Index]