%0 Journal Article %1 kannan2004clusterings %A Kannan, Ravi %A Vempala, Santosh %A Vetta, Adrian %C New York, NY, USA %D 2004 %I ACM %J J. ACM %K clustering community evaluation %N 3 %P 497--515 %R 10.1145/990308.990313 %T On clusterings: Good, bad and spectral %U http://portal.acm.org/citation.cfm?id=990313 %V 51 %X We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.

@article{kannan2004clusterings, abstract = {We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.}, added-at = {2010-07-26T18:43:13.000+0200}, address = {New York, NY, USA}, author = {Kannan, Ravi and Vempala, Santosh and Vetta, Adrian}, biburl = {https://www.bibsonomy.org/bibtex/2e861c1d63015e10120909af68d34f766/folke}, description = {On clusterings}, doi = {10.1145/990308.990313}, interhash = {a1b52b044b404dec2ffc8f1089760d88}, intrahash = {e861c1d63015e10120909af68d34f766}, issn = {0004-5411}, journal = {J. ACM}, keywords = {clustering community evaluation}, number = 3, pages = {497--515}, publisher = {ACM}, timestamp = {2011-09-13T22:35:47.000+0200}, title = {On clusterings: Good, bad and spectral}, url = {http://portal.acm.org/citation.cfm?id=990313}, volume = 51, year = 2004 }