EffR {simplifyNet}

Effective resistances calculator

Description

Calculate or approximate the effective resistances of an inputted, undirected graph. There are three methods.
(1) 'ext' which exactly calculates the effective resistances (WARNING! Not ideal for large graphs).
(2) 'spl' which approximates the effective resistances of the inputted graph using the original Spielman-Srivastava algorithm.
(3) 'kts' which approximates the effective resistances of the inputted graph using the implementation by Koutis et al. (ideal for large graphs where memory usage is a concern).
The relative fidelity of the approximation methods is governed by the variable epsilon.

Usage

EffR(network, epsilon = 0.1, type = "kts", tol = 1e-10)

Arguments

network

Weighted adjacency matrix, weighted igraph network, or edge list formatted | n1 | n2 | weight | with colnames c("n1", "n2", "weight").

epsilon

Variable epsilon governs the relative fidelity of the approximation methods 'spl' and 'kts'. The smaller the value the greater the fidelity of the approximation. Default value is 0.1.

type

There are three methods.
(1) 'ext' which exactly calculates the effective resistances (WARNING! Not ideal for large graphs).
(2) 'spl' which approximates the effective resistances of the inputted graph using the original Spielman-Srivastava algorithm.
(3) 'kts' which approximates the effective resistances of the inputted graph using the implementation by Koutis et al. (ideal for large graphs where memory usage is a concern).

tol

Tolerance for the linear algebra (conjugate gradient) solver to find the effective resistances. Default value is 1e-10.

Details

The fidelity of the effective resistance approximation decreases with a decrease in epsilon. However, it is more important for sparsification by effective resistances that the approximations be roughly equivalent relative to one another, as they will be normalized in a probability distribution where exact values are not needed.
The number of edges contained in the sparsifier will be less than or equal to the number of samples taken, q.

Value

Return either exact or approximate effective resistances for each edge in the same order as "weight" in the edge list.

Author(s)

Alexander Mercier

References

Spielman, D. A., & Srivastava, N. (2011). Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6), 1913-1926.
Koutis, I., Miller, G. L., & Peng, R. (2014). Approaching optimality for solving SDD linear systems. SIAM Journal on Computing, 43(1), 337-354.

Examples

E_List = matrix(c(1,1,2,2,3,3,1,1,1), 3, 3) #Triangle graph, \eqn{K_3}, with edge weights equal to 1
effR = simplifyNet::EffR(E_List, epsilon = 0.1, type = 'kts', tol = 1e-10)