Name
Abstract | ||
|---|---|---|
Clustering problems are applicable to several areas of science. Approaches and algorithms are as varied as the applications. From a graph theory perspective, clustering can be generated by partitioning an input graph into a vertex-disjoint union of cliques (clusters) through addition and deletion of edges. Finding the minimum number of edges additions and deletions required to cluster data that can be represented as graphs is a well-known problem in combinatorial optimization, often referred to as cluster editing problem. However, many real-world clustering applications are characterized by overlapping clusters, that is, clusters that are non-disjoint. In these situations cluster editing cannot be applied to these problems. Literature concerning a relaxation of the cluster editing, where clusters can overlap, is scarce. In this work, we propose the overlapping cluster editing problem, a variation of the cluster editing where the goal is to partition a graph, also by editing edges, into maximal cliques that are not necessarily disjoint. In addition, we also present three slightly different versions of a hybrid heuristic to solve this problem. Each hybrid heuristic is based on coupling two metaheuristicsthat, together, generate a set of clusters; and one of three mixed-integer linear programming models, also introduced in this paper, that uses these clusters as input. The objective with the metaheuristics is to limit the solution exploration space in the models’ resolution, therefore reducing its computational time. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.asoc.2019.105482 | Applied Soft Computing |
Keywords | Field | DocType |
Overlapping cluster editing,Cluster editing,Overlapping clustering,Hybrid heuristic | Graph theory,Cluster (physics),Mathematical optimization,Heuristic,Vertex (geometry),Theoretical computer science,Combinatorial optimization,Linear programming,Cluster analysis,Mathematics,Metaheuristic | Journal |
Volume | ISSN | Citations |
81 | 1568-4946 | 2 |
PageRank | References | Authors |
0.38 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guilherme Oliveira Chagas | 1 | 2 | 0.38 |
| Luiz Antonio Nogueira Lorena | 2 | 498 | 36.72 |
| Rafael Duarte Coelho dos Santos | 3 | 2 | 0.38 |