Verteidigung der Masterarbeit: "Heuristics for Dense Graph Partition"
von Tessa Bertholdt
- https://www.informatik.hu-berlin.de/de/events/verteidigung-der-masterarbeit-heuristics-for-dense-graph-partition
- Verteidigung der Masterarbeit: "Heuristics for Dense Graph Partition"
- 2026-09-30T14:00:00+02:00
- 2026-09-30T23:59:59+02:00
- von Tessa Bertholdt
- Wann 30.09.2026 ab 14:00 Uhr
- Wo RUD25 3.321
- Name des Kontakts Dr. Katrin Casel
-
iCal
Abstract
The Maximum Dense Graph Partition Problem (MDGP) is the problem of partitioning the vertices of a graph so as to maximize the sum of the internal densities of the resulting clusters. In this thesis, a local-search heuristic for optimizing the MDGP objective function is developed and evaluated experimentally. For this purpose, different methods for constructing initial partitions and different local-search strategies are compared. The resulting heuristic, MDGP-Plateau, uses a maximum matching partition as its initial partition and improves it through repeated local moves of individual vertices between clusters. In addition to strictly improving moves, neutral moves are allowed in order to traverse plateaus in the search space.
The experimental evaluation is conducted on synthetically generated Powerlaw and Erdös-Renyi graphs of different sizes and densities. To assess solution quality, MDGP-Plateau is compared with several graph partitioning methods. These include the Leiden method, an extension of the Louvain method for community detection, a variant of Leiden adapted to the MDGP objective function, and the Cluster Editing heuristic KaPoCE. On the considered synthetic graphs, MDGP-Plateau achieves the highest overall solution quality regarding the MDGP objective function.
In addition, the behavior of the methods is studied on synthetic Gaussian partition graphs with a known ground-truth partition. Besides MDGP solution quality, the extent to which the resulting partitions agree with the predefined cluster structure is evaluated. The results show that a high MDGP partition density does not necessarily coincide with a high agreement with the predefined community structure. Optimizing the MDGP objective function and recovering a given community structure therefore constitute different objectives.