Nätverksdynamik, 7.5 hp
Networks permeate our modern societies. Everyday, we exchange information through the World Wide Web and other communication networks, modify our opinions and make decisions under the influence of our social interactions, commute across road networks, buy goods made available to us by production and distribution networks, use electrical power, gas and water that infrastructure networks bring directly to our homes, invest our savings in highly interconnected networks of financial funds, ...
This course will focus on common principles at the heart of the functioning of these networks and will show how the same notions related to connectivity, resilience and fragility, centrality and influence arise in several different domains. It will both introduce mathematical tools from graph theory, random graphs, dynamical systems, optimization and game theory, and cover a wide variety of applications including: opinion dynamics and learning in social networks; economic and financial networks; communication networks and the Internet; consensus and gossiping; spread and control of epidemics; dynamics and control of transportation and power networks.
All basic information will be availble at this webpage. Course material etc will be made available to registered students via the Piazza course page. There will be four hand-ins (whose completion is compulsory to pass and whose on-time submission and most oustanding solutions give extra points for the grading) and a final exam (determining the grade along with the possible extra points collected from the hand-ins). For further inquiries, please contact the responsible for the course, Giacomo Como.
Below is the schedule for the lectures and exercises for Spring 2018. This year the course will be held by Giacomo Como with collaboration from the TAs Kaito Ariu, Gustav Nilsson, and Christian Rosdahl. Study material (lecture notes, slides, readings, exercises) will be posted as it becomes available.
L1 Tuesday, March 20, 10:00-12:00, room M:E. Course introduction. Graphs and networks: basic notions such as adjacency and weight matrices, walks and paths, distance and diameter, degree distributions, clustering and modularity. Application: the structure of Facebook.
L2 Wednesday, March 21, 10:00-12:00, room M:E. Network centrality: Laplacian and normalized adjacency matrices, connected components and dimension of the eigenspaces, centrality measures including Bonacich, Katz, PageRank, betweenness and closeness. Application: Google's Pagerank.
L3 Thursday, March 22, 10:00-12:00, seminar room of the Autiomatic Control Dept. (M:2112B). Network connectivity: Menger's theorem. Network flows: link-node incidence matrix, the max-flow min-cut theorem. Application: resilience of transportation network to capacity losses.
E1 Friday, March 23, 10:00-12:00, room M:R.
L4 Tuesday, March 27, 10:00-12:00, room M:E. Linear network dynamics. Positive systems, linear flow dynamics, and distributed averaging. Applications: opinion dynamics, compartmental models.
L5 Wednesday, March 28, 10:00-12:00, room M:E. Markov chains and random walks 1. Convergence to and form of the stationary probability distribution. Absorbing probabilities and hitting times. Reversible stochastic matrices, birth-and-death chains. Application: the gambler's ruin.
E2 Thursday, March 29, 08:00-10:00, room M:R.
E3 Thursday, March 29, 10:00-12:00, room M:R.
L6 Tuesday, April 17, 10:00-12:00, room M:E. Markov chains and random walks 2: speed of convergence, network conductance. Continuous-time Markov chains. Application: MM1 queues.
L7 Wednesday, April 18, 10:00-12:00, room M:E. Network flows optimization: centralized vs user optimum flows, Wardrop equilibrium, Braess paradox, price of anarchy, margial cost pricing.
E4 Thursday, April 19, 10:00-12:00, room M:R.
E5 Friday, April 20, 10:00-12:00, room M:R.
L8 Tuesday, April 24, 10:00-12:00, room M:E. Basics of game theory 1: Nash equilibrium, potential games. Positive and negative externalities.
L9 Wednesday, April 25, 10:00-12:00, room M:E. Basics of game theory 2: Best response dynamics, noisy best response, convergence.
E6 Thursday, April 26, 10:00-12:00, room M:R.
E7 Friday, April 27, 10:00-12:00, room M:R.
E8 Wednesday, May 2, 10:00-12:00, room M:E.
E9 Thursday, May 3, 10:00-12:00, room M:R.
E10 Friday, May 4, 10:00-12:00, room M:R.
L10 Tuesday, May 8, 10:00-12:00, room M:E. Random graphs 1: branching process, Erdos-Renyi graph.
L11 Wednesday, May 9, 10:00-12:00, room M:E. Random graphs 2: configuration model, small world and preferential attachment.
E11 Thursday, May 9, 15:00-17:00, room M:R.
E12 Monday, May 14, 13:00-15:00, room M:R.
L12 Tuesday, May 15, 10:00-12:00, room M:E. Network epidemics: SI, SIR, SIS models.
L13 Wednesday, May 16, 10:00-12:00, room M:E. Network effects and contagion: linear threshold model. Application: diffusion of innovation, cascading failures in financial networks.
E13 Thursday, May 17, 10:00-12:00, room M:R.
E14 Friday, May 18, 10:00-12:00, room M:R.
L14 Tuesday, May 23, 10:00-12:00, room M:E. Course summary. Pointers to further studies.
Exam Saturday, June 2, 8:00-13:00, room Kårhusets Gasquesal.
Retake exam Friday, August 24, 14:00-19:00, room MA:9D.