Density-Constrained Graph Clustering
| Autor: | Robert Görke, Andrea Schumm, Dorothea Wagner |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Theoretical computer science
Heuristic (computer science) business.industry Exact cover Machine learning computer.software_genre Measure (mathematics) Range (mathematics) Cut Algorithmic efficiency Feature (machine learning) Artificial intelligence business computer Clustering coefficient Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642222993 WADS |
| DOI: | 10.1007/978-3-642-22300-6_58 |
| Popis: | 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|