PORTALE DELLA DIDATTICA

Dynamics on networks and graphs

01TXLSM

A.A. 2021/22

2021/22

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Network Dynamics and Learning

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Dynamics on networks and graphs

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Network Dynamics and Learning

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Network Dynamics and Learning Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

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.

Network Dynamics and Learning

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.

Dynamics on networks and graphs

Modalit� di esame: Prova orale obbligatoria;

Network Dynamics and Learning

Modalit� di esame: Prova orale obbligatoria; Elaborato progettuale individuale;

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Exam: Compulsory oral exam;

Network Dynamics and Learning

Exam: Compulsory oral exam; Individual project;

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Modalit� di esame:

Network Dynamics and Learning

Modalit� di esame: Prova orale obbligatoria; Elaborato scritto individuale;

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Exam:

Network Dynamics and Learning

Exam: Compulsory oral exam; Individual essay;

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Modalit� di esame:

Network Dynamics and Learning

Modalit� di esame: Prova orale obbligatoria; Elaborato scritto individuale;

Dynamics on networks and graphs

Network Dynamics and Learning

Dynamics on networks and graphs

Exam:

Network Dynamics and Learning

Exam: Compulsory oral exam; Individual essay;

Dynamics on networks and graphs

Network Dynamics and Learning