University of Konstanz
Algorithmics Group
Prof. Dr. Ulrik Brandes

Network Analysis (SS 2012)


Networks are omnipresent these days. Besides physical networks as, e.g., in electrical engineering or transportation systems, abstract networks as the structure of the WWW or constellations of political actors are increasingly analysed. Due to the variety of applications and resulting research questions, a wide range of methods is applied leading to interesting coherences between graph theory, linear algebra and probabilistic methods. In this course, some of the used methods and their theoretical foundations are presented. While research questions will be motivated by examples of application, the focus, however, will be on algorithmic approaches to these problems as well as their assumptions and characteristics. Moreover, we will come across a number of open questions that invite to further work on this topic.

General Information

Lecture (U. Brandes) Tue 18:45 - 20:15 (D 436)
Wed 17:00 - 18:30 (D 436)
Tutorial (N. Indlekofer,
U. Nagel, B. Nick)
Mon 17:00 - 18:30 (E 403)
Oral Exam 1st date: to be announced
2nd date: to be announced

Please register for this course in the StudIS and LSF.

Homework Assignments

Normally, the assignments are made available on this webpage as a PDF-file (in English) every Thursday at 10:00.

The editing time for each homework is one week. It is due on the next Thursday at 10:00. The assignments have to be delivered in written form either in English or German. You can choose to either deposit them in the box for handout marked "Abgabe" in front of the door to room E 202, or to submit them electronically to the three teaching assistants (as one PDF only). In the latter case, please follow the naming schema uXX_name1_name2.pdf, where XX indicates the number of the assignment. We will return the corrected and scored assignments in the tutorial. Whatever is not picked up will be placed back into the handout box marked "Rückgabe".

The requirements for the admittance to the final exam are 50 percent of the total score of the assignments, regular attendance at the tutorials, and the presentation of at least two of your solutions of the assignments. In writing up your assignments, be as clear, precise, and concise as possible. Understandability will be an important factor in the scoring of the assignments. There will be approximately twelve written assignments. Regular attendance is considered especially for borderline cases.

You are permitted and encouraged to work in groups of two.

No. Posted Due Date Tutorial Download Tutor Additional Material
00 17.04.2012 20.04.2012 Assignment0.pdf Natalie
01 19.04.2012 26.04.2012 30.04.2012 Assignment1.pdf Uwe references.bib
02 26.04.2012 03.05.2012 07.05.2012 Assignment2.pdf Natalie
03 03.05.2012 10.05.2012 14.05.2012 Assignment3.pdf Uwe
04 10.05.2012 17.05.2012 21.05.2012 Assignment4.pdf Uwe
05 17.05.2012 24.05.2012 04.06.2012 Assignment5.pdf Natalie
06 24.05.2012 31.05.2012 04.06.2012 Assignment6.pdf Natalie slides
07 31.05.2012 07.06.2012 11.06.2012 Assignment7.pdf Bobo
08 07.06.2012 14.06.2012 18.06.2012 Assignment8.pdf Bobo football data
09 14.06.2012 21.06.2012 25.06.2012 Assignment9.pdf Bobo
10 21.06.2012 28.06.2012 02.07.2012 Assignment10.pdf Bobo/Uwe
10 28.06.2012 05.07.2012 09.07.2012 Assignment11.pdf Uwe
10 05.07.2012 12.07.2012 16.07.2012 Assignment12.pdf Uwe

Course Notes and Supplemental Material

Non-public material is accessible only from local machines (IP 134.34.*.*) or via VPN.

  • Lecture notes from previous edition of this course (in German). Note that the content is revised substantially this year.
  • First tutorial: Review of basic definitions and notations
  • Lecture notes for this edition. We will attempt to provide updates in a timely manner.
  • Friendship Paradox
  • Attempted definitions: social network, network analysis
  • Textbooks

    Further Information (in German)