Spectral Sparsification of Graphs
Citations Over TimeTop 1% of 2011 papers
Abstract
We introduce a new notion of graph sparsification based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time $O(m\log^{c}m)$, where m is the number of edges in the original graph and c is some absolute constant. This construction is a key component of a nearly linear time algorithm for solving linear equations in diagonally dominant matrices. Our sparsification algorithm makes use of a nearly linear time algorithm for graph partitioning that satisfies a strong guarantee: if the partition it outputs is very unbalanced, then the larger part is contained in a subgraph of high conductance.
Related Papers
- → Algebraic aspects of the normalized Laplacian(2016)49 cited
- → Laplacian dynamics on signed networks(2016)22 cited
- → New bounds for Laplacian energy(2020)1 cited
- → The Deformed Consensus Protocol: Extended Version(2013)2 cited
- Performance Analysis of Graph Laplacian Matrices in Detecting Protein Complexes(2012)