Multi-level Algorithms for Modularity Clustering
- Modularity is a widely used quality measure for graph clusterings. Its exact maximization is prohibitively expensive for large graphs. Popular heuristics progressively merge clusters starting from singletons (coarsening), and optionally improve the resulting clustering by moving vertices between clusters (refinement). This paper experimentally compares existing and new heuristics of this type with respect to their effectiveness (achieved modularity) and runtime. For coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria. For refinement, a new multi-level algorithm produces significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in theModularity is a widely used quality measure for graph clusterings. Its exact maximization is prohibitively expensive for large graphs. Popular heuristics progressively merge clusters starting from singletons (coarsening), and optionally improve the resulting clustering by moving vertices between clusters (refinement). This paper experimentally compares existing and new heuristics of this type with respect to their effectiveness (achieved modularity) and runtime. For coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria. For refinement, a new multi-level algorithm produces significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature.…
Author: | Andreas Noack, Randolf Rotta |
---|---|
URL: | http://www.springerlink.com/content/qugv7708h3806230/ |
Document Type: | Conference Proceeding |
Language: | English |
Year of publication: | 2009 |
Tag: | Algorithmen Clustering |
Quelle aus UBICO: | Experimental Algorithms : 8th International Symposium, SEA 2009, Dortmund, Germany, June 4 - 6, 2009. - Berlin : Springer, 2009, S. 257 - 268, 978-3-642-02010-0 (Lecture Notes in Computer Science ; 5526) |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik |
Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Praktische Informatik / Softwaresystemtechnik | |
Institution name at the time of publication: | Fakultät für Mathematik, Naturwissenschaften und Informatik (eBTU) / LS Praktische Informatik / Software-Systemtechnik |
Fakultät für Mathematik, Naturwissenschaften und Informatik (eBTU) / LS Theoretische Informatik |