EffR: Effective resistances calculator

In simplifyNet: Network Sparsification

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)

simplifyNet documentation built on Nov. 15, 2022, 5:05 p.m.