Multi-level algorithms for modularity clustering

Details Multi-level algorithms for modularity clustering Multi-level algorithms for modularity clustering

2008-12-22

arxiv.org/abs/0812.4073v2

Proceedings of the 8th International Symposium on Experimental Algorithms (SEA 2009). Lecture Notes in Computer Science 5526,

Computer Science

Data Structures and Algorithms

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Multi-level algorithms for modularity clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-level algorithms for modularity clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-level algorithms for modularity clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-537700