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

Proseminar 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 per Doodle bestimmt.

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

17.10.2012
Die Folien zur Vorbesprechung sind unter „Links“ zu finden. Die Mailingliste ist angelegt. Wer noch keine Mail über die Liste bekommen hat, sollte sich so bald wie möglich bei uns melden.

5.3.2013
Die Folien der Vorträge sind jetzt (fast) vollständig auf unserer Homepage. Das dazu nötige Passwort wird für die Teilnehmer des Seminars per Email bekannt gegeben.

Termine

Literatur

Wird im Rahmen der ersten Seminarbesprechung bekanntgegeben.

Formales

Dieses Proseminar ist Teil des Moduls „Proseminar [IN2INPROSEM]“ (zugehörige Lehrveranstaltung: PROSEM) und findet in Zusammenarbeit mit dem Institut für Programmstrukturen und Datenorganisation (IPD) statt. Es ist inhaltlich und organisatorisch verknüpft mit dem „Seminar Algorithmentechnik B“, d.h. Proseminar und Seminar bilden eine gemeinsame Veranstaltung. Die Themen verschiedener Schwierigkeitsgrade werden entsprechend vergeben.

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 3 Leistungspunkten.

  • Die Folien zur Vorbesprechung gibt es hier.