Institut für Theoretische Informatik, Algorithmik

Synergien aus Graph-Theorie und Data-Mining für fortgeschrittene Analysen von Netzwerkdaten

Seminar Algorithmentechnik B im Wintersemester 2012/13

Allgemeines

Betreuung

Dr. Tanja Hartmann, Dr. Andrea Kappes, Prof. Dr. Dorothea Wagner
Anmeldung per Mail an Tanja Hartmann

Regelmäßiger Termin

Wird noch bekannt gegeben

Erster Termin

Die Vorbesprechung mit Themenvergabe findet am Dienstag, den 16. Oktober 2012 um 14:00 Uhr bis 15:30 Uhr im Seminarraum 348 (Geb. 50.34) statt.

Inhalt

Graph-Theorie und Datenanalyse sind fundamental wichtige Grundlagen der Informatik, welche zusammen eine neue Forschungsrichtung bilden. Im Bereich der Graph-Analyse werden komplexe Netzwerke (z.B. aus sozialen Netzwerken, Zitationsdatenbanken, Sensoren, oder Produktempfehlungen) untersucht. Das Ziel von Graph-Analyse ist diese Netzwerkdaten mit automatisierten Methoden auszuwerten. Hierbei sollen komplexe Muster in Graphen entdeckt werden, aber gleichzeitig auch die Skalierbarkeit der Algorithmen für große Datenbestände gewährleistet werden. Die Veranstaltung bietet eine übergreifende Betrachtung von Techniken in folgenden drei Bereichen:

  • Graph Measures
    zur Bewertung von Knoten und Subgraphen
  • Graph Clustering
    zur Gruppierung von ähnlichen Graph-Strukturen
  • Graph Outlier Mining
    zur Erkennung von abweichenden Graph-Anomalien

Diese Themenschwerpunkte sollen jeweils an Beispielen realer Netzwerke diskutiert werden. Eine individuelle Komplexitätsanalyse soll die Schwächen oder Stärken bestimmter Verfahren für große Datenmengen aufzeigen. Übergreifend sollen die Skalierbarkeit im Vergleich zu den anderen Techniken diskutiert werden. Effiziente Approximationen von komplexen Graph-Analyse Modellen sind für heutige Datenmengen unerlässlich. Es soll deshalb auch die Abwägung zwischen Qualität und Laufzeit im Seminar diskutiert werden.

Die Veranstaltung wird gemeinsam mit dem Institut für Programmstrukturen und Datenorganisation (IPD) angeboten. Wir erwarten große Synergien aus Theorie und Praxis für die Analyse großer Graphen, welche den Studenten in diesem gemeinsamen Seminar vermittelt werden sollen.

Aktuelles

Ist hier zu finden.

Termine

Sind ebenfalls hier zu finden.

Literatur

Wird im Rahmen der ersten Seminarbesprechung bekanntgegeben.

Formales

Dieses Seminar ist Teil des Moduls „Seminar Algorithmentechnik [IN4INALGTS]“ (zugehörige Lehrveranstaltung: 24079s) und findet in Zusammenarbeit mit dem Institut für Programmstrukturen und Datenorganisation (IPD) statt. Es ist inhaltlich unabhängig vom „Seminar Algorithmentechnik A“, welches aus organisatorischen Gründen zum selben Modul und zur selben Lehrveranstaltung zählt.

Lernziele

In dieser Veranstaltung sollen zum einen inhaltliche Kenntnisse im Bereich der Graph-Analyse in modernen Informationssystemen vermittelt werden. Zum anderen sollen die Studierenden methodische Kenntnisse über die selbständige Literaturrecherche und das Aufbereiten von Material für schriftliche Ausarbeitungen und Präsentationen erwerben und vertiefen.

Empfehlungen

Grundkenntnisse im Bereich Graph-Algorithmen sind erwünscht (z.B. aus den Vorlesungen „Algorithmische Methoden zur Netzwerkanalyse“ [24162], „Graphenalgorithmen und lineare Algebra Hand in Hand“ [24694] oder „Algorithmen für planare Graphen“).

Erfolgskontrolle, Note, ECTS-Punkte

Die Erfolgskontrolle erfolgt als Gesamtnote für Ausarbeitung (50%) und Präsentation (50%). Der Arbeitsaufwand entspricht 110 Stunden (4 Leistungspunkte).

Weitere Informationen folgen.