|Politecnico di Torino|
|Academic Year 2017/18|
Stochastic processes/Dynamics over networks
Master of science-level of the Bologna process in Mathematical Engineering - Torino
This course aims at presenting the foundations of stochastic processes and graph theory and their applications in the mathematical modelling of network dynamics. The course covers stochastic processes both in discrete and continuous time with special focus on their engineering applications, the foundations of both algebraic and topological graph theories, and the theory of stochastic matrices. It then focuses on both deterministic and stochastic dynamical processes on graphs. Finally, it introduces the student to several applications: queuing theory, distributed inference algorithms, opinion dynamics, epidemics models, game theory and learning.
Expected learning outcomes
- Elements of stochastic processes and their main properties
- Elements of algebraic and topological graph theory with special emphasis on centrality, connectivity, periodcity of a node, and network flows.
- Nonnegative matrix theory (stochastic and substochastic matrices), their spectral properties, and their use in the mathematical modelling of deterministic and stochastic network dynamics.
- Basics of convex network flow optimization, game theory, and related evolutionary dynamics.
- Basic models of random graphs and their fundamental properties
- Identify and select the proper stochastic processes to model non-deterministic system dynamics.
- Analyze stochastic dynamical models and their main associated random variables, such as waiting and absorbing times, as well as stationarity conditions and related distributions.
- Construct and compare mathematical models for interconnected systems arising in social, economic, biological, and infrastructure networks.
- Apply basic notions of algebraic and totpological 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.
Prerequisites / Assumed knowledge
Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.
1. Topological and algebraic graph theory
- Basics in graph theory: paths, cycles, connectivity, distance, diameter. Undirected graphs: properties and examples (complete, trees, cycle, grids). Combinatorial properties of trees. Bipartite graphs and their properties. Eulerian circuits. Connected components of a graph and the concept of condensation graph. Period of a node. Characterization of aperiodicity and related properties.
- Weight matrix of a graph and its powers. Matrices associated with aperiodic graphs. Stochastic matrix and Laplacian associated to a graph. Perron-Frobenius theorem. Spectral properties of stochastic matrices. Centrality (degree, eigenvector, Bonacich, Page-rank, Katz).
- Reversible stochastic matrices. Dirichlet form. Variational characterization of the second eigenvalue of a reversible matrix. Conductance and Cheeger bound. Example.
- Connectivity and flows on a network: Menger’s theorem, max-flow/min-cut theorem.
2. Averaging and linear flow dynamics
- Distributed averaging and compartmental systems for closed networks and for networks with exogeneous inputs.
- Convergence theorems, role of centrality, bi-stochastic matrices.
- Applications: distributed estimation on a network, Mteorpolis algorithm, opinion dynamics (De Groot model), wisdom of crowds, influential models for social networks, linear flow dynamics, distribued algorithms for computing centrality.
- Bounds on convergence times for reversible stochastic matrices: role of the second eigenvalue. Spectra of circulant matrices and Kronecker products. Exlicit computation of spectra for notable graphs: complete, cycles, grids, hypercubes, stars.
- Sub-stochastic matrices and their properties. Speed of convergence for distributed averaging and compartmental systems with inputs.
- Positive and monotone dynamical systems: definition and basic properties.
3. Introduction to stochastic processes
- Definition of a stochastic process and discussion of its main characterizations and properties.
- Filtrations and stopping times.
-Discrete time martngale and related properties. Decomposition of supermartingales and submartingales. Doob’s theorem, convergence.
- Processes with stationary increments and with independent increments.
- Brownian motions: definition, main properties, applications.
- Poisson processes: equivalent definitions, main results, generalizations (non-homogeneous, composed, mixed).
4. Markov chains
- Discrete time Markov processes and their properties, transition matrices, Chapman-Kolmogorov equations, classification of states, convergence in law and ergodic theorem for irreducible chains. Unicity of the invariant distribution.
- Mean hitting times and hitting probabilities of absorbing states, return times and Kac’s theorem. Role of the fundamental matrix.
- Notable examples: reversible chains and birth and death chains, random walks on graphs. Branching processes: extinction probabilities, critical threshold, supercritical and subcritical processes.
- Continuous time Markov processes and their representations, continuous time birth and death processes, Kolmogorov equations, invariant distributions, balance equations.
- Coupling, variational distance, mixing time.
- Stochastic domination of I and II order. Application to the study of the asymptotic behavior of Markov chains.
5. Optimization of network flows
- Optimization of network flows with separable convex costs, necessary and sufficient conditions for optimality, duality, interpretation of Lagrange multipliers as marginal costs.
- Electrical networks: interpretation of Ohm and Kirchoff laws, effective resistance, Rayleigh’s variational principle. Application to reversible Markov chains and to influential models on social undirected networks.
- Optimization of network flows: system optimum, Wardrop equilibrium, price of anarchie, use of incentives and disincentives. Application to transportation newtorks.
6. Evolutionary game theory
- Introduction to non-cooperative game theory. Games in strategic form, best response, dominant strategies, Nash equilibria. Classical examples.
- Potential and congestion games.
- Network games. Examples: majority, minority, graph coloring.
- Analysis of best response and noisy best response dynamics.
7. Epidemics and pairwise interacting models.
- Pairwise interacting models: general definition and properties.
- Averaging gossip algorithms.
- Epidemic models (SI, SIS, SIR), voter model.
- Computation of the absorbing times and absorbing probabilities for simple topologies (complete, line, star).
- Ergodic models (noisy voter model, SIS with spontaneous mutation).
8. Mean field limits
- Interaction models on a complete graph with anonymous transition matrix. Examples. Process of empirical frequencies.
- Hydrodynamic limit: Kurtz’s theorem and the limit ODE
- Hydrodynamic limit of binary models: voter, SIS, majority, k-majority.
- Ergodic models: relation between the invariant distribution and the equilibria of the corresponding ODE.
- Multi-dimensional examples: SIR, SIRS, heterogeneous models.
9. Random graphs
- Erdos-Renyi random graph: definition, properties, degree distribution, branching process approximation, connectivity threshold, threshold for the existence of a giant component.
- Random graphs with preassigned degree distribution (configuration model): elementary properties, branching process approximation, threshold for connectivity and for the existence of a giant component
- Other random graph models: preferential attchment, small world.
- Hydrodynamic limit of memoryless dynamics on random graphs with preassigned degree distribution.
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.
Texts, readings, handouts and other learning resources
Part of the course topics are covered by lecture notes that will be made available to the students through the Portale della Didattica.
Other reference texts are:
- S.N. Ross, Stochastic Processes, 2nd Edition, Wiley.
- J. Jacod and P. Protter, Probability Essentials, Springer, 2000
- D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (online available).
Other material will be suggested in class and made avalaible thorugh the Portale della Didattica.
Assessment and grading criteria
The assessment consists of two parts:
1. Three homework assignments (HW1, HW2, HW3) that will be assigned to the students towards the end of October, November, and December (before Christmas break), respectively. 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 two topics studied in the course covering both theoretical aspects and possibly their applications. The two topics are 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.
Please contact the course responsible, Professor Fabio Fagnani, firstname.lastname@example.org
Programma definitivo per l'A.A.2017/18