v1.16.1

PA - C3 - MAP564 : Réseaux sociaux et de communication : modèles et algorithmes proba

Domaine > Mathématiques appliquées.

Descriptif

Ce cours a pour but de fournir des outils pour mieux appréhender les réseaux au sens large, allant des réseaux de communications qui sous-tendent l'Internet aux réseaux sociaux (en ligne ou non).

Il s'agit de proposer :

  • des modèles des systèmes et des phénomènes d'intérêt,
  • des méthodes algorithmiques pour leur contrôle (idéalement décentralisé),
  • des outils mathématiques pour l’analyse du comportement et de la performance de ces systèmes.

Le plan sera le suivant :

  1. Contrôle distribué d’accès aléatoire à un canal : protocoles randomisés de type Aloha et leur stabilité. Outils : Chaînes de Markov à temps discret, leur ergodicité, et le critère d’ergodicité de Foster-Lyapunov.
  2. Politiques d’ordonnancement stabilisantes pour les routeurs et les réseaux sans fils. Notion de région de stabilité. Modèle de switch généralisé, et stabilité optimale de la politique de poids maximal.  Politique de « back-pressure » pour les réseaux multi-bonds.
  3. Allocation de ressources en réseaux : critères d’équité pour le contrôle de congestion. Algorithmes de gradient comme méthode de contrôle distribué. Interprétation du protocole TCP comme un tel algorithme. Outils : systèmes dynamiques, stabilité par méthode de Lyapunov, dualité Lagrangienne.
  4. Phénomènes épidémiques : modèle SI de propagation. Processus de branchement de Galton-Watson et transition de phase associée. Epidémie SIR, lien avec les graphes aléatoires d’Erdös-Rényi, et émergence du composant géant. Outils : inégalité de Chernoff.
  5. Détection de communautés. Modèle de graphe « stochastique par blocs ». Méthodes spectrales pour la reconstruction des communautés. Outils : contrôle de perturbation de spectre de matrices hermitiennes, contrôle de rayon spectral de matrices aléatoires.
  6. Topologies de réseaux particulières : modèle de Barabasi-Albert d’attachement préférentiel et graphes en loi de puissance. Réseaux dits « navigables » et phénomène de petit monde. Outils : inégalité d’Azuma-Hoeffding.
  7. Modélisation de systèmes de files d’attente à temps continu. Outils : processus de Poisson et ses propriétés fondamentales. Processus Markoviens de sauts (ergodicité et réversibilité). Le modèle d’Erlang de réseau à pertes.
  8. Description et analyse de quelques réseaux de files d'attente: réseaux de Jackson, transferts dans Internet, réseaux à priorités.
  9. Modèles épidémiques SI et SIS.


Référence bibliographique :

"Réseaux : contrôle distribué et phénomènes émergents", Laurent Massoulié, 2016

Cours dispensé en anglais

Langue du cours : Anglais

Credits ECTS : 4

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique

Veuillez patienter