EffRSparse {simplifyNet}

Sparsification through edge sampling via effective resistances

Description

Sparsify an undirected network by sampling edges proportional to w_e * R_e where w_e is the weight of edge e and R_e is the effective resistance of edge e.
Approximately preserves the graph Laplacian, L, with increasing fidelity as the number of samples taken increases.

Usage

EffRSparse(network, q, effR, seed, n)

Arguments

network

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

q

The numbers of samples taken. The fidelity to the original network increases as the number of samples increases, but decreases the sparseness.

effR

Effective resistances corresponding to each edge. Should be in the same order as "weight".

seed

Set the seed to reproduce results of random sampling.

n

The number of nodes in the network. Default is the max node index of the edge list.

Details

The performance of this method is dependent on the size of the network and fidelity of the effective resistance approximation. The network should be "sufficiently large."
For more details, see: https://epubs.siam.org/doi/epdf/10.1137/080734029

Value

A sparsified network, H, edge list where the number of edges is dependent on the number of samples taken, q.

Author(s)

Daniel A. Spielman,

Alexander Mercier

References

Spielman, D. A., & Srivastava, N. (2011). Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6), 1913-1926.

Examples

#Generate random ER graph with uniformly random edge weights
g = igraph::erdos.renyi.game(100, 0.1)
igraph::E(g)$weight <- runif(length(igraph::E(g)))
#Approximate effective resistances
effR = simplifyNet::EffR(g)
#Use effective resistances to create spectral sparsifier by edge sampling
S = simplifyNet::EffRSparse(g, q = 200, effR = effR, seed = 150)
sg = simplifyNet::net.as(S, net.to="igraph", directed=FALSE)
igraph::ecount(sg)/igraph::ecount(g)#fraction of edges in the sparsifier