040968 UK Graph Algorithms and Network Flows (2011S)
Continuous assessment of course work
Labels
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).
- Registration is open from Mo 07.02.2011 09:00 to Th 17.02.2011 17:00
- Registration is open from We 23.02.2011 09:00 to Fr 11.03.2011 14:00
- Deregistration possible until Mo 14.03.2011 23:59
Details
max. 30 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
- Tuesday 01.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 08.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 15.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 22.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 29.03. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 05.04. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 12.04. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 03.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 10.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 17.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 24.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 31.05. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 07.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 21.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
- Tuesday 28.06. 16:30 - 18:00 Leopold-Schmetterer-Seminarraum, Universitätsstraße 5, 3.Stock
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.
- 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.
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/
* 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