sna (version 2.3-2)

reachability: Find the Reachability Matrix of a Graph

Description

reachability takes one or more (possibly directed) graphs as input, producing the associated reachability matrices.

Usage

reachability(dat, geodist.precomp=NULL)

Arguments

dat
one or more graphs (directed or otherwise).
geodist.precomp
optionally, a precomputed geodist object.

Value

A reachability matrix

Details

For a digraph $G=(V,E)$ with vertices $i$ and $j$, let $P_ij$ represent a directed $ij$ path. Then the graph

$$ R = \left(V\left(G\right),\left\{\left(i,j\right):i,j \in V\left(G\right), P_{ij} \in G\right\}\right)$$

is said to be the reachability graph of $G$, and the adjacency matrix of $R$ is said to be $G$'s reachability matrix. (Note that when $G$ is undirected, we simply take each undirected edge to be bidirectional.) Vertices which are adjacent in the reachability graph are connected by one or more directed paths in the original graph; thus, structural equivalence classes in the reachability graph are synonymous with strongly connected components in the original structure.

Bear in mind that -- as with all matters involving connectedness -- reachability is strongly related to size and density. Since, for any given density, almost all structures of sufficiently large size are connected, reachability graphs associated with large structures will generally be complete. Measures based on the reachability graph, then, will tend to become degenerate in the large $|V(G)|$ limit (assuming constant positive density).

References

Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

See Also

geodist

Examples

Run this code
#Find the reachability matrix for a sparse random graph
g<-rgraph(10,tprob=0.15)
rg<-reachability(g)
g  #Compare the two structures
rg

#Compare to the output of geodist
all(rg==(geodist(g)$counts>0))

Run the code above in your browser using DataLab