Multi-level algorithms for modularity clustering

Abstract

Modularity is one of the most widely used quality measures for graph clusterings. Maximizing modularity is NP-hard, and the runtime of exact algorithms is prohibitive for large graphs. A simple and effective class of heuristics coarsens the graph by iteratively merging clusters (starting from singletons), and optionally refines the resulting clustering by iteratively moving individual vertices between clusters. Several heuristics of this type have been proposed in the literature, but little is known about their relative performance. This paper experimentally compares existing and new coarsening- and refinement-based heuristics with respect to their effectiveness (achieved modularity) and efficiency (runtime). Concerning 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 algorithm by Schuetz and Caflisch is no improvement over simple greedy coarsening for these criteria. Concerning refinement, a new multi-level algorithm is shown to produce 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.

12 pages, 10 figures, see http://www.informatik.tu-cottbus.de/~rrotta/ for downloading the graph clustering software

References in corpus (13)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Analysis of weighted networks
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Modularity-Maximizing Network Communities via Mathematical Programming
• Finding Community Structure in Mega-scale Social Networks
• Identifying "communities" within energy landscapes

Cited by in corpus (6)

• Community detection in graphs
• Communities in Networks
• Optimizing an Organized Modularity Measure for Topographic Graph Clustering: a Deterministic Annealing Approach
• Block modelling in dynamic networks with non-homogeneous Poisson processes and exact ICL
• Developmental tendencies in the Academic Field of Intellectual Property through the Identification of Invisible Colleges
• Network Community Detection with A Successive Spectral Relaxation Method