No CrossRef data available.
Article contents
Graph Partitioning via Adaptive Spectral Techniques
Published online by Cambridge University Press: 13 November 2009
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a ‘latent’ partition V1,. . ., Vk. Moreover, consider a ‘density matrix’ Ɛ = (Ɛvw)v, sw∈V such that, for v ∈ Vi and w ∈ Vj, the entry Ɛvw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: Ɛ approximates the adjacency matrix of G in the operator norm, for vertices v ∈ Vi, w ∈ Vj ≠ Vi the corresponding column vectors Ɛv, Ɛw are separated, and G is sufficiently ‘regular’ with respect to the matrix Ɛ. This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2009
References
[1]Alon, N. and Kahale, N. (1997) A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26 1733–1748.CrossRefGoogle Scholar
[2]Alon, N., Krivelevich, M. and Sudakov, B. (1998) Finding a large hidden clique in a random graph. Random Struct. Alg. 13 457–466.3.0.CO;2-W>CrossRefGoogle Scholar
[3]Azar, Y., Fiat, A., Karlin, A. R., McSherry, F. and Saia, J. (2001) Spectral analysis of data. In Proc. 33rd STOC, pp. 619–626.CrossRefGoogle Scholar
[5]Bollobás, B. and Scott, A. D. (2004) Max cut for random graphs with a planted partition. Combin. Probab. Comput. 13 451–474.Google Scholar
[6]Boppana, R. (1987) Eigenvalues and graph bisection: An average-case analysis. In Proc. 28th FOCS, pp. 280–285.CrossRefGoogle Scholar
[7]Bui, T., Chaudhuri, S., Leighton, T. and Sipser, M. (1987) Graph bisection algorithms with good average case behavior. Combinatorica 7 171–191.CrossRefGoogle Scholar
[8]Chen, H. and Frieze, A. (1996) Coloring bipartite hypergraphs. In Proc. 5th IPCO, pp. 345–358.CrossRefGoogle Scholar
[9]Chung, F. and Graham, R. (2002) Sparse quasi-random graphs. Combinatorica 22 217–244.CrossRefGoogle Scholar
[10]Coja-Oghlan, A. (2005) A spectral heuristic for bisecting random graphs. In Proc. 16th SODA, pp. 850–859.Google Scholar
[11]Coja-Oghlan, A. (2005) Spectral techniques, semidefinite programs, and random graphs. Habilitation thesis, Humboldt University of Berlin.Google Scholar
[12]Dasgupta, A., Hopcroft, J. E. and McSherry, F. (2004) Spectral analysis of random graphs with skewed degree distributions. In Proc. 45th FOCS, pp. 529–537.CrossRefGoogle Scholar
[13]Dasgupta, A., Hopcroft, J. E., Kannan, R. and Mitra, P. (2006) Spectral partitioning by recursive partitioning. In Proc. 14th ESA, pp. 256–267.Google Scholar
[14]Ding, C. H. Q. (2002) Analysis of gene expression profiles: Class discovery and leaf ordering. In Proc. 6th International Conference on Computational Biology, pp. 127–136CrossRefGoogle Scholar
[15]Dyer, M. and Frieze, A. (1989) The solution of some NP-hard problems in polynomial expected time. J. Algorithms 10 451–489.CrossRefGoogle Scholar
[16]Feige, U. and Kilian, J. (2001) Heuristics for semirandom graph problems. J. Comput. Syst. Sci. 63 639–671.CrossRefGoogle Scholar
[17]Feige, U. and Ofek, E. (2005) Spectral techniques applied to sparse random graphs. Random Struct. Alg. 27 251–275.CrossRefGoogle Scholar
[18]Flaxman, A. (2003) A spectral technique for random satisfiable 3CNF formulas. In Proc. 14th SODA, pp. 357–363.Google Scholar
[19]Frieze, A. and Kannan, R. (1999) Quick approximation to matrices and applications. Combinatorica 19 175–220.CrossRefGoogle Scholar
[20]Füredi, Z. and Komloś, J. (1981) The eigenvalues of random symmetric matrices. Combinatorica 1 233–241.Google Scholar
[21]Goerdt, A. and Lanka, A. (2004) On the hardness and easiness of random 4-SAT formulas. In Proc. 15th ISAAC, pp. 470–483.CrossRefGoogle Scholar
[23]Jerrum, M. and Sorkin, G. (1998) The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82 155–175.CrossRefGoogle Scholar
[24]Friedman, J., Kahn, J. and Szemerédi, E. (1989) On the second eigenvalue in random regular graphs. In Proc. 21st STOC, pp. 587–598.CrossRefGoogle Scholar
[25]Kannan, R., Vempala, S. and Vetta, A. (2004) On clusterings: Good, bad and spectral. J. Assoc. Comput. Mach. 51 497–515.CrossRefGoogle Scholar
[26]Krivelevich, M. and Sudakov, B. (2003) The largest eigenvalue of sparse random graphs. Combin. Probab. Comput. 12 61–72.Google Scholar
[27]Krivelevich, M. and Sudakov, B. (2006) Pseudo-random graphs. In More Sets, Graphs and Numbers (Gyori, E., Katona, G. O. H. and Lovasz, L., eds), Vol. 15 of Bolyai Society Mathematical Studies, pp. 199–262.CrossRefGoogle Scholar
[28]McSherry, F. (2001) Spectral partitioning of random graphs. In Proc. 42nd FOCS, pp. 529–537.CrossRefGoogle Scholar
[29]Pothen, A., Simon, H. D. and Kang-Pu, L. (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11 430–452.CrossRefGoogle Scholar
[30]Schloegel, K., Karypis, G. and Kumar, V. (2000) Graph partitioning for high performance scientific simulations. In CRPC Parallel Computation Handbook (Dongarra, J., Foster, I., Fox, G., Kennedy, K. and White, A., eds), Morgan Kaufmann.Google Scholar
[31]Spielman, D. A. and Teng, S.-H. (1996) Spectral partitioning works: Planar graphs and finite element meshes. In Proc. 36th FOCS, pp. 96–105.CrossRefGoogle Scholar
[32]Subramanian, C. R. and Veni Madhavan, C. E. (2002) General partitioning on random graphs. J. Algorithms 42 153–172.CrossRefGoogle Scholar
You have
Access
- 81
- Cited by