social.all.paths: All paths between two nodes

In social: Social Autocorrelation

Description

Estimate all the possible paths between two nodes in a simple graph using the stochastic method described by Roberts & Kroese (2007).

Usage

social.all.paths(A, start.node, end.node, max.depth = nrow(A), 
  n.pilot = 5000, n.estimate = 10000)

Arguments

A	a (possibly weighted) adjacency matrix.
start.node	the index of the vertex from which the paths will be calculated.
end.node	the index of the vertex to which the paths will be calculated.
max.depth	the maximum length of the paths to the returned.
n.pilot	the number of naive paths to generate (see Roberts & Kroese, 2007).
n.estimate	the number of paths to generate (see Roberts & Kroese, 2007).

Value

An estimate of all the unique paths between start.node and end.node as an nrow(A)xN matrix, padded with zeros.

References

Roberts, B. & Kroese, D.P. (2007) Estimating the number of s-t paths in a graph. Journal of Graph Algorithms and Applications 11(1), 195-214.

Examples

# Using the data from Figure 1 in Roberts & Kroese (2007)
A = matrix(c(0,1,0,1,0,
             1,0,0,1,1,
             0,0,0,1,1,
             1,1,1,0,0,
             0,1,1,0,0), nrow=5)
paths = social.all.paths(A, 1, 5)

social documentation built on May 2, 2019, 12:36 p.m.