Memetic Graph Clustering
This provides an efficient solution for graph clustering tasks, though it appears incremental as it builds on existing memetic and ensemble methods.
The authors tackled the graph clustering problem by developing VieClus, a general memetic algorithm that optimizes different objective functions and uses ensemble clustering and multi-level techniques. They showed it successfully improves or reproduces all entries of the 10th DIMACS implementation challenge using minimal time.
It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation~challenge under consideration using a small amount of time.