Course syllabus
Nätverksdynamik
Network Dynamics
FRTN30, 7,5 credits, A (Second Cycle)
Valid for: 2014/15
Decided by: Education Board B
Date of Decision: 2014-04-08
General Information
Elective for: D4, E4-ra, F4, F4-r, Pi4-bg
Language of instruction: The course will be given in English
Aim
Networks are ubiquitous in our modern society: infrastructure
networks, providing communication, transportation, energy services;
social networks, determining our information, influencing our
opinions, and shaping our political views; economic and financial
networks, determining the nature of economic interactions and
financial linkages; and natural networks (e.g., biological and
physical networks), governing the evolution and spread of natural
phenomena.
This course will focus on common mathematical principles that
permeate the structure and functioning of these networks. It will
introduce conceptual tools from dynamical systems, (random) graph
theory, Markov chains, optimization and game theory. It will also
cover a variety of applications including: learning and
informational cascades; economic and financial networks; social
influence networks; formation of social groups; communication
networks and the Internet; consensus and gossiping; spread and
control of epidemics; control of transportation and energy
networks.
Learning outcomes
Knowledge and understanding
For a passing grade the student must
- know the basic principles of graph theory and apply them to
model real-world networks
- have insight in the basic differences between different models
of random graphs
- be familiar with the properties of random walks on graphs
- be able to analyze simple dynamical systems over networks
- understand emerging phenomena in large-scale networks
- be able to give an overview of modern directions in network
science.
Competences and skills
For a passing grade the student must
- be able to analyze properties of (random) graphs both
quantitatively and qualitatively
- be able to handle basic analytical computations for random
walks
- be able to analyze simple dynamical systems over networks and
to relate their behavior to the network structure
- be able to use computer tools for simulation and analysis of
networks.
Judgement and approach
For a passing grade the student must
- be able to understand relations and limitations when simple
models are used to describe complex networks
- be able to evaluate dominating emerging phenomena in network
dynamics
- show ability for teamwork and collaboration in groups.
Contents
- Basic graph theory: connectivity, degree distributions, trees,
adjacency matrices, spectrum.
- Random graphs: Erdos-Renyi, configuration model, preferential
attachment, small-world, branching process approximations.
- Flows and games on graphs: max-flow min-cut, optimal transport,
Wardrop equilibria, evolutionary dynamics.
- Random walks on graphs: invariant distributions, hitting times,
mixing times.
- Dynamical systems on graphs: distributed averaging, interacting
particle systems, epidemics, opinion dynamics. Mean-field and
branching process approximations.
Examination details
Grading scale: TH
Assessment: Written exam (5 hours), four homework assignments. When less then five registered the exam may be oral.
Parts
Code: 0115. Name: Examination.
Credits: 7,5. Grading scale: TH.
Code: 0215. Name: Homework Assignment 1.
Credits: 0. Grading scale: UG.
Code: 0315. Name: Homework Assignment 2.
Credits: 0. Grading scale: UG.
Code: 0415. Name: Homework Assignment 3.
Credits: 0. Grading scale: UG.
Code: 0515. Name: Homework Assignment 4.
Credits: 0. Grading scale: UG.
Admission
Required prior knowledge: FRT010 Automatic Control, Basic Course.
The number of participants is limited to: No
Reading list
- D. Easley & J. Kleinberg: Networks, crowds and markets, reasoning about a highly connected world. Cambridge University Press, 2010, ISBN: 978-0-521-19533-1, Supplement to lecturer's notes.
- R. Van Der Hofstad: Random Graphs and Complex Networks. Supplement to lecturer's notes. Online available at http://www.win.tue.nl/~rhofstad/.
- D. Levin, Y. Peres, E. Wilmer: Markov chains and mixing times. American Mathematical Society, 2009, ISBN: 978-0-8218-4739-8, Supplement to lecturer's notes.
Contact and other information
Course coordinator: Giacomo Como, giacomo.como@control.lth.se
Director of studies: Karl-Erik Årzén, karlerik@control.lth.se