Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Density-Constrained Graph Clustering
verfasst von : Robert Görke, Andrea Schumm, Dorothea Wagner
Erschienen in: Algorithms and Data Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Clusterings of graphs are often constructed and evaluated with the aid of a quality measure. Numerous such measures exist, some of which adapt an established measure for graph cuts to clusterings. In this work we pursue the problem of finding clusterings which simultaneously feature guaranteed intra- and good intercluster quality. To this end we systematically assemble a range of cut-based bicriteria measures and, after showing
$\mathcal{NP}$
-hardness for some, focus on the classic heuristic of constrained greedy agglomeration. We identify key behavioral traits of a measure, (dis-)prove them for each one proposed and show how these translate to algorithmic efficiency.