resistance_sparsify

resistance_sparsify(graph: TGraph, target_mean_degree, ensure_connected=True, epsilon=0.01)[source]

Sparsify a graph to have a target mean degree using effective resistance based sampling

Parameters:

  • graph – input graph

  • target_mean_degree – desired mean degree after sparsification

  • ensure_connected – if True, first add edges of a maximum spanning tree based on the resistance weights to ensure that the sparsified graph remains connected if the input graph is connected

  • epsilon – tolerance for effective resistance computation

Returns:

sparsified graph

This algorithm is based on the method of

D. A. Spielman and N. Srivastava. “Graph sparsification by effective resistances”. SIAM Journal on Computing 40.6 (2011), pp. 1913–1926.

However, a fixed number of edges are sampled without replacement, and optionally a maximum spanning tree is kept to ensure the connectedness of the sparsified graph.