# component.dist: Calculate the Component Size Distribution of a Graph In sna: Tools for Social Network Analysis

 component.dist 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 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`.

### 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, `"strong"` components are used. `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 `result=="graph"`, should the resulting structure be returned in edgelist form?

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

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

### Author(s)

Carter T. Butts buttsc@uci.edu

### References

West, D.B. (1996). Introduction to Graph Theory. Upper Saddle River, N.J.: Prentice Hall.

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

sna documentation built on June 1, 2022, 9:06 a.m.