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

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

Zoumis, Angelos (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Software Technology; TU Delft Intelligent Systems)

Demirović, E. (mentor)
Pouwelse, J.A. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2021-07-01

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.

Agglomerative hierarchical clustering
closed neighborhood
Cluster editing
Divisive hierarchical clustering
K-means

http://resolver.tudelft.nl/uuid:70669928-f3a9-4756-87bf-d02d14efa412

Student theses

bachelor thesis

© 2021 Angelos Zoumis