A partitioning-based divisive clustering technique for maximizing the modularity
Ümit V. Çatalyürek, Kamer Kaya, Johannes Langguth, Bora Uçar · Contemporary mathematics - American Mathematical Society · 2013
We present a new graph clustering algorithm aimed at obtaining clusterings of high modularity. The algorithm pursues a divisive clustering approach and uses established graph partitioning algorithms and techniques to compute recursive bipartitions of the input as well as to refine clusters. Experimental evaluation shows that the modularity scores obtained compare favorably to many previous approaches. In the majority of test cases, the algorithm outperformed the best known alternatives. In particular, among 13 problem instances common in the literature, the proposed algorithm improves the best known modularity in 9 cases.