We introduce a new notion of graph sparsificaiton 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 $\softOm$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. 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.
%0 Journal Article
%1 DBLP:journals/corr/abs-0808-4134
%A Spielman, Daniel A.
%A Teng, Shang-Hua
%D 2008
%J CoRR
%K eigenvalues graph.theory sparsification spectral.graph.theory
%T Spectral Sparsification of Graphs
%U http://arxiv.org/abs/0808.4134
%V abs/0808.4134
%X We introduce a new notion of graph sparsificaiton 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 $\softOm$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. 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.
@article{DBLP:journals/corr/abs-0808-4134,
abstract = {We introduce a new notion of graph sparsificaiton 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 $\softO{m}$, where $m$ is the number of edges in the original graph. This construction is a key component of a nearly-linear time algorithm for solving linear equations in diagonally-dominant matrcies. 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. },
added-at = {2011-03-29T00:38:55.000+0200},
author = {Spielman, Daniel A. and Teng, Shang-Hua},
bibsource = {DBLP, http://dblp.uni-trier.de},
biburl = {https://www.bibsonomy.org/bibtex/23fdd841acda82fa789193203447a03d6/ytyoun},
interhash = {b141d98b33dc29fdd418232c8b3a4c4e},
intrahash = {3fdd841acda82fa789193203447a03d6},
journal = {CoRR},
keywords = {eigenvalues graph.theory sparsification spectral.graph.theory},
timestamp = {2016-11-16T07:55:02.000+0100},
title = {Spectral Sparsification of Graphs},
url = {http://arxiv.org/abs/0808.4134},
volume = {abs/0808.4134},
year = 2008
}