Overlapping Community Detection using Cluster Editing with Vertex Splitting

Abstract

The problem Cluster Editing with Vertex Splitting models the task of overlapping community detection by yielding a cluster graph wherein a vertex of the input graph may be split so that it is present in several clusters. Cluster Editing with Vertex Splitting is previously proved to be in FPT with a quadratic size kernel. In this thesis we apply techniques from the fields of metaheuristics and hyperheuristics in order to develop heuristics for the problem. These heuristics prove to be robust, to scale linearly with a factor of 2.1*10^(-3) per additional edge in the input graph and to enable the study of high-quality solutions of CEVS for much larger graphs than what is possible with currently known exact methods. Furthermore, CEVS-score is introduced as a ground truth independent measure for comparing solutions to the overlapping community detection task, and communities found by the CEVS-heuristics are compared to communities found by other algorithms solving the overlapping community detection task with results favoring the CEVS-heuristics.