BibSonomy :: publication ::

tag user group author concept BibTeX key search:all search:folke

The blue social bookmark and publication sharing system.

entry of folke and 1 other user:

(0)

This publication has not been reviewed yet.

rating distribution

average user rating

The average rating is computed over all reviews. However, some of them may be invisible to you due to the visibility setting chosen by the reviewers.

(0.0 of 5.0 based on 0 reviews)

On clusterings: Good, bad and spectral

by: Ravi Kannan, Santosh Vempala, and Adrian Vetta

In: J. ACM, Vol. 51, Nr. 3 New York, NY, USA: ACM (2004) , p. 497--515.

Resources (URL, PDF, PS...)

URL:	http://portal.acm.org/citation.cfm?id=990313
DOI:	10.1145/990308.990313

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.

Description

On clusterings

BibTeX record

@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 = {http://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 = {2010-07-26T18:43:13.000+0200},
  title = {On clusterings: Good, bad and spectral},
  url = {http://portal.acm.org/citation.cfm?id=990313},
  volume = 51,
  year = 2004
}

Endnote record