geodist: Fund the Numbers and Lengths of Geodesics Among Nodes in a...

In sna: Tools for Social Network Analysis

Fund the Numbers and Lengths of Geodesics Among Nodes in a Graph

Description

geodist uses a BFS to find the number and lengths of geodesics between all nodes of dat. Where geodesics do not exist, the value in inf.replace is substituted for the distance in question.

Usage

geodist(dat, inf.replace=Inf, count.paths=TRUE, predecessors=FALSE,
    ignore.eval=TRUE, na.omit=TRUE)

Arguments

dat	one or more input graphs.
inf.replace	the value to use for geodesic distances between disconnected nodes; by default, this is equal Inf.
count.paths	logical; should a count of geodesics be included in the returned object?
predecessors	logical; should a predecessor list be included in the returned object?
ignore.eval	logical; should edge values be ignored when computing geodesics?
na.omit	logical; should NA-valued edges be removed?

Details

This routine is used by a variety of other functions; many of these will allow the user to provide manually precomputed geodist output so as to prevent expensive recomputation. Note that the choice of infinite path length for disconnected vertex pairs is non-canonical (albeit common), and some may prefer to simply treat these as missing values. geodist (without loss of generality) treats all paths as directed, a fact which should be kept in mind when interpreting geodist output.

By default, geodist ignores edge values (except for NAed edges, which are dropped when na.omit==TRUE). Setting ignore.eval=FALSE will change this behavior, with edge values being interpreted as distances; where edge values reflect proximity or tie strength, transformation may be necessary. Edge values should also be non-negative. Because the valued-case algorithm is significantly slower than the unvalued-case algorithm, ignore.eval should be set to TRUE wherever possible.

Value

A list containing:

counts	If count.paths==TRUE, a matrix containing the number of geodesics between each pair of vertices
gdist	A matrix containing the geodesic distances between each pair of vertices
predecessors	If predecessors, a list whose ith element is a list of vectors, the jth of which contains the intervening vertices on all shortest paths from i to j

Author(s)

Carter T. Butts [e-mail]

References

Brandes, U. (2000). “Faster Evaluation of Shortest-Path Based Centrality Indices.” Konstanzer Schriften in Mathematik und Informatik, 120.

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

See Also

component.dist, components

Examples

#Find geodesics on a random graph
gd<-geodist(rgraph(15))

#Examine the number of geodesics
gd$counts

#Examine the geodesic distances
gd$gdist

sna documentation built on Sept. 11, 2024, 8:45 p.m.