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
- Schriftliche Ausarbeitung, Latex
- Vortrag, Powerpoint
- Vortrag, Keynote
- Text für die Selbstständigkeitserklärung
- Checkliste für Vortrag und Seminararbeit
Zeitplan Blockseminar
| Mittwoch, 12.2.2014 | ||
| 10.00 | Lipka | Bellmann-Ford Algorithmus |
| 10.40 | Piesk | Routen-Findung |
| 12.00 | Deppisch | Betweenness-Centrality |
| 12.40 | Schulze | Reachability Indexing mit GRAIL |
| Freitag, 14.2.2014 | ||
| 10.00 | Kondrateva | Subgraph Isomorphism |
| 10.40 | Hönicke | Approximative Subgraphsuche mit SAGA |
| 11.20 | Sielhorst | 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 |
|
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 |