{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T19:46:51Z","timestamp":1767383211530},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_25","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"256-267","source":"Crossref","is-referenced-by-count":16,"title":["Spectral Clustering by Recursive Partitioning"],"prefix":"10.1007","author":[{"given":"Anirban","family":"Dasgupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Hopcroft","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pradipta","family":"Mitra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/11503415_31","volume-title":"Learning Theory","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., McSherry, F.: On spectral learning of mixtures of distributions. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS, vol.\u00a03559, pp. 458\u2013469. Springer, Heidelberg (2005)"},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica\u00a06(2), 83\u201396 (1986)","journal-title":"Combinatorica"},{"issue":"6","key":"25_CR3","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM Journal on Computing\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Azar, Y., Fiat, A., Karlin, A.R., McSherry, F., Saia, J.: Spectral analysis of data. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 619\u2013626 (2001)","key":"25_CR4","DOI":"10.1145\/380752.380859"},{"doi-asserted-by":"crossref","unstructured":"Boppana, R.: Eigenvalues and graph bisection: an average case analysis. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science (1987)","key":"25_CR5","DOI":"10.1109\/SFCS.1987.22"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. Bui","year":"1987","unstructured":"Bui, T., Chaudhuri, S., Leighton, T., Sipser, M.: Graph bisection algorithms with good average case behavior. Combinatorica\u00a07, 171\u2013191 (1987)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Cheng, D., Kannan, R., Vempala, S., Wang, G.: A Divide-and- Merge methodology for Clustering. In: Proc. of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 196\u2013205","key":"25_CR7","DOI":"10.1145\/1065167.1065192"},{"doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: A spectral heuristic for bisecting random graphs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (2005)","key":"25_CR8","DOI":"10.1002\/rsa.20116"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/11786986_60","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A.: An adaptive spectral heuristic for partitioning random graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 691\u2013702. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Dasgupta, A., Hopcroft, J., McSherry, F.: Spectral analysis of random Graphs with skewed degree distributions. In: Proceedings of the 42 nd IEEE Symposium on Foundations of Computer Science, pp. 602\u2013610 (2004)","key":"25_CR10","DOI":"10.1109\/FOCS.2004.61"},{"doi-asserted-by":"crossref","unstructured":"Dyer, M., Frieze, A.: Fast Solution of Some Random NP-Hard Problems. In: Proceedings of the 27 th IEEE Symposium on Foundations of Computer Science, pp. 331\u2013336 (1986)","key":"25_CR11","DOI":"10.1109\/SFCS.1986.17"},{"issue":"2","key":"25_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U. Feige","year":"2005","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Random Structures and Algorithms\u00a027(2), 251\u2013275 (2005)","journal-title":"Random Structures and Algorithms"},{"issue":"98","key":"25_CR13","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"Fiedler, M.: Algebraic connectibility of graphs. Czechoslovak Mathematical Journal\u00a023(98), 298\u2013305 (1973)","journal-title":"Czechoslovak Mathematical Journal"},{"doi-asserted-by":"crossref","unstructured":"Friedman, J., Kahn, J., Szemeredi, E.: On the second eigenvalue of random regular graphs. In: Proceedings of the 21 st annual ACM Symposium on Theory of computing, pp. 587\u2013598 (1989)","key":"25_CR14","DOI":"10.1145\/73007.73063"},{"issue":"3","key":"25_CR15","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. Furedi","year":"1981","unstructured":"Furedi, Z., Komlos, J.: The eigenvalues of random symmetric matrices. Combinatorica\u00a01(3), 233\u2013241 (1981)","journal-title":"Combinatorica"},{"key":"25_CR16","volume-title":"Matrix computations","author":"G. Golub","year":"1996","unstructured":"Golub, G., Van Loan, C.: Matrix computations, 3rd edn. Johns Hopkins University Press, London (1996)","edition":"3"},{"doi-asserted-by":"crossref","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On Clusterings: Good, bad and spectral. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 497\u2013515 (2000)","key":"25_CR17","DOI":"10.1109\/SFCS.2000.892125"},{"doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 529\u2013537 (2001)","key":"25_CR18","DOI":"10.1109\/SFCS.2001.959929"},{"doi-asserted-by":"crossref","unstructured":"Sinclair, A., Jerrum, M.: Conductance and the mixing property of markov chains, the approximation of the permenant resolved. In: Proc. of the 20th Annual ACM Symposium on Theory of Computing, pp. 235\u2013244 (1988)","key":"25_CR19","DOI":"10.1145\/62212.62234"},{"doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.-h.: Spectral Partitioning Works: Planar graphs and finite element meshes. In: Proc. of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996), pp. 96\u2013105 (1996)","key":"25_CR20","DOI":"10.1109\/SFCS.1996.548468"},{"unstructured":"Verma, D., Meila, M.: A comparison of spectral clustering algorithms, TR UW-CSE-03-05-01, Department of Computer Science and Engineering, University of Washington (2005)","key":"25_CR21"},{"doi-asserted-by":"crossref","unstructured":"Van Vu: Spectral norm of random matrices. In: Proc. of the 36 th annual ACM Symposium on Theory of computing, pp. 619\u2013626 (2005)","key":"25_CR22","DOI":"10.1145\/1060590.1060654"},{"doi-asserted-by":"crossref","unstructured":"Zhao, Y., Karypis, G.: Evaluation of hierarchical clustering algorithms for document datasets. In: Proc. of the 11 International Conference on Information and Knowledge Management, pp. 515\u2013524 (2002)","key":"25_CR23","DOI":"10.21236\/ADA439551"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T11:25:46Z","timestamp":1707218746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11841036_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}