Le but de ce cours est double :

• proposer des modèles mathématiques pertinents pour les réseaux (e.g. réseaux de communications, réseaux sociaux);

• donner les bases théoriques permettant de mener à bien l'analyse de la dynamique de ces modèles.

Le cours est structuré en thèmes, pouvant être plus ou moins développés suivant les années :

• Graphes aléatoires (e.g. Erdos-Renyi, attachement préférentiel), en relation avec la modélisation des réseaux sociaux.

• Réseaux de files d'attente et applications, modélisation markovienne;

• Optimisation et contrôle stochastique pour les réseaux (processus markoviens de décision, apprentissage par renforcement);

Horaire: Le cours sera structuré en 8 séances de 3h chacune. Il aura lieu le mardi de 16:15 a 19:15 en période 1 (première séance: 16 septembre).

Lieu: Bâtiment Sophie Germain, salle 1004. Le cours aura lieu en anglais si un ou plusieurs étudiants le demandent et en français sinon.

Le programme et les intervenants:

1. Graphes aléatoires et applications aux réseaux sociaux (9h, L. Massoulié);
2. Réseaux de files d'attente et applications; optimisation et contrôle stochastique pour les réseaux (15h, A. Busic).

* 16/09/25 Laurent Massoulié 1

* 23/09/25 Ana Busic 1

* 30/09/25 Ana Busic 2

* 07/10/25 Laurent Massoulié 2

* 14/10/25 Laurent Massoulié 3

* 21/10/25 Ana Busic 3

* 04/11/25 Ana Busic 4

* 18/11/25 Ana Busic 5

* 25/11/25 Exam (à confirmer)

Une familiarité avec les probabilités discrètes et les chaînes de Markov est préférable, sans être obligatoire. (En particulier, le cours commencera par des éléments sur les processus de Markov à temps continu. Ce qui permettra au passage de voir ou de revoir les notions de base sur les chaines de Markov à temps discret.)

Graphes aléatoires

• J. Klainberg. The small-world phenomenon: an algorithmic perspective. STOC'00: Proceedings of the thirty-second annual ACM symposium on Theory of computing. 2000.
• U. Feige and E. Ofek. Spectral techniques applied to sparse random graphs. Random Struct. Algorithms, 27(2):251–275, Sept. 2005.
• K. Pearson. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, (2), 1901.
• D.-C. Tomozei and L. Massoulié. Distributed user profiling via spectral methods. Stochastic Systems, (4), 2014.

Files d'attente, modélisation markovienne

• P. Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues. 2nd edition. Springer. 2021.
• F. Kelly. Reversibility and Stochastic Networks, Wiley, 1979.
• M. Harchol-Balter. Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press. 2013.
• A. E. Krzesinski. Order Independent Queues. In: Boucherie, R., van Dijk, N. (eds) Queueing Networks. International Series in Operations Research & Management Science, vol 154. Springer, Boston, MA. 2011.
• A. Busic, V. Gupta, and J. Mairesse. Stability of the bipartite matching model. Adv. Appl. Probab., 45(2):351-378, 2013.
• P. Moyal, A. Busic, J. Mairesse. A product form for the general stochastic matching model. Journal of Applied Probability 58 (2), 449-468, 2021.

Optimisation et contrôle pour les réseaux

• D. P. Bertsekas. Dynamic Programming and Optimal Control, Vol I, 4th Edition, Athena Scientific. 2017.
• D. P. Bertsekas. Dynamic Programming and Optimal Control: Approximate Dynamic Programming , Vol II, 4th Edition, Athena Scientific. 2012.
• M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. 2014.
• R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. Second Edition. MIT Press, Cambridge, MA, 2018. http://incompleteideas.net/book/the-book.html
• R. Srikant and L. Ying. Communication Networks: An Optimization, Control, and Stochastic Networks Perspective. Cambridge University Press, 2014.