186.812 Networks: Design and Analysis
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2020S, VU, 2.0h, 3.0EC


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Learning outcomes

After successful completion of the course, students are able to...

- solve fundamental network design problems such as Steiner Trees and Steiner Networks using combinatorial approximation algorithms, primal-dual algorithms, integer linear programming (ILP), and branch-and-cut.
- analyze social networks using graph-theoretic concepts.
- implement algorithms to solve network design problems on standard data sets.

Subject of course

1) Network design
- Two fundamental network design problems: 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

2) 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

In the practical assignments, students will develop algorithms for solving related problems using standard network data sets available in the literature.

Teaching methods

Lectures, presentation of a research paper/book chapter, programming assignments

Mode of examination


Additional information

Total: 3 ECTS points (i.e, 75 hours):
25    hours: Lectures
10    hours: Student Presentations
20    hours: Preparing the programming exercise and homework assignments
19.0 hours: Preparing the written exam
1.0 hours: Written Exam

UPDATE: Due to the COVID-19 pandemic there will be a take home exam (with online interviews) instead of a written exam.


  • Sinnl, Markus


Course dates

Mon14:00 - 16:0009.03.2020Seminarraum FAV EG B (Seminarraum von Neumann) Lecture

Examination modalities

Oral exam (50%), programming assignments (35%), presentation (15%)

Course registration

Begin End Deregistration end
02.03.2020 09:00 25.04.2020 23:59 25.04.2020 23:59



No lecture notes are available.

Preceding courses

Accompanying courses