Sparsification of Graphs

[chebee7i]

It might be nice to get some functions in NetworkX for sparsifying graphs. cut sparsification and spectral sparsification are two options. For example,

http://arxiv.org/abs/0808.4134

Spectral Sparsification of Graphs Daniel A. Spielman, Shang-Hua Teng

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.

[jreback]

did u mean to put this in the pandas tracker? this is way out of scope

[chebee7i]

Pfft...sorry, wrong project.