Network Dynamics (FRTN30/FRTN30F)
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 2017. This year the course will be held by Giacomo Como together with Giulia Giordano, and Jacob Bergstedt will help with exercise sessions. Study material (lecture notes, slides, readings, exercises) will be posted as it becomes available.
L1 Monday, 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 Tuesday, 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.
E1 Thursday, March 23, 10:00-12:00, room M:L1.
E2 Friday, March 24, 10:00-12:00, room M:M1.
L3 Monday, March 27, 10:00-12:00, room M:E. Network connectivity and flows: the max-flow min-cut theorem.
L4 Tuesday, March 28, 10:00-12:00, room M:E. Linear network dynamics. Positive systems, compartmental models, and distributed averaging. Applications: opinion dynamics, compartmental models.
E3 Thursday, March 30, 10:00-12:00, room M:L1.
E4 Friday, March 31, 10:00-12:00, room M:M1.
L5 Monday, April 3, 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.
E5 Thursday, April 6, 10:00-12:00, room M:L1.
E6 Friday, April 7, 10:00-12:00, room M:M1.
L7 Monday, April 24, 10:00-12:00, room M:E. Network flows optimization: centralized vs user optimum flows, Wardrop equilibrium, Braess paradox, price of anarchy.
L8 Tuesday, April 25, 10:00-12:00, room M:E. Basics game theory 1: Nash equilibrium, potential games. Positive and negative externalities.
E7 Thursday, April 27, 10:00-12:00, room M:L1.
E8 Friday, April 28, 10:00-12:00, room M:M1.
L9 Tuesday, May 2, 10:00-12:00, room M:D. Basics game theory 2: Best response dynamics, noisy best response, convergence.
L10 Wednesday, May 3, 8:00-10:00, room M:E. Random graphs 1: branching process, Erdos-Renyi graph.
E9 Thursday, May 4, 10:00-12:00, room M:L1.
E10 Friday, May 5, 10:00-12:00, room M:M1.
L11 Monday, May 8, 10:00-12:00, room M:E. Random graphs 2: configuration model, small world and preferential attachment.
L12 Tuesday, May 9, 10:00-12:00, room M:E. Network epidemics: SI, SIR, SIS models.
E11 Thursday, May 11, 10:00-12:00, room M:L1.
E12 Friday, May 12, 10:00-12:00, room M:M1.
L13 Monday, May 15, 10:00-12:00, room M:E. Network effects and contagion: linear threshold model. Application: diffusion of innovation, cascading failures in financial networks.
L14 Tuesday, May 16, 10:00-12:00, room M:E. Course summary. Pointers to further studies.
E13 Thursday, May 18, 10:00-12:00, room M:L1.
E14 Friday, May 19, 10:00-12:00, room M:M1.