Correlation Clustering via 2-Club Clustering with Vertex Splitting

Abstract

In the realm of graph theory, correlation cluster is studied as a graph modification problem known under "Cluster Editing." In this problem, we apply a sequence of k edge (or vertex) additions and/or deletions so the graph becomes a topological sum of clusters. At first, a cluster was considered a clique but relaxation models have later emerged as cliques were deemed too strict of a requirement in application domains. Another limitation of cluster editing is that it forces each vertex to be in exactly one cluster, i.e. it does not allow overlapping communities. In this thesis, we study two novel problems: 2-CLUB CLUSTER VERTEX SPLITTING (2CCVS) and 2-CLUB CLUSTER EDITING WITH VERTEX SPLITTING (2CCEDVS). 2-Clubs alleviate the strictness of cliques and vertex splitting allows for a vertex to be in multiple clusters, overcoming two main limitations of the currently studied models. Both of these problems are proved to be NP-Hard and heuristics are presented for 2CCED and 2CCEDVS.We compare the heuristic’s performance against well-known clustering algorithms on Biological and Social Networks. The presented 2CCEDVS heuristic achieves the best cluster separation, i.e. highest inter-cluster distance.