Approximations for the isoperimetric and spectral profile of graphs and related parameters
Approximations for the isoperimetric and spectral profile of graphs and related parameters
复制标题
图形和相关参数的等周和光谱轮廓的近似值
DOI：
10.1145/1806689.1806776
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Tetali
中科院分区：
文献类型：
--
作者：
P. Raghavendra;David Steurer;P. Tetali
图的光谱曲线是其雷利商的经典通知的自然概括。最大程度地减少了G在适当的概率度量上，在最多支持的vectors vectors的Laplacian矩阵的光谱间隙最小化（从变化表征中）。 g是a函数λ<sub> g </sub>：[0,1/2] - > r定义为：λ<sub> g </sub>（δ）def = min <sub> <sub> <sub>x∈R<sup > v </sup> d（suppp（x））≤Δ</sub> </sub>（∑g <sub> ij </sub>） </sub>）<sup> 2 </sup>）/（∑ <sub> i </sub> d <sub> i </sub> x <sub> i </sub> i </sub> <Sup> 2 </sup >）其中g <sub> ij </sub>是图中边缘（i，j）的重量，d <ub> i </sub>是顶点的程度i和d（\ supp（x））是向量X的顶点的边缘的分数，而光谱概况的概念在马尔可夫链中具有许多应用，它也与其等值材料密切相关。 ，光谱曲线是在这项工作中近似小集的边缘扩展的问题。 λ<sub> g </sub>（δ）。与[18]中的独特游戏猜想密切相关，我们扩展了技术，以获得对对角线占主导地位的特征值问题的近似算法。
The spectral profile of a graph is a natural generalization of the classical notion of its Rayleigh quotient. Roughly speaking, given a graph G, for each 0< δ < 1, the spectral profile Λ<sub>G</sub>(δ) minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of G over vectors with support at most δ over a suitable probability measure. Formally, the spectral profile Λ<sub>G</sub> of a graph G is a function Λ<sub>G</sub> : [0,1/2] -> R defined as: Λ<sub>G</sub>(δ) def= min<sub><sub>x∈ R<sup>V</sup>d(supp(x))≤ δ</sub></sub> (∑g<sub>ij</sub> (x<sub>i</sub>-x<sub>j</sub>)<sup>2</sup>)/(∑<sub>i</sub> d<sub>i</sub> x<sub>i</sub><sup>2</sup>) where g<sub>ij</sub> is the weight of the edge (i,j) in the graph, d<sub>i</sub> is the degree of vertex i, and d(\supp(x)) is the fraction of edges incident on vertices within the support of vector x. While the notion of the spectral profile has numerous applications in Markov chain, it is also is closely tied to its isoperimetric profile of a graph. Specifically, the spectral profile is a relaxation for the problem of approximating edge expansion of small sets in graphs. In this work, we obtain an efficient algorithm that yields a log(1/δ)-factor approximation for the value of Λ<sub>G</sub>(δ). By virtue of its connection to edge-expansion, we also obtain an algorithm for the problem of approximating edge expansion of small linear sized sets in a graph. This problem was recently shown to be intimately connected to the Unique Games Conjecture in [18]. Finally, we extend the techniques to obtain approximation algorithms with similar guarantees for restricted eigenvalue problems on diagonally dominant matrices.