Computes approximate geodesic distance matrix using graph powers and keeping the amount of memory used low.

approx_geodesic(graph, n = 6L, warn = FALSE) approx_geodist(graph, n = 6L, warn = FALSE)

graph | Any class of accepted graph format (see |
---|---|

n | Integer scalar. Degree of approximation. Bigger values increase precision (see details). |

warn | Logical scalar. When |

A sparse matrix of class `dgCMatrix`

of size
`nnodes(graph)^2`

with geodesic distances up to `n`

.

While both igraph and sna offer very good and computationally
efficient routines for computing geodesic distances, both functions return
dense matrices, i.e. not sparse, which can be troublesome. Furthermore,
from the perspective of social network analysis, path lengths of more than 6 steps,
for example, may not be meaningful, or at least, relevant for the researcher.
In such cases, `approx_geodesic`

serves as a solution to this problem,
computing geodesics up to the number of steps, `n`

, desired, hence,
if `n = 6`

, once the algorithm finds all paths of 6 or less steps it
will stop, returning a sparse matrix with zeros for those pairs of
vertices for which it was not able to find a path with less than `n`

steps.

Depending on the graph size and density, `approx_geodesic`

's performance
can be compared to that of `sna::geodist`

. Although,
as `n`

increases, `geodist`

becomes a better alternative.

The algorithm was implemented using power graphs. At each itereation i the
power graph of order `i`

is computed, and its values are compared
to the current values of the geodesic matrix (which is initialized in zero).

Initialize the output

`ans(n, n)`

For

`i=1`

to`i < n`

doIterate through the edges of

`G^i`

, if`ans`

has a zero value in the corresponding row+column, replace it with`i`

next

Replace all diagonal elements with a zero and return.

This implementation can be more memory efficient that the aforementioned ones, but at the same time it can be significant slower.

`approx_geodist`

is just an allias for `approx_geodesic`

.

# A very simple example ----------------------------------------------------- g <- ring_lattice(10, 3) approx_geodesic(g, 6)#> 10 x 10 sparse Matrix of class "dgCMatrix" #> #> [1,] . 1 1 1 2 2 2 3 3 3 #> [2,] 3 . 1 1 1 2 2 2 3 3 #> [3,] 3 3 . 1 1 1 2 2 2 3 #> [4,] 3 3 3 . 1 1 1 2 2 2 #> [5,] 2 3 3 3 . 1 1 1 2 2 #> [6,] 2 2 3 3 3 . 1 1 1 2 #> [7,] 2 2 2 3 3 3 . 1 1 1 #> [8,] 1 2 2 2 3 3 3 . 1 1 #> [9,] 1 1 2 2 2 3 3 3 . 1 #> [10,] 1 1 1 2 2 2 3 3 3 .#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [1,] 0 1 1 1 2 2 2 3 3 3 #> [2,] 3 0 1 1 1 2 2 2 3 3 #> [3,] 3 3 0 1 1 1 2 2 2 3 #> [4,] 3 3 3 0 1 1 1 2 2 2 #> [5,] 2 3 3 3 0 1 1 1 2 2 #> [6,] 2 2 3 3 3 0 1 1 1 2 #> [7,] 2 2 2 3 3 3 0 1 1 1 #> [8,] 1 2 2 2 3 3 3 0 1 1 #> [9,] 1 1 2 2 2 3 3 3 0 1 #> [10,] 1 1 1 2 2 2 3 3 3 0#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [1,] 0 1 1 1 2 2 2 3 3 3 #> [2,] 3 0 1 1 1 2 2 2 3 3 #> [3,] 3 3 0 1 1 1 2 2 2 3 #> [4,] 3 3 3 0 1 1 1 2 2 2 #> [5,] 2 3 3 3 0 1 1 1 2 2 #> [6,] 2 2 3 3 3 0 1 1 1 2 #> [7,] 2 2 2 3 3 3 0 1 1 1 #> [8,] 1 2 2 2 3 3 3 0 1 1 #> [9,] 1 1 2 2 2 3 3 3 0 1 #> [10,] 1 1 1 2 2 2 3 3 3 0