# approx_geodesic: Approximate Geodesic Distances In USCCANA/netdiffuseR: Analysis of Diffusion and Contagion Processes on Networks

## Description

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

## Usage

 ```1 2 3``` ```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

 ```1 2 3 4 5 6 7 8``` ```# 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/netdiffuseR documentation built on March 14, 2020, 11:38 a.m.