PORTALE DELLA DIDATTICA

### Network Dynamics and Learning

01TXLSM

A.A. 2023/24

Course Language

Inglese

Course degree

Master of science-level of the Bologna process in Data Science And Engineering - Torino

Course structure
Teaching Hours
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Teaching assistant
Context
SSD CFU Activities Area context
MAT/05 8 C - Affini o integrative Attività formative affini o integrative
2022/23
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.
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.
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.
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.
Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.
Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.
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.
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.
Theoretical lectures and practice classes. Theoretical lectures are devoted to the presentation of the topics, with definitions, properties, introductory examples, as well as a number of selected proofs which are believed to facilitate the learning process. The practice classes are devoted to train the students’ abilities to solve problems and exercises and to implement computations and simulations.
Theoretical lectures and practice classes. Theoretical lectures are devoted to the presentation of the topics, with definitions, properties, introductory examples, as well as a number of selected proofs which are believed to facilitate the learning process. The practice classes are devoted to train the students’ abilities to solve problems and exercises and to implement computations and simulations.
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.
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.
Modalità di esame: Prova orale obbligatoria; Elaborato progettuale individuale;
Exam: Compulsory oral exam; Individual project;
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam: Compulsory oral exam; Individual project;