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 Canvas 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, the 2021 edition of the course will be held remotely through online platforms. All material and links to the video-lectures, as well as announcements, will be posted in the Canvas 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 and the TAs Jonas Hansson, Taouba Jouini, and Johan Ruuskanen. Study material (lecture notes, slides, readings, exercises) will be posted as it becomes available.
L1 Monday, March 22, 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 23, 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 24, 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 25, 10:00-12:00.
E2 Friday, March 26, 10:00-12:00.
L4 Monday, March 29, 10:00-12:00. Linear network dynamics. Positive systems, linear flow dynamics, and distributed averaging. Applications: opinion dynamics, compartmental models.
E3 Tuesday, March 30, 10:00-12:00.
E4 Wednesday, March 31, 10:00-12:00.
L5 Monday, April 19, 10:00-12:00. Network flows optimization: centralized vs user optimum flows, Wardrop equilibrium, Braess paradox, price of anarchy, marginal cost pricing.
L6 Tuesday, March 20, 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.
L7 Wednesday, April 21, 10:00-12:00. Markov chains and random walks 2: speed of convergence, network conductance. Continuous-time Markov chains. Application: MM1 queues.
E5 Thursday, April 22, 10:00-12:00.
E6 Friday, April 23, 10:00-12:00.
L8 Monday, April 26, 10:00-12:00. Network epidemics: SI, SIR, SIS models.
L9 Tuesday, April 27, 10:00-12:00. Basics of game theory 1: Nash equilibrium, potential games. Positive and negative externalities.
L10 Wednesday, April 28, 10:00-12:00. Basics of game theory 2: Best response dynamics, noisy best response, convergence.
E7 Thursday, April 29, 10:00-12:00.
E8 Monday, May 3, 10:00-12:00.
L11 Tuesday, May 4, 10:00-12:00. Random graphs 1: branching process, Erdos-Renyi graph.
L12 Wednesday, May 5, 10:00-12:00. Random graphs 2: configuration model, small world and preferential attachment.
E9 Thursday, May 6, 10:00-12:00.
E10 Friday, May 7, 10:00-12:00.
E11 Monday, May 10, 13:00-15:00.
E12 Tuesday, May 11, 10:00-12:00.
E13 Wednesday, May 12, 13:00-15:00.
L13 Monday, May 17, 10:00-12:00. Network effects and contagion: linear threshold model. Application: diffusion of innovation, cascading failures in financial networks.
L14 Tuesday, May 18, 10:00-12:00. Course summary. Pointers to further studies.
E14 Thursday, May 20, 10:00-12:00.
E15 Friday, May 21, 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.