Das Ziel eines Seminars ist einerseits die vertiefte inhaltliche Auseinandersetzung mit einem Thema, andererseits dient ein Seminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.
Seminar: Spektrale Graphentheorie und ihre Anwendungen
- Leitung:
PD Dr. Hanjo Täubig - Modul: IN0014, IN2107
- Bereich:
2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
- Anmeldung:
Die Anmeldung erfolgt über das Matching Tool. - Zeit:
Das Seminar wird als Blockveranstaltung abgehalten:- Samstag 16.01.2021 10-16 Uhr (online: BigBlueButton)
- Samstag 23.01.2021 10-16 Uhr (online: BigBlueButton)
- Schein:
Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat. - Hörerkreis:
Studierende im Bachelorstudiengang Informatik
Studierende im Masterstudiengang Informatik
- Voraussetzungen:
Voraussetzung für die Teilnahme am Seminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der überwiegend englischsprachigen Literatur sein müssen.
Zusammenfassung
Mögliche Themen
- Graph Isomorphism Testing
- Random Walks, Cheeger Inequalities
- Diameters and eigenvalues
- Paths, Flows, and Routing
- Google's PageRank Algorithm
- Kleinberg's HITS (Hubs and Authorities) Algorithm
- Virus Spread / Epidemic Processes
- Graph Partitioning and Clustering, Spectral Image Segmentation
- Distributions of Eigenvalues and Compression
- Eigenvalue Computation
- Eigenvalues and Quasi-Randomness
- Expanders and explicit constructions
- Eigenvalues of symmetrical graphs
- Eigenvalues of subgraphs with boundary conditions
- Heat kernels
Themenverteilung
- Graph Isomorphism Testing
Robin Münk - Random Walks, Cheeger Inequalities
Lukas Retschmeier - Diameters and eigenvalues
Fabian Frank - Graph Coloring / Chromatic Number
Martin Lambeck - Paths, Flows, and Routing
Christopher Aßmus - Google's PageRank Algorithm
- - Kleinberg's HITS (Hubs and Authorities) Algorithm
Jakob Robbiani - Virus Spread / Epidemic Processes
Barbaros Ozakan - Graph Partitioning and Clustering, Spectral Image Segmentation
Ilia Khitrov - Distributions of Eigenvalues and Compression
- - Eigenvalue Computation
- - Eigenvalues and Quasi-Randomness
- - Expanders and explicit constructions
- - Eigenvalues of symmetrical graphs
- - Eigenvalues of subgraphs with boundary conditions
- - Heat kernels
-
Literatur
Es wird erwartet, dass alle Teilnehmer/-innen eigenständig geeignete Literatur (Bücher, Journal-Artikel, Konferenzbeiträge, Manuskripte / Technische Berichte, Vorlesungsunterlagen, etc.) recherchieren. Folgende Bücher könnten dabei z.B. als Grundlage dienen:- F. R. K. Chung:
Spectral Graph Theory (revised chapters) - P. Van Mieghem:
Graph Spectra for Complex Networks - Z. Stanić:
Inequalities for Graph Eigenvalues - D. Stevanović:
Spectral Radius of Graphs - U. Brandes, Th. Erlebach (Eds.):
Network Analysis - Methodological Foundations - R. A. Brualdi, S. Friedland, V. Klee (Eds.):
Combinatorial and Graph-Theoretical Problems in Linear Algebra - R. A. Brualdi, D. Cvetković:
A Combinatorial Approach to Matrix Theory and Its Applications, - B. Nica:
A Brief Introduction to Spectral Graph Theory - D. Cvetković, P. Rowlinson, S. Simić:
Eigenspaces of Graphs - H. Täubig:
Matrix Inequalities for Iterative Systems
- Spectral Graph Theory and its Applications (Daniel A. Spielman, Yale University)
- Lectures on Spectral Graph Theory (Fan R. K. Chung, University of Pennsylvania, Philadelphia)
- A brief introduction to Spectral Graph Theory (Bogdan Nica, McGill University, Montreal, Canada)
- Introduction to Spectral Graph Theory and Graph Clustering (Chengming Jiang, University of California, Davis)
Hinweise
- Vorbereitung
- Jeder Studierende wählt ein Thema, sucht sich relevante Literatur und verschafft sich einen Überblick über das Thema. Anschließend wird der Entwurf der Präsentation erstellt, dies beinhaltet beispielsweise das Erstellen der Folien und die Planung des Tafelbilds.
- Vorbesprechung
- Spätestens zwei Wochen vor dem Vortragstermin wird der Entwurf des Vortrags mit dem Betreuer besprochen. Dazu vereinbart jeder Studierende rechtzeitig einen Termin. Zu diesem Zeitpunkt muss auch mindestens die Gliederung der Ausarbeitung vorliegen.
- Seminarvortrag
- Der Seminarvortrag soll ca. 60(±5) Minuten dauern. Vortrag und Folien können auf deutsch oder englisch gehalten bzw. verfasst werden. Nach dem Vortrag hat das Publikum die Möglichkeit, Fragen zu stellen. Eine LaTeX-Vorlage für die Präsentation findet sich in diesem Ordner. Eine Powerpoint-Vorlage kann man auf der Seite vom TUM Corporate Design herunterladen (Login mit MyTUM-Kennung). Diese Vorlagen müssen nicht verwendet werden oder können bei Bedarf auch angepasst werden.
- Seminararbeit
- Die Seminararbeit ist mit Hilfe von LaTeX zu erstellen. Die Endfassung der Seminarbeit ist als PDF-Datei abzugeben. (Das PDF File kann z.B. mit pdflatex erstellt werden.) Der Umfang der Seminararbeit beträgt 10 ± 2 Seiten (ohne Abbildungen, Inhalts- und Literaturverzeichnis).
- Anwesenheit
- Jeder Studierende muss bei allen Vorträgen anwesend sein und sich aktiv an der Diskussion beteiligen.
Gute Vorträge
Hinweise zum Vorbereiten und Halten guter Präsentationen:
- Hilfreiche Hinweise zur Vorbereitung, zum Erstellen der Folien und zum eigentlichen Vortrag geben Garr Reynolds' presentation tips.
- Einige sehr wichtige Aspekte guter Vorträge sind auch im Beamer User Guide in Kapitel I.5
Guidelines for Creating Presentations
beschrieben. - Die Fokussierung auf eine wichtige Nachricht wird in der kurzen Präsentation Rethinking Presentation Design betont.
- Bei einigen Themen bietet es sich möglicherweise an, den Algorithmus in einer kurzen Live-Demonstration vorzuführen (z.B. per Java-Applet).