Editing Problem in Clustering

Abstract—The editing problem in clustering (deletion and addition of edges and/or vertices in an initial graph for building a cluster structure), including various options of the problem (edge cluster editing, vertex cluster editing, etc.) is studied. A literature survey on the problems (problem types and solving approaches) is presented. The cluster edge editing problem is in focus. Several mathematical optimization models for the problem are described: (i) the basic edge editing problem with minimization of the general number of added edges and the number of deleted edges, (ii) the option of the above-mentioned problem with weights of all vertex pairs (including the bi-criteria problem case), and (iii) a multi-criteria problem with vector weights of the vertex pairs. In addition, some other editing problems are briefly described: (a) the edge deletion editing problem, (b) edge editing problem with several vertex types, and (c) vertex deletion editing problem. The problems discussed are illustrated by numerical examples. Some future research directions are pointed out.