The Randomized Greedy Modularity Clustering Algorithm and the Core Groups Graph Clustering Scheme

The modularity measure of Newman and Girvan is a popular formal cluster criterium for graph clustering. Although the modularity maximization problem has been shown to be NP-hard, a large number of heuristic modularity maximization algorithms have been developed. In the 10th DIMACS Implementation Challenge of the Center for Discrete Mathematics & Theoretical Computer Science (DIMACS) for graph clustering our core groups graph clustering scheme combined with a randomized greedy modularity clustering algorithm won both modularity optimization challenges: the Modularity (highest modularity) and the Pareto Challenge (tradeoff between modularity and performance). The core groups graph clustering scheme is an ensemble learning clustering method which combines the local solutions of several base algorithms to form a good start solution for the final algorithm. The randomized greedy modularity algorithm is a non-deterministic agglomerative hierarchical clustering approach which finds locally optimal solutions. In this contribution we analyze the similarity of the randomized greedy modularity algorithm with incomplete solvers for the satisfiability problem and we establish an analogy between the cluster core group heuristic used in core groups graph clustering and a sampling of restart points on the Morse graph of a continuous optimization problem with the same local optima.