EffRSparse {simplifyNet} | R Documentation |
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 |
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