Computes approximate geodesic distance matrix using graph powers and keeping the amount of memory used low.
1 2 3
Any class of accepted graph format (see
Integer scalar. Degree of approximation. Bigger values increase precision (see details).
Logical scalar. When
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,
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
Depending on the graph size and density,
can be compared to that of
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
i < n do
Iterate through the edges of
ans has a zero
value in the corresponding row+column, replace it with
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
A sparse matrix of class
dgCMatrix of size
nnodes(graph)^2 with geodesic distances up to
1 2 3 4 5 6 7 8
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.