Algorithm Engineering und Network Science

Vorlesung

Dr. Manuel Penschuck

Dienstag 14:15 - 16:00 in SR 307

Donnerstag 14:15 - 16:00 in SR 307

Sprechstunde: Nach Vereinbarung

Tutorials

Daniel Allendorf

Hung Tran

Donnerstag 12:15 - 14:00 in SR 307

Sprechstunde: Nach Vereinbarung

Organisation der Übungen

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Inhalt

Unser alltägliches Leben wird durch Netzwerke geprägt; Strom und Wasser erreichen uns durch entsprechende Leitungsnetze. Logistikketten stellen unsere Lebensmittel zur Verfügung und das Datennetz liefert Katzenvideos. Aber auch wir selbst bewegen uns im Straßennetz und leben meist in gleich mehreren sozialen Netzwerken.

Wenig überraschend lassen sich diese Netze als Graphen auffassen, und zeigen dann –trotz unterschiedlicher Herkunft– oft strukturelle Ähnlichkeiten. Network Science versucht diese so genannten Komplexen Strukturen zu erklären und sowohl qualitativ wie quantitativ zu analysieren. In dieser Vorlesung betrachten wir eine Auswahl von Eigenschaften von komplexen Netzwerken (z.B. Small-World, Powerlaw Gradverteilungen, Communities). Zusätzlich betrachen wir Algorithmen um solche Eigenschaten zu finden, zu produzieren, oder auszunutzen.

Prüfung

Die Prüfungsform wird während der Veranstaltung bekannt gegeben.

Übungsblätter

Materialien

• Skript Das Skript wird während des Semesters regelmäßig ergänzt und aktualisiert. Die Quellen können auf Github eingesehen werden. Pull-Requests sind willkommen!

• Folien Deg und Inc-Gen

• Buchempfehlung: Elementare Stochastik / Kersting, Wakolbinger (E-Book via Bibliothek)
• Buchempfehlung: Network Science / Barabasi
• Scalable Generation of Random Graphs
• Vorlesungsmitschrift Effiziente Algorithmen 2015
• Generating Graphs Randomly