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)Any class of accepted graph format (see netdiffuseR-graphs).
Integer scalar. Degree of approximation. Bigger values increase precision (see details).
Logical scalar. When TRUE, it warns if the algorithm
performs less steps than required.
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 do
Iterate 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 .
sna::geodist(as.matrix(g))[[2]]
#> [,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
igraph::distances(
igraph::graph_from_adjacency_matrix(g, mode = "directed"),
mode = "out"
)
#> [,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