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.
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.
VERY IMPORTANT: Due to the current COVID-19 pandemic and today's decision (2020-03-17) by the Swedish Government that all teaching activities at Swedish Universities are to be run in remote/digital modalities, the 2020 edition of the course will be held remotely with video-recorded lectures and exercise and consulting sessions held through online platforms. All material and links to the video-lectures, as well as announcements, will be posted in the Piazza page of the course. Please, do activate your account so that you can stay updated. For any issue, please contact the course responsible.
Below is the schedule for the lectures and exercises for Spring 2020. This year the course will be held by Giacomo Como with collaboration from Dr. Richard Pates the TAs Martin Heyden, Taouba Jouini, and Johan Ruuskanen. Study material (lecture notes, slides, readings, exercises) will be posted as it becomes available.
L1 Monday, March 23, 10:00-12:00. 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 Tuesday, March 24, 10:00-12:00. 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, production networks.
L3 Wednesday, March 25, 10:00-12:00. Network connectivity: Menger's theorem. Network flows: link-node incidence matrix, the max-flow min-cut theorem. Application: resilience of transportation networks.
E1 Thursday, March 26, 10:00-12:00.
E2 Friday, March 27, 10:00-12:00.
L4 Monday, March 30, 10:00-12:00. Linear network dynamics. Positive systems, linear flow dynamics, and distributed averaging. Applications: opinion dynamics, compartmental models.
L5 Tuesday, March 31, 10:00-12:00. 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: gambler's ruin.
L6 Wednesday, April 1, 10:00-12:00. Markov chains and random walks 2: speed of convergence, network conductance. Continuous-time Markov chains. Application: MM1 queues.
E3 Thursday, April 2, 10:00-12:00.
E4 Friday, April 3, 10:00-12:00.
E5 Monday, April 6, 10:00-12:00.
L7 Tuesday, April 7, 10:00-12:00. Network epidemics: SI, SIR, SIS models.
E6 Thursday, April 9, 10:00-12:00.
E7 Monday, April 27, 10:00-12:00.
L8 Tuesday, April 28, 10:00-12:00. Network flows optimization: centralized vs user optimum flows, Wardrop equilibrium, Braess paradox, price of anarchy, margial cost pricing.
L9 Wednesday, April 29, 10:00-12:00. Basics of game theory 1: Nash equilibrium, potential games. Positive and negative externalities.
E8 Monday, May 4, 10:00-12:00.
L10 Tuesday, May 5, 10:00-12:00. Basics of game theory 2: Best response dynamics, noisy best response, convergence.
L11 Wednesday, May 6, 10:00-12:00. Random graphs 1: branching process, Erdos-Renyi graph.
L12 Thursday, May 7, 10:00-12:00. Random graphs 2: configuration model, small world and preferential attachment.
E9 Friday, May 8, 10:00-12:00.
L13 Monday, May 11, 10:00-12:00. Network effects and contagion: linear threshold model. Application: diffusion of innovation, cascading failures in financial networks.
L14 Tuesday, May 12, 10:00-12:00. Course summary. Pointers to further studies.
E10 Wednesday, May 13, 10:00-12:00.
E11 Thursday, May 14, 13:00-15:00.
E12 Friday, May 15, 10:00-12:00.
E13 Monday, May 18, 13:00-15:00.
E14 Tuesday, May 19, 10:00-12:00.
E15 Wednesday, May 20, 10:00-12:00.
Exam Friday, June 5, 14:00-19:00, room MA:10I-J.
Retake exam Friday, August 21, 8:00-13:00, room MA:10D.