Correlation Clustering with Overlaps

Abstract

The Cluster Editing problem asks for transforming a given graph into a disjoint union of cliques by applying a minimal number of edge-editing operations. The allowed operations include addition of non-existing edges and deletion of existing ones. We study a multi-parameterized version of the problem that limits the global number of allowed edge editing operations in the graph and the local amounts of the edge edits performed per vertex. Moreover, we allow the new vertex splitting operation, which allows the resulting clusters to overlap. In other words, data elements (or vertices) will be allowed to be members in more than one cluster instead of limiting them to only one single cluster, as in classical clustering methods. We present a heuristic algorithm and a semi-exact algorithm for the Multi-Parameterized Cluster Editing with Vertex Splitting problem. In our experimental analysis, we study the efficiency of our algorithms as well as the effectiveness of allowing vertex splitting. In particular, we show that allowing vertex splitting yields higher clustering accuracy and higher intra-cluster similarity.