Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-21T12:50:57.907Z Has data issue: false hasContentIssue false
  • English
  • Français

A Simple SVD Algorithm for Finding Hidden Partitions

Part of: Combinatorial probability Algorithms - Computer Science Theory of computing

Published online by Cambridge University Press:  09 October 2017

VAN VU
VAN VU*
Affiliation:
Department of Mathematics, Yale, New Haven, CT 06520, USA (e-mail [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Finding a hidden partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a hidden clique, finding a hidden colouring, finding a hidden bipartition, etc.

In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.

MSC classification

Primary: 68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Secondary: 68W20: Randomized algorithms 60C05: Combinatorial probability
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 1 , January 2018 , pp. 124 - 140
Copyright
Copyright © Cambridge University Press 2017 

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., McSherry, F. and Saia, J. (2001) Spectral analysis of data. In STOC '1: Proc. 33rd Annual ACM Symposium on Theory of Computing, ACM, pp. 619–626.CrossRefGoogle Scholar
[4] Bai, Z. and Silverstein, J. W. (2009) Spectral Analysis of Large Dimensional Random Matrices, Springer.Google Scholar
[5] Bhatia, R. (1997) Matrix Analysis, Vol. 169 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[6] Blum, A. and Spencer, J. (1995) Coloring random and semi-random k-colorable graphs. J. Algorithms 19 204–234.CrossRefGoogle Scholar
[7] Boppana, R. B. (1987) Eigenvalues and graph bisection: An average-case analysis. In SFCS '87: Proc. 28th Annual Symposium on Foundations of Computer Science, ACM, pp. 280–285.CrossRefGoogle Scholar
[8] Bui, T. N., Chaudhuri, S., Leighton, F. T. and Sipser, M. (1987) Graph bisection algorithms with good average case behavior. Combinatorica 7 171–191.CrossRefGoogle Scholar
[9] Chin, P., Rao, A. and Vu, V. (2015) Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. Proc. of Machine Learning Research 40 391–423.Google Scholar
[10] Coja-Oghlan, A. (2010) Graph partitioning via adaptive spectral techniques. Combin. Probab. Comput. 19 227–284.CrossRefGoogle Scholar
[11] Condon, A. and Karp, R. M. (2001) Algorithms for graph partitioning on the planted partition model. Random Struct. Alg. 18 116–140.3.0.CO;2-2>CrossRefGoogle Scholar
[12] Davis, C. and Kahan, W. M. (1970) The rotation of eigenvectors by a perturbation III. SIAM J. Numer. Anal. 7 1–46.CrossRefGoogle Scholar
[13] Dekel, Y., Gurel-Gurevich, O. and Peres, Y. (2011) Finding hidden cliques in linear time with high probability. In ANALCO11: Proc. Eighth Workshop on Analytic Algorithmics and Combinatorics, SIAM, pp. 67–75.CrossRefGoogle Scholar
[14] Deshpande, Y. and Montanari, A. (2015) Finding hidden cliques of size $\sqrt{N/e}$ in nearly linear time. Found. Comput. Math. 15 1069–1128.CrossRefGoogle Scholar
[15] Dyer, M. E. and Frieze, A. M. (1986) Fast solution of some random NP-hard problems. In 27th Annual Symposium on Foundations of Computer Science, IEEE, pp. 221–336.CrossRefGoogle Scholar
[16] Feige, U. and Krauthgamer, R. (2000) Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Alg. 16 195–208.3.0.CO;2-A>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] Feige, U. and Ron, D. (2010) Finding hidden cliques in linear time. In AofA'10: 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, DMTCS Proc. AM, pp. 189–204.CrossRefGoogle Scholar
[19] Füredi, Z. and Komlós, J. (1981) The eigenvalues of random symmetric matrices. Combinatorica 1 233–241.CrossRefGoogle Scholar
[20] Golub, G. H. and Van Loan, C. F. (1996) Matrix Computations, Johns Hopkins University Press.Google Scholar
[21] Jerrum, M. and Sorkin, G. B. (1993) Simulated annealing for graph bisection. In Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 94–103. Friedman, J., Kahn, J. and Szemeredi, E. (1989) On the second eigenvalue of random regular graphs, STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing Pages 587–598.CrossRefGoogle Scholar
[22] Friedman, J., Kahn, J. and Szemerédi, E. (1989) On the second eigenvalue of random regular graphs. In Proc. of the twenty first annual ACM symposium on theory of computing: STOC, pp. 587–598.CrossRefGoogle Scholar
[23] Kannan, R. and Vempala, S. (2009) Spectral Algorithms, Now Publishers Inc.Google Scholar
[24] Kučera, L. (1977) Expected behavior of graph coloring algorithms. In Fundamentals of Computation Theory: Proc. 1977 International FCT-Conference, Springer, pp. 447–451.CrossRefGoogle Scholar
[25] Matula, D. W. (1972) The employee party problem. Notices Amer. Math. Soc. 19 A–382.Google Scholar
[26] McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (Habib, M. et al., eds), Springer, pp. 195–248.CrossRefGoogle Scholar
[27] McSherry, F. (2001) Spectral partitioning of random graphs. In FOCS 2001: Proc. 42nd IEEE Symposium on Foundations of Computer Science, IEEE, pp. 529–537.CrossRefGoogle Scholar
[28] Talagrand, M. (1996) A new look at independence. Ann. Probab. 24 1–34.CrossRefGoogle Scholar
[29] Turner, J. (1988) Almost all k-colorable graphs are easy to color. J. Algorithms 9 63–82.CrossRefGoogle Scholar
[30] Vu, V. (2007) Spectral norm of random matrices. Combinatorica 27 721–736.CrossRefGoogle Scholar
[31] Vu, V. and Wang, K. (2015) Random weighted projections, random quadratic forms and random eigenvectors. Random Struct. Alg. 47 792–821.CrossRefGoogle Scholar
[32] Wedin, P.-Å. (1972) Perturbation bounds in connection with singular value decomposition. BIT Numer. Math. 12 99–111.CrossRefGoogle Scholar
[33] Xu, R. and Wunsch, D. (2014) Clustering, Wiley.Google ScholarPubMed