A Greedy Heuristic for Cluster Editing with Vertex Splitting

Abstract

Cluster Editing is one form of correlation clustering that requires a minimal amount of edge-editing operations to transform a given graph into a transitive graph or a disjoint union of cliques. This paper considers the more realistic scenario where data elements can belong to more than one cluster. This problem formulation is typical of real-world data such as social networks where individuals can be members of different communities or have multiple roles/interests. Capitalizing on recent work on Cluster Editing with Vertex Splitting, we present a heuristic approach that, among other steps, evaluates the likelihood of splitting a vertex into two vertices with disjoint neighborhoods and tries to predict how such splitting should be performed. Experimental results show the effectiveness of the splitting operation in giving more insightful clustering and provide empirical evidence of the effectiveness of the proposed heuristic as a promising tool for data analysis in various domains.