approx_geodesic: Approximate Geodesic Distances

In USCCANA/diffusiontest: Analysis of Diffusion and Contagion Processes on Networks

Approximate Geodesic Distances

Description

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

Usage

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

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

Arguments

graph	Any class of accepted graph format (see netdiffuseR-graphs).
n	Integer scalar. Degree of approximation. Bigger values increase precision (see details).
warn	Logical scalar. When TRUE, it warns if the algorithm performs less steps than required.

Details

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).

1. Initialize the output ans(n, n)

2. For i=1 to i < n do

   1. Iterate through the edges of G^i, if ans has a zero value in the corresponding row+column, replace it with i

   2. next

3. 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.

Value

A sparse matrix of class dgCMatrix of size nnodes(graph)^2 with geodesic distances up to n.

Examples

# A very simple example -----------------------------------------------------
g <- ring_lattice(10, 3)
approx_geodesic(g, 6)
sna::geodist(as.matrix(g))[[2]]
igraph::distances(
  igraph::graph_from_adjacency_matrix(g, mode = "directed"),
  mode = "out"
)

USCCANA/diffusiontest documentation built on Sept. 4, 2023, 11:38 p.m.