Abstract
A partition of a set of n items is a grouping of the items into k disjoint classes of equal size. Any partition can be modeled as a graph: the items become the vertices of the graph and two vertices are connected by an edge if and only if the associated items belong to the same class. In a planted partition model a graph that models the planted partition is obscured by random noise, i.e., edges within a class can get removed and edges between classes can get inserted at random. We study the task to reconstruct the planted partition from this graph whose complexity can be controlled by the number k of classes if the noise level is fixed. The best bounds on k where the classes can be reconstructed correctly almost surely are achieved by spectral algorithms. We show that a combination of random sampling and iterating the spectral approach can boost its performance in the sense that the number of classes that can be reconstructed correctly asymptotically almost surely can be as large as \(k = c\sqrt{n}/{\rm loglog}n\) for some constant c. This extends the range of k for which such guarantees can be given for any efficient algorithm.
Partly supported by the Swiss National Science Foundation under the grant “Non-linear manifold learning”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bollobas, B., Scott, A.D.: Max cut for random graphs with a planted partition. Combinatorics, Probability and Computing 13, 451–474 (2004)
Condon, A., Karp, R.: Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms 8(2), 116–140 (1999)
Frieze, A., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms 10, 5–42 (1997)
Füredi, Z., Komlós, J.: The eigenvalues of random symmetric matrices. Combinatorica I 3, 233–241 (1981)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete graph problems. Theoretical Computer Science 1, 237–267 (1976)
Giesen, J., Mitsche, D.: Bounding the misclassification error in spectral partitioning in the planted partition model. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 409–420. Springer, Heidelberg (2005)
Giesen, J., Mitsche, D.: Reconstructing many partitions using spectral techniques. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 433–444. Springer, Heidelberg (2005)
Krivelevich, M., Vu, V.H.: On the concentration of eigenvalues of random symmetric matrices. Microsoft Technical Report 60 (2000)
McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of 42nd IEEE Symosium on Foundations of Computer Science, pp. 529–537 (2001)
Shamir, R., Tsur, D.: Improved algorithms for the random cluster graph model. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 230–259. Springer, Heidelberg (2002)
Stewart, G., Sun, J.: Matrix perturbation theory. Academic Press, Boston (1990)
Vu, V.H.: Spectral norm of random matrices. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 423–430. ACM Press, New York (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giesen, J., Mitsche, D. (2005). Boosting Spectral Partitioning by Sampling and Iteration. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_48
Download citation
DOI: https://doi.org/10.1007/11602613_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)