




























Spectral graph sparsification has emerged as a powerful tool in the analysis of large-scale networks by reducing the overall number of edges, while maintaining a comparable graph Laplacian matrix. In this paper, we present an efficient algorithm for the construction of a new type of spectral sparsifier, the unweighted spectral sparsifier. Given a general undirected and unweighted graph $G = (V, E)$ and an integer $\ell < |E|$ (the number of edges in $E$), we compute an unweighted graph $H = (V, F)$ with $F \subset E$ and $|F| = \ell$ such that for every $x \in \mathbb{R}^{V}$ \[ {\displaystyle \frac{x^T L_G x}κ \leq x^T L_H x \leq x^T L_G x,} \] where $L_G$ and $L_H$ are the Laplacian matrices for $G$ and $H$, respectively, and $κ\geq 1$ is a slowly-varying function of $|V|, |E|$ and $\ell$. This work addresses the open question of the existence of unweighted graph sparsifiers for unweighted graphs. Additionally, our algorithm can efficiently compute unweighted graph sparsifiers for weighted graphs, leading to sparsified graphs that retain the weights of the original graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。