Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-25T19:16:37.416Z Has data issue: false hasContentIssue false
  • English
  • Français

Graph Partitioning via Adaptive Spectral Techniques

Published online by Cambridge University Press:  13 November 2009

AMIN COJA-OGHLAN
AMIN COJA-OGHLAN*
Affiliation:
School of Informatics, University of Edinburgh, Crichton Street, Edinburgh EH8 9AB, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 2 , March 2010 , pp. 227 - 284
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
[4]Bilu, Y. and Linial, N. (2004) Are stable instances easy? Preprint.Google 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
[22]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.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