Graph Sparsification by Effective Resistances

Random walks and electric networks

P. Doyle and J. Snell · 1984

Earlier work this paper cites.

Extensions of Lipschitz mappings into a Hilbert space

W. Johnson and J. Lindenstrauss · 1984

Earlier work this paper cites.

A new approach to the maximum flow problem

A. V. Goldberg and R. E. Tarjan · 1986

Earlier work this paper cites.

The electrical resistance of a graph captures its commute and cover times

A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky · 1989

Earlier work this paper cites.

Approximating s-t minimum cuts in O ~ ​ ( n 2 ) \tilde{O}(n^{2}) time

A. A. Benczúr and D. R. Karger · 1996

Earlier work this paper cites.

Spectral Graph Theory

F. R. K. Chung · 1997

Earlier work this paper cites.

Modern Graph Theory

B. Bollobas · 1998

Earlier work this paper cites.

Random vectors in the isotropic position

M. Rudelson · 1999

Earlier work this paper cites.

Graph embeddings and Laplacian eigenvalues

S. Guattery and G. L. Miller · 2000

Earlier work this paper cites.

Database-friendly random projections

D. Achlioptas · 2001

Cited alongside, same era.

Fast computation of low rank matrix approximations

D. Achlioptas and F. McSherry · 2001

Cited alongside, same era.

Fast monte-carlo algorithms for approximate matrix multiplication

P. Drineas and R. Kannan · 2001

Cited alongside, same era.

Algebraic Graph Theory

Chris Godsil and Gordon Royle · 2001

Cited alongside, same era.

Pass efficient algorithms for approximating large matrices

P. Drineas and R. Kannan · 2003

Cited alongside, same era.

Concentration-of-measure inequalities, 2003

G. Lugosi · 2003

Cited alongside, same era.

Fast monte-carlo algorithms for finding low-rank approximations

A fast random sampling algorithm for sparsifying matrices

S. Arora, E. Hazan, and S. Kale · 2006

Later among the works it cites.

Graph partitioning using single commodity flows

R. Khandekar, S. Rao, and U. Vazirani · 2006

Later among the works it cites.

Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

D. A. Spielman and S.-H. Teng · 2006

Later among the works it cites.

Genetic clustering of social networks using random walks

A. Firat, S. Chatterjee, and M. Yilmaz · 2007

Later among the works it cites.

Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation

F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens · 2007

Later among the works it cites.

Sampling from large matrices: An approach through geometric functional analysis