GraphMFPT: Compute mean first-passage time-based distance matrix

In SANTA: Spatial Analysis of Network Associations

Description

Using the mean first-passage time method, compute the distances between vertex pairs in an undirected graph, with or without edge weights.

Usage

GraphMFPT(g, v=V(g), edge.attr.weight=NULL, average.distances=TRUE)

Arguments

g	igraph object, the graph to work on.
v	igraph object or numeric vector, the vertices from which each distance is calculated.
edge.attr.weight	String, the name of the edge attribute to be used as weights along the edges. Greater weights indicate a stronger interaction between the two genes (this is the opposite to edge distances, where smaller distances indicate stronger interactions). If NULL then each edge is assumed to have a weight of 1.
average.distances	Logical, if TRUE then the distance from vertex A to B and the distance from vertex B to A are averaged to give a single distance. Otherwise, two different distances may be returned.

Details

The mean first-passage time from vertex A to vertex B is defined as the expected number of steps taken on a random walk emanating from vertex A until the first arrival at vertex B. This provides a method of measuring the distance between pairs of vertices that does not simply take into account the distance along the shortest path, but rather incorporates how well the two vertices are connected across multiple paths.

The mean first-passage time from vertex A to vertex B is not necessarily the same as the mean first-passage time from vertex B to vertex A. If a symmetric distance matrix is required, reciprocal distances can be averaged to give a single value for each vertex pair.

If a vertex pair is unconnected, then the distance between the vertices is Inf.

The distance from vertex A to vertex A is always 0.

Value

Numeric matrix, containing the mean first-passage time-derived vertex pair distance between each vertex in v and every vertex in g.

Author(s)

Alex J. Cornish [e-mail]

References

White, S. and Smyth, P. (2003). Algorithms for Estimating Relative Importance in Networks. Technical Report UCI-ICS 04-25.

See Also

GraphDiffusion, shortest.paths

Examples

# create a  and compute the mean first-passage time-based vertex pair distance matrix
g <- erdos.renyi.game(6, p.or.m=0.5, directed=FALSE)
GraphMFPT(g) 
plot(g, layout=layout.fruchterman.reingold)

Example output

Loading required package: igraph

Attaching package: 'igraph'

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union

         [,1]     [,2]     [,3]     [,4]     [,5]     [,6]
[1,] 0.000000 4.000000 4.695652 4.260870 8.173913 5.130435
[2,] 4.000000 0.000000 4.695652 4.260870 8.173913 5.130435
[3,] 4.695652 4.695652 0.000000 4.782609 9.565217 7.391304
[4,] 4.260870 4.260870 4.782609 0.000000 6.521739 6.086957
[5,] 8.173913 8.173913 9.565217 6.521739 0.000000 6.521739
[6,] 5.130435 5.130435 7.391304 6.086957 6.521739 0.000000

SANTA documentation built on Oct. 31, 2019, 3:21 a.m.