• search hit 33 of 141
Back to Result List

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.show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
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
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.