Knowledge of: - Elements of algebraic and topological graph theory with special emphasis on connectivity, centrality, and network flows. - Elements of non-negative matrix theory (stochastic and substochastic matrices), their spectral properties, and their use in the mathematical modelling of deterministic and stochastic network dynamics. - Elements of Markov processes over networks (random walks, epidemic spreading, randomized algorithms) - Convex optimization problems over large scale network (flow optimization, inference, learning). Distributed algorithms. - Elements of game theory and learning dynamics. Mechanism design. - Basics of probabilistic graphical models: Bayesan networks and random Markov fields. - Basics of models of random graphs and their fundamental properties Ability to: - Construct and compare mathematical models for interconnected systems arising in information, social, economic, biological, and infrastructure networks. - Apply basics notions of algebraic and topological graph theory, Markov processes, game theory, and dynamical systems in order to analyze networks and interconnected dynamical systems. - Critically identify and evaluate network properties such as centrality, connectivity, emerging behaviors, and scalability. - Design and propose cooperative distributed algorithms on networks, to evaluate their asymptotics, speed of convergence, and complexity, and to implement them on modern platforms for numerical simulation.
This course aims at presenting the mathematical foundations of networks with special emphasis on dynamical models both of deterministic and stochastic nature, as well to illustrate their main engineering applications. The course covers the basics of: graph theory, non-negative matrices, Markov probabilistic models, game theory, distributed optimization. It introduces the student to several applications: distributed optimization and inference algorithms, opinion dynamics, epidemics models, learning in games.
1. Topological and algebraic graph theory - Basics of graph theory. Directed acyclic graphs, undirected graphs: properties and examples. Combinatorial properties of trees and bipartite graphs. Eulerian circuits. Connected components and condensation graph. Cliques, independent sets, coverings, matchings, and colorings. - Matrices associated to a graph: weight, adjacency, stochastic, and Laplacian matrices. Perron-Frobenius theorem and spectral properties of nonnegative matrices. - Network centrality (degree, eigenvector, Bonacich, Page-rank, Katz). - Network connectivity and flows: Menger’s theorem, max-flow/min-cut theorem. - Applications: constraints satisfaction problems (e.g., scheduling, allocation), social and economic networks, resilience of infrastructure networks. 2. Distributed averaging and linear flow dynamics - Distributed averaging and compartmental systems for closed networks. Convergence theorems, role of centrality. - Dynamics with exogeneous inputs. Properties of sub-stochastic matrices, convergence results. - Applications: distributed estimation and computation on a network, opinion dynamics, wisdom of crowds, social influence, flow diffusion. 3. Distributed optimization - Optimization of convex separable functions with linear coupling constraints. - Network flow optimization: duality, Lagrange multipliers as marginal costs. - Electrical networks: effective resistance, Rayleigh’s variational principle. - Network flow optimization: system optimum traffic assignment, Wardrop equilibrium, price of anarchy, marginal cost mechanisms. -Applications: energy and transportation systems. 4. Markov chains - Discrete- and continuous-time Markov chains: stationary distributions, convergence, ergodic theorem, reversibility, hitting and return times, absorbing probabilities. - Notable examples: birth-and-death chains, random walks on graphs. - Mixing time, conductance, rapid mixing, coupling, - Applications: Markov Chain Monte Carlo, Metropolis-Hastings algorithm, Gibbs sampling. 5. Contagion and diffusion over networks - Pairwise interacting models: general definition and properties. - Epidemic models (SI, SIS, SIR), voter model, evolutionary dynamics. - Computation of the absorbing times and absorbing probabilities for simple topologies (complete, line, star). - Detection and control policies. - Applications: diffusion of innovations, evolutionary competition, spread of rumors and fake news, network security. 6. Game theory and learning - Non-cooperative games in strategic form, best response, dominant strategies, Nash equilibria. mixed strategies, correlated strategies. - Classical examples. Symmetric games. Potential and congestion games. - Network games. Examples: coordination and anti-coordination, graph coloring, quadratic games. - Learning: best response dynamics, log-linear learning, fictitious play. - Mechanism design. - Applications: behavior of social and economic networks, pricing mechanisms in markets, algorithms for combinatorial optimization. 7. Probabilistic graphical models - Bayesian networks - Markov random fields. Ising model and Glauber dynamics. Boltzmann machines. - Distributed inference: computation of marginal and posterior distributions, likelihood maximization, 8. Random graphs - Branching processes. - Erdos-Renyi random graph: phase transitions for connectivity and for the existence of a giant component. - Random graphs with preassigned degree distribution (configuration model). - Preferential attachment and small world models.
Modalita di esame: Prova orale obbligatoria;
Exam: Compulsory oral exam;
... Exam: compulsory oral exam; individual essay; The assessment consists of two parts: 1. Three homework assignments (HW1, HW2, HW3) that will be assigned to the students during the course HW1 and HW2 consist of exercises that are aimed at assessing the students’ achieved learning level of the theoretical aspects and their ability to select relevant principles to solve the proposed problems. In addition to an exercise part of the same nature as in HW1 and HW2, the HW3 assignment includes a small project that involves numerical simulations as well as deductive and analytical reasonings and is aimed at testing the mathematical modelling abilities of the students and their ability to present their analyses and results in a proper format of a written report such that a technically qualified person can follow and obtain similar findings. Students will have two weeks each to submit their HW1 and HW2 reports, and three weeks to submit their HW3 report. 2. An oral test consisting of two parts: (2a) a discussion of the submitted HW1, HW2, and HW3 reports, aimed at testing the depth of the students’ understanding of the subjects and their ability to explain, defend, reflect, critically evaluate, and possibly improve their work; (2b) a presentation of a tpic studied in the course covering both theoretical aspects and possibly their applications. The topic is chosen by the examination committee and communicated to the student, who has 30 minutes to prepare her/his presentation: during this time the student has access to books, notes, and other learning material. This part of the oral test is aimed at evaluating the breadth and depth of the kwoledge acquired by the student, and her/his ability to effectively present and communicate it to a technically qualified audience. Grading: the maximum grade for HW1, HW2, and HW3, upon the discussion detailed at point (2a) above, is of 4,4, and 6 points, respectively. If HW1, HW2, and HW3 are not submitted by their deadline, the maximum grades above are lowered to 3, 3, and 5 points, respectively. The maximum grade for part (2b) of the oral test is 18 points. The final course grade is then obtained by summing up the final grades in HW1, HW2, HW3, and of part (2b) of the oral test: if such sum is less than or equal to 30, the final grade coincides with it, if the sum is strictly larger than 30 the final grade is 30 cum laude.
Part of the course topics are covered by lecture notes that will be made available to the students through the Portale della Didattica. Other material will be suggested in class and made avalaible thorugh the Portale della Didattica.
