Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼
 

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Seminar Algorithms for Large Graphs

Prof. Dr. Ulf Leser

Graphen sind elementare Datenstrukturen in der Informatik und haben eine große Bedeutung in vielen Bereichen. Während viele Fragestellungen für kleine Graphen, Bäume oder DAGs sehr schnell gelöst werden können, sind sehr große Graphen, die nicht in den Hauptspeicher passen, auch für relativ einfache Probleme oftmals noch eine Herausforderung. Beispiele für große Graphen sind soziale Netzwerke (Facebook, Twitter), Zitationsgraphen oder biologische Netzwerke (Gen / Protein Interaktionsnetzwerke). Das Seminar bietet eine Einführung in klassische Graph-Algorithmen (Erreichbarkeit, Subgraphmatching, kürzeste Wege, etc.) mit Fokus auf großen Graphen. Die Studenten stellen in Vortrag und Seminararbeit spezielle Algorithmen und Optimierungen vor.

Das Seminar findet im wesentlichen als Blockseminar am Ende des Semesters statt. Vorher sind aber Einführungstermine und individuelle Themenbesprechungen zu besuchen.

Voraussetzungen

  • Gute Kenntnisse in Algorithmen und Datenstrukturen (z.B. gleichnamige Vorlesung)
  • Kenntnisse in Datenbanken und Indexstrukturen (z.B. Einführung in Datenbanken)

Schein und Anrechenbarkeit

Das Seminar ist anrechenbar für

  • Diplom Informatik
  • Monobachelor Informatik

Voraussetzung für den Schein ist:

  • das Bestehen einer Kurzklausur zu Grundlagenthemen in der Mitte des Semesters (siehe unten),
  • das Halten eines wissenschaftlichen Vortrags am Ende des Semesters,
  • das Erstellen einer schriftlichen Ausarbeitung (Seminararbeit)

Anmeldung

Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgt über Goya.

Termine und Ablauf

Am 29.10.2013 findet von 13-15 Uhr die Einführungsveranstaltung statt, die für alle Teilnehmenden verpflichtend ist. Dort werden die Themen erläutert und vergeben.

Das Seminar wird als Blockseminar am Ende des Semesters abgehalten. Jede(r) Studierende muss einen ca. 30 minütigen Vortrag über das zugewiesene Thema halten. Vorher finden mindestens zwei Treffen mit dem/der Betreuer(in) statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, in dem alle Studierenden in einer 5-minütigen Flash-Präsentation ihr Thema vorstellen, um Querverbindungen zu erkennen und die rechtzeitige Beschäftigung mit dem Thema sicherzustellen. Schließlich muss zu jedem Thema eine 10-15 seitige Seminararbeit verfasst werden.

Zusätzlich zu der speziellen Literatur, über die die Vorträge gehalten werden, gibt es für alle Teilnehmer verpflichtende Einführungslektüre. In der Mitte des Semesters werden die dort vermittelten Kenntnisse im Rahmen einer Kurzklausur überprüft. Das Bestehen der Klausur ist Voraussetzung für die weitere Teilnahme.

Alle Pflichttermine in der Übersicht:

  • 29.10.13, 13-15 Uhr: Einführung und Themenvergabe, EZ 0'313
  • Bis 30.11.2013: Treffen mit dem Betreuer zur Themenbesprechung und -eingrenzung
  • 20.12.2013, 11-13 Uhr: Flash-Präsentationen und Kurzklausur; HU Kabinett
  • Bis 20.1.2014: Treffen mit dem Betreuer zur Besprechung der Folien
  • 12/14.2.2014, 10-14 Uhr: Blockseminar, HU Kabinett
  • Bis 31.3.2014: Abgabe Seminararbeit

Vorlagen


Zeitplan Blockseminar

Mittwoch, 12.2.2014
10.00 Lipka Bellmann-Ford Algorithmus
10.40Piesk Routen-Findung
12.00 Deppisch Betweenness-Centrality
12.40 Schulze Reachability Indexing mit GRAIL
Freitag, 14.2.2014
10.00 KondratevaSubgraph Isomorphism
10.40 Hönicke Approximative Subgraphsuche mit SAGA
11.20Sielhorst Network Motifs
12.00 Manthey Dense Subgraph Maintenance in Data Streans
12.40 Triebel Ford-Fulkerson Algorithmus


Themen

Topic Paper Vortragende(r) Betreuer(in)
Einführende Literatur für alle Teilnehmer Sedgewick, "Algorithms in Java", Part 5, Chapter 17    
Folien der Einführung     Ulf Leser
Shortest Paths with Bellman-Ford Sedgewick, "Algorithms in Java", Part 5, Chapter 21 Lipka Ulf Leser
Regular Path Queries Koschmieder, A. and Leser, U. (2012). "Regular Path Queries on Large Graphs". Int. Conf. on Scientific and Statistical Database Management, Chania, Greece. Andre Koschmieder
Betweenness-Centrality Brandes, U. (2001). "A faster algorithm for betweenness centrality." Journal of Mathematical Sociology 25(2): 163-177. Deppisch Ulf Leser
Graph Alignment Kuchaiev, O., Milenkovi, T., Memisevic, V., Hayes, W. and Przulj, N. (2010). "Topological network alignment uncovers biological function and phylogeny." Journal of the Royal Society.   Andre Koschmieder
Exact Subgraph Matching Lee, J., Han, W.-S., Kasperovics, R. and Lee, J.-H. (2013). "An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases". PVLDB, Riva del Garda, Italy. Kondrateva Ulf Leser
Route Planning in Planar Graphs
  • SS05] Sanders, P. and Schultes, D. (2005). "Highway Hierarchies Hasten Exact Shortest Path Queries". 13th European Symposium on Algorithms (ESA): 568-579.
  • Sanders, P. and Schultes, D. (2007). "Engineering Fast Route Planning Algorithms". 6th Workshop on Experimental Algorithms (WEA). pp 23-36.
Piesk Ulf Leser
Reachability Yildirim, H., Chaoji, V. and Zaki, M. J. (2010). "GRAIL: Scalable Reachability Index for Large Graphs." Proceedings of the VLDB Endowment 3(1). Schulze Ulf Leser
Frequent Subgraphs Wernicke, S. (2006). "Efficient detection of network motifs." IEEE/ACM Trans Comput Biol Bioinform 3(4): 347-59. Sielhorst Ulf Leser
Max-Flow with Ford/Fulkerson Sedgewick, "Algorithms in Java", Part 5, Chapter 22 Triebel Ulf Leser
Approximate Subgraph Search Tian, Y., McEachin, R. C., Santos, C., States, D. J. and Patel, J. M. (2007). "SAGA: a subgraph matching tool for biological graphs." Bioinformatics 23(2): 232-9. Hönicke Ulf Leser
Story-Recognition using Dense Subgraphs Angel, A., Koudas, N., Sarkas, N. and Srivastava, D. (2012). "Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification". Int. Conf. on Very Large Databases Istanbul, Turkey. Manthey Ulf Leser