Analyse von Graph-Daten

BearbeiterIn:Sebastian Lenz
Titel:Analyse von Graph-Daten
Typ:Studienarbeit
Betreuer:Wörlein, M.; Werth, T.; Dreweke, A.; Philippsen, M.
Status:abgeschlossen am 4. Februar 2008
Vorausetzungen:

Die Arbeitsgruppe ParSeMiS (Parallele und Sequentielle graph Mining Suite) beschäftigt sich mit der Suche nach häufigen interessanten Strukturen in Graphdatenbanken; ein Forschungsgebiet, das in den letzten Jahren sehr reges Interesse geweckt hat. Da viele Forschungs- und Wirtschaftsdaten in strukturierter Form erfasst werden können, bietet sich die Speicherung komplexer Zusammenhänge in Form von allgemeinen oder speziellen Graphen an. Diese meist unüberschaubaren Datenmengen sind nur schwer mit Hand und Auge zu erfassen, so dass Algorithmen zur Entdeckung interessanter Korrelationen unabdingbar sind. Da das Entdecken dieser Zusammenhänge in Graphen im Allgemeinen sehr aufwändig ist, ist die Suche nach paralellen und spezialisierten Algorithmen notwendig, die den benötigen Rechenzeit- und Speicheranforderungen auch bei immer größer werdenden Datenmengen gewachsen sind.

Thema:

Bisherige Graph-Mining-Algorithm werden meist an uneinheitlichen, nicht immer öffentlich zugänglichen oder den jeweiligen Einsatzgebiet angepassten Daten bewertet, was einen fairen Vergleich dieser Bewertungen untereinander quasi unmöglich macht. Die Laufzeiten der NP-vollständigen Algorithmen hängen stark von den Eigenschaften der Datenbank ab. Zu erwähnen sind hier z.B. die Anzahl und Größe der Elemente, die Häufigkeit und Größe der Fragmente, die Anzahl und Verteilung der Knoten-/Kantenbeschriftungen, oder die Anzahl bzw. Häufigkeit von Zyklen. Unterschiedliche Anwendungsgebiete arbeiten auf unterschiedliche Daten, wodurch Messungen aus einem Gebiet nichts über die Laufzeiten/Speicherbedürfnisse andere Anwendungsgebiete aussagen müssen.

In dieser Arbeit geht es darum verschiedene Datensätze hinsichtlich ihrer Auswirkungen auf verschiedene Algorithmen zu gruppieren und zu analysieren, welche Eigenschaften sich positiv bzw. negativ auf die unterschiedlichen Algorithmen auswirken. Anhand dieser erarbeiteten Daten soll eine aussagekräftige Menge von realen und synthetischen Datenbanken zusammengestellt werden, mit der alte und neue Graph-Mining-Algorithmen auf ihre Effizienz in unterschiedlichen Bereichen getestet und verglichen werden können. Hierfür sind folgende Schritte vorgeschlagen:

  • Einarbeitung in die vorhandenen Datenstrukturen und die unterschiedlichen Anwendungsgebiete des Graph Minings (wie z.B. Molekulares Mining [1], Prozedurale Abstraktion [2])
  • Analyse und Gruppierung der vorhandenen Datenbanken anhand von auffälligen Laufzeit- und Speicheranforderungen verschiedener Mining-Algorithmen
  • Identifikation und Verifikation unterscheidender Merkmale der entdeckten Gruppen
  • Erstellung und Zusammenstellung relevanter Datensätze in einem (oder mehreren) Standard-Datenformat(en) [3]
  • Vermessungen der vorhandenen Algorithmen anhand der gefundenen Datensätze
  • Optional: Suche und Vermessung weiterer öffentlicher Graph-Mining Algorithmen anhand der gefundenen Datensätze

[1] T. Washio and H. Motoda. State of the Art of Graph–based Data Mining. SIGKDD Explorations Newsletter, 5(1):59–68, July 2003.
[2] A. Dreweke, M. Wörlein, I. Fischer, D. Schell, T. Meinl, and M. Philippsen. Graph-Based Procedural Abstraction. Proc. of the 2007 CGO:259-270, March 2007.
[3] GraphML: http://graphml.graphdrawing.org/

watermark seal