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.

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.

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

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.

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