direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Graphclustern durch Zerstören langer induzierter Pfade

Felix Bohlmann (TU Berlin)

Beim Clustern von Graphen geht es darum, dichte Teilgraphen zu finden, die wenige
Kanten zum Rest des Graphen aufweisen, und diese mit möglichst wenigen Änderun-
gen zu separieren. Diese dichten Teilgraphen werden durch ein konkretes Modell charakterisiert.
Ein solches ist zum Beispiel das P5 -frei-Modell, mit welchem wir uns in
dieser Arbeit befassen wollen. Das P5-frei-Editierungsproblem ist das NP-schwere Problem
einen gegebenen Graphen durch Hinzufügen und Löschen einer minimalen Anzahl
an Kanten in einen P5-freien Graphen zu transformieren.
Wir werden einen parametrisierten Algorithmus vorstellen, der
in O(10^k · m^2) Laufzeit eine optimale Lösung fürdas Problem findet.

Der Fokus dieser Arbeit liegt darauf, eine leistungsstarke Implementierung dieses
Algorithmus zu konstruieren. Dazu gehen wir auf Algorithmen zur Suche von P5's ein und
stellen Datenreduktionsregeln sowie untere Schranken für die minimale Anzahl der Änderungen auf.
Anschließend wenden wir den Algorithmus auf synthetischen Graphen sowie Interaktions-
und Proteinähnlichkeitsgraphen  an und bewerten wie gut das P5 -frei-Modell zu den einzelnen Graphen passt.
Wir kommen zu dem Schluss, dass das P5-frei-Modell für die von uns gewählten
Graphen ein gutes Modell ist. Wir konnten zum Beispiel für den Zachary-Karate-Club-Graphen
mit 34 Knoten eine optimale Lösung mit 13 Editierungen berechnen, welche den Graphen
in die selben Partitionen wie einst Zachary aufteilt. Allerdings ist das Finden
einer optimalen Lösung deutlich schwieriger als für viele andere ähnliche Modelle,
wie zum Beispiel das Clustergraph- oder das Co-Graph-Modell.

The talk will be held in german.

Date
Speaker
Location
Language
27.05.2015
17:30
Felix Bohlmann
TEL 512
german

Back to the research colloquium site.

Zusatzinformationen / Extras