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

Marc Bux

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

  • Master of Science (Informatik)
  • Diplom (Informatik)
  • Master of Education (Informatik)

Voraussetzung für den Schein ist:

  • das Halten eines fünfminütigen Flash-Vortrags in der Mitte des Semesters,
  • das Halten eines dreißigminütigen wissenschaftlichen Vortrags am Ende des Semesters,
  • das Erstellen einer zehn- bis fünfzehnseitigen schriftlichen Ausarbeitung (Seminararbeit).

Anmeldung

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

Termine und Ablauf

Am 19.10.2015 findet von 15-17 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 Betreuer statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, an 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.

Alle Pflichttermine in der Übersicht:

  • 19.10.15, 15-17 Uhr, RUD 26, 1'308: Einführung und Themenvergabe
  • Bis 20.11.2015: Erstes Treffen mit dem Betreuer zur Themenbesprechung und -eingrenzung (Termin bis 2.11.2015 vereinbaren)
  • Bis 30.11.2015: Zusenden eines ersten Entwurfs der Folien für die Flash-Präsentation
  • 7.12.2015, 15-17 Uhr, RUD 26, 0'313: Flash-Präsentationen
  • Bis 15.1.2016: Zweites Treffen mit dem Betreuer zur Besprechung der Folien (Termin bis 21.12.2015 vereinbaren)
  • 29.1. und 5.2., 10-15 Uhr, RUD 25, Humboldt-Kabinett: Blockseminar
  • Bis 31.3.2016: Abgabe Seminararbeit

Vorlagen


Themen

Topic Paper Vortragende(r) Betreuer(in)
Einführende Literatur für alle Teilnehmer
  • Sedgewick, Robert. "Algorithms in Java", Part 5, Chapter 17 (2003).
Einführung Folien der Einführung Bux
Regular Path Queries
  • Koschmieder, André, and Ulf Leser. "Regular path queries on large graphs." Proceedings of the 24th international conference on Scientific and Statistical Database Management (2012): 177-194.
Vogt (Folien des Vortrags) Marc Bux
Betweenness-Centrality
  • Brandes, Ulrik. "A faster algorithm for betweenness centrality." Journal of Mathematical Sociology 25.2 (2001): 163-177.
Schaeffer (Folien des Vortrags) Marc Bux
Graph Alignment
  • Kuchaiev, Oleksii, et al. "Topological network alignment uncovers biological function and phylogeny." Journal of the Royal Society Interface 7.50 (2010): 1341-1354.
Döpmann (Folien des Vortrags) Marc Bux
Reachability
  • Yildirim, Hilmi, Vineet Chaoji, and Mohammed J. Zaki. "Grail: Scalable reachability index for large graphs." Proceedings of the VLDB Endowment 3.1-2 (2010): 276-284.
Schekahn (Folien des Vortrags) Marc Bux
Max-Flow with Ford/Fulkerson
  • Sedgewick, Robert. "Algorithms in Java", Part 5, Chapter 22 (2003).
Dettmer (Folien des Vortrags) Marc Bux
Approximate Subgraph Search
  • Tian, Yuanyuan, et al. "SAGA: a subgraph matching tool for biological graphs." Bioinformatics 23.2 (2007): 232-239.
Völker Marc Bux
Algorithms for Pregel
  • Malewicz, Grzegorz, et al. "Pregel: a system for large-scale graph processing." Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (2010).
  • Salihoglu, Semih, and Jennifer Widom. "Optimizing graph algorithms on pregel-like systems." Proceedings of the VLDB Endowment 7.7 (2014): 577-588.
Akili & Hüneburg Marc Bux
Graph Partitioning
  • Rahimian, Fatemeh, et al. "Ja-be-ja: A distributed algorithm for balanced graph partitioning." Proceedings of the 7th International Conference on Self-Adaptive and Self-Organizing Systems (SASO) (2013).
Borchert & Skrzypczak Marc Bux