Graph partitioning via adaptive spectral techniques

摘要: In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a whose vertex set has ‘latent’ partition V1,. . ., Vk. Moreover, consider ‘density matrix’ Ɛ (Ɛvw)v, sw∈V such that, v ∈ Vi and w Vj, entry Ɛvw is fraction all possible Vi−Vj-edges that are actually present in G. We show on input (G, k) Vk can (very nearly) recovered polynomial time via methods, provided following holds: approximates adjacency matrix operator norm, vertices Vi, Vj ≠ corresponding column vectors Ɛv, Ɛw separated, sufficiently ‘regular’ with respect to Ɛ. This result particular applies sparse graphs bounded average degree as n #V → ∞, it various consequences partitioning random graphs.