Universität Wien

040968 UK Graph Algorithms and Network Flows (2012S)

4.00 ECTS (2.00 SWS), SPL 4 - Wirtschaftswissenschaften
Continuous assessment of course work

FR 02.03.2012 16.00-19.30 Ort: Seminarraum 3 BWZ EG;
SA 03.03.2012 09.00-12.30 Ort: Seminarraum 3 BWZ EG;
FR 30.03.2012 16.00-19.30 Ort: Seminarraum 3 BWZ EG;
MO 16.04.2012 16.00-19.30 Ort: Hörsaal 7 BWZ 3. OG;
MO 04.06.2012 16.00-19.30 Ort: Hörsaal 7 BWZ
FR 08.06.2012 16:00.19:30 Ort: Hörsaal 7 BWZ
FR 29.06.2012 09:00-11:00 Ort: SR 3 BWZ
Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

max. 30 participants
Language: English

Lecturers

Classes

Currently no class schedule is known.

Information

Aims, contents and method of the course

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

1) Design of some optimal network topologies. We will study several 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.

Assessment and permitted materials

- Homework (25%)
- Presentation of a selected topic (15%)
- Oral exam (60%)

At least 60% in total are needed to pass the exam.

Minimum requirements and assessment criteria

This course should help graduate students to:

a) understand information about networks, and
b) develop models and algorithms to design, manage and analyse networks.

Examination topics

1) Graphs.
- Graph Traversal Algorithms. Topological Ordering.
- Dynamic Programming. Shortest Path Algorithms.
- Greedy Algorithms. Minimum Spanning Tree.
- Flow Algorithms.

2) Analysis of social networks
- Graph partitioning (strong and week ties, betweenness measures)
- 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.
- Spreading epidemics in networks: branching process, SIR vs. SIS epidemic model. Analysis of branching process.

Reading list

* Network Flows: Theory, Algorithms, and Applications, by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
* Algorithm Design, by Eva Tardos, Jon Kleinberg
* Networks, Crowds, and Markets: Reasoning About a Highly Connected World, by David Easley and
Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/networks-book/

Association in the course directory

Last modified: Mo 07.09.2020 15:29