A heuristic graph editing approach to correlation clustering with overlap

Abstract

Correlation clustering seeks a partition of the vertex set of a given graph/network into groups of closely related, or just close enough, vertices so that elements of different groups are not close to each other. The problem has been previously modeled and studied as a graph editing problem, namely Cluster Editing , which assumes that closely related data elements must be adjacent. As such, the main objective (of the Cluster Editing problem) is to turn clusters into cliques as a way to identify them. This is to be obtained via two main edge editing operations: additions and deletions. There are two problems with the Cluster Editing model that we seek to address in this paper. First, “closely” related does not necessarily mean “directly” related. So closeness should be measured by relatively short distance. As such, we seek to turn clusters into (sub)graphs of small diameter. Diameter two and three (sub)graphs have been particularly effective at clustering biological networks. Second, in real applications, a data element can belong, or have roles, in multiple groups. For example, proteins can have multiple functions. In some cases, not allowing data elements to belong to more than one cluster could make it difficult to obtain significant clustering via classical partition-based methods. We address this latter problem by allowing vertex cloning, also known as vertex splitting. A novel Markov chain heuristic method is presented for the problem along with experimental results showing the effectiveness of the proposed model and algorithmic approach in gene-function association as well as synthetic networks. In particular, the presented heuristic achieved the highest F-score on the extended Lancichinetti-Fortunato-Radicchi (LFR) benchmark.