Skeleton-Based Clustering by Quasi-Threshold Editing
| Autor: | Ulrik Brandes, Michael Hamann, Luise Häuser, Dorothea Wagner |
|---|---|
| Přispěvatelé: | Bast, Hannah, Korzen, Claudius, Meyer, Ulrich, Penschuck, Manuel |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science, 13201 Algorithms for Big Data Lecture Notes in Computer Science ISBN: 9783031215339 |
| ISSN: | 0302-9743 1611-3349 |
| Popis: | We consider the problem of transforming a given graph into a quasi-threshold graph using a minimum number of edge additions and deletions. Building on the previously proposed heuristic Quasi-Threshold Mover (QTM), we present improvements both in terms of running time and quality. We propose a novel, linear-time algorithm that solves the inclusion-minimal variant of this problem, i.e., a set of edge edits such that no subset of them also transforms the given graph into a quasi-threshold graph. In an extensive experimental evaluation, we apply these algorithms to a large set of graphs from different applications and find that they lead QTM to find solutions with fewer edits. Although the inclusion-minimal algorithm needs significantly more edits on its own, it outperforms the initialization heuristic previously proposed for QTM. Lecture Notes in Computer Science, 13201 ISSN:0302-9743 ISSN:1611-3349 Algorithms for Big Data ISBN:978-3-031-21533-9 ISBN:978-3-031-21534-6 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|