Developing efficient heuristic approaches to cluster editing, inspired by other clustering problems

Abstract

Cluster editing attempts to find the minimum number of edge additions and removals on an undirected graph, that will transform the graph to one consisting of only disconnected cliques. In this paper, we propose three heuristic approaches to this problem, based on algorithms used to solve different clustering problems. The algorithms were based on agglomerative, divisive and k-means clustering algorithms. Experimental results show that all three algorithms are able to find results close to the minimum number of edits, but in particular, the k-means algorithm has a lower time complexity compared to the other two algorithms, while producing on average, the lowest number of edits.