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

Bachelor thesis (2021)

Authors

A. Zoumis Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (mentor)
J.A. Pouwelse Data-Intensive Systems - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Angelos Zoumis
More Info
expand_more

Published Date

01-07-2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

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.

Files

Research_paper.pdf
(pdf | 0.494 Mb)
Unknown license