Achtung ! Wegen eines Fehlers wird derzeit der Studienbeitragsstatus und somit auch der Fortmeldungsstatus falsch angezeigt. An der Behebung des Fehlers wird gearbeitet. Wir danken für Ihr Verständnis!

186.812 Networks: Design and Analysis
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Networks are apparent in our daily lives. Typical examples of networks are: electrical and power networks, telephone or Internet data networks, traffic networks (highways, rail networks, airline service networks), manufacturing and distribution networks, or even social networks.


In this course, we are going to study two main aspects of networks:

1) Design of optimal network topologies. We will study two representative problems from this well-established research field using methods of complexity, algorithms and operations research.

2) Analysis of social networks. The growing public excitement by the global ``connectivity'' of the modern society has motivated scientists from multiple scientific disciplines (computer science, applied mathematics, economy and sociology) to develop this new interdisciplinary research field. We will study several graph-theoretical concept of social networks, their complexity and algorithmic approaches for their analysis.


Learning Objectives

This course should help graduate students to: a) understand information about networks, and b) develop models and algorithms to design, manage and analyse networks.

In particular the main aims of the course are to:
- provide the knowledge of the fundamental concepts of networks
- learn skills in modeling optimization or analysis tasks on networks
- learn skills in developing algorithmic techniques. This includes in particular the development of: 1) combinatorial algorithms (for polynomially solvable cases), 2) polynomial time heuristics with a constant approximation ratio and 3) exact algorithms applied to the corresponding mixed integer programming models.

Inhalt der Lehrveranstaltung

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.

Weitere Informationen

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

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.13:00 - 15:0004.03.2019 - 24.06.2019Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.13:00 - 15:0003.06.2019Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Networks: Design and Analysis - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.04.03.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.11.03.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.18.03.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.25.03.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.01.04.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.08.04.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.15.04.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.22.04.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.29.04.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.06.05.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.13.05.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.20.05.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.27.05.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.03.06.201913:00 - 15:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Mo.10.06.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.17.06.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung
Mo.24.06.201913:00 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) Vorlesung

Leistungsnachweis

Homeworks including programming exercises, student presentations and exam

LVA-Anmeldung

Von Bis Abmeldung bis
25.02.2019 09:00 20.04.2019 23:59 20.04.2019 23:59

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen

Sprache

Englisch