TU Wien:Networks: Design and Analysis VU (Sinnl)

Aus VoWi
Wechseln zu: Navigation, Suche

Daten[Bearbeiten]

Inhalt[Bearbeiten]

Split up in two parts:

Network design

  • Steiner trees and Steiner networks (aka survivable network design problems).
  • Complexity, combinatorial algorithms with constant approximation ratio, primal-dual algorithms, integer linear programming (ILP) models and branch-and-cut

Analysis of social networks

  • Strong and week ties, betweenness measures, graph partitioning
  • Networks in their surrounding contexts: homophily, affiliation
  • Positive and negative relationships: structural balance, weaker form of structural balance, generalization
  • Cascading behavior in networks: diffusion, cascades and clusters. Knowledge, threshold and collective action. The cascade capacity.
  • Basics of Game Theory and its application to Networks
  • Influence Maximization in Networks
  • Link Analysis and Web Search

Ablauf[Bearbeiten]

Four lectures on saturdays, normaly around three hours long and not like the planned four hours.
Last lecture was only an hour long.
Studentpresentation about some book chapter, presentation of programming exercises and a test at the and.

Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten]

Basic understanding of algorithms (Algodat 1 + 2) some programing knowledge for the exercises.

Vortrag[Bearbeiten]

The lecture is based on the book the professor uses and the slides are heavily based on that and also have a lot of text on them (are the sole material for learning). In geral interessting even though quick paced and one should stay focused to understand everything what gets presented.

Übungen[Bearbeiten]

One programming exercise for network design (Influence maximization with independent cascade model), second programming exercise network analysis with an implementation of a shortest path heuristic and dual ascend.
The exercises are interesting and challenging, the steinlib fileformat gets used to parse the input of the graph's (the description is not accurate on the webpage).

Prüfung, Benotung[Bearbeiten]

Written exam in the last lecture - ~ 1 hour (was not so strict, waited until everybody finished the exam). All in all not so difficult, reading all the slides a couple of times and doint the examples on the slides is enough. Roughly one or two good learning days are enough.

Dauer der Zeugnisausstellung[Bearbeiten]

noch offen

Zeitaufwand[Bearbeiten]

  • one day for reading the chapter/paper for the presentation and making a presentation
  • For each programming exercise ~ 1 or 2 Days
  • about the same for the exam in the end.

Unterlagen[Bearbeiten]

noch offen

Tipps[Bearbeiten]

  • Don't underestimate the programming exercise, it takes for a team of two people easily two or three days.
  • Calculate/do the algorithms on the slides, helps for the exam

Verbesserungsvorschläge / Kritik[Bearbeiten]

noch offen