Prepas.org

Le site de l'UPS pour les Classes Préparatoires aux Grandes Écoles

Télécom ParisTech Promenades aléatoires dans les graphes le Mardi 23 mai 2017

Synopsis

Les graphes sont les objets mathématiques de référence pour décrire la manière dont notre monde est connecté, qu’il s’agisse du monde réel (réseau routier, réseau des liaisons aériennes, Internet) ou virtuel (réseaux sociaux, Web, Wikipedia). Pour mieux comprendre ce monde qui nous entoure, il est important de disposer d’outils d’analyse automatique de ces graphes : quels sont les nœuds du graphe les plus importants ? peut-on identifier des communautés de nœuds plus fortement connectés ? peut-on suggérer de nouvelles liaisons entre des nœuds ?

Il s’avère que des algorithmes basés sur des promenades aléatoires dans les graphes permettent de répondre simplement à ces questions. L’exemple phare est l’algorithme PageRank de Google, permettant de mesurer la popularité des pages Web à partir de la fréquence de visite de ces pages par un internaute imaginaire, naviguant au hasard sur le Web, mais il en existe bien d’autres.

Nous partirons des fondements théoriques des marches aléatoires sur les graphes pour mieux comprendre le fonctionnement de ces algorithmes. Des détours (aléatoires) vers les domaines (connexes) de l’informatique et de la physique ne sont pas à exclure...

Inscription


Inscription, libre mais obligatoire, de préférence en ligne ICI
ou par mél à liesse@telecom-paristech.fr

Informations générales

Dates de la session : Mardi 23 mai 2017
Type de stage : Cours
Auditoire attendu : les professeurs de mathématiques supérieures et spéciales, en mathématiques, physique, chimie, informatique et sciences de l'ingénieur.
Pré-requis : le programme de probabilités de CPGE.
Lieu : Télécom ParisTech, 46, rue Barrault, 75013 Paris
Volume horaire et programmation : voir ci-dessous
Responsable pédagogique : Thomas Bonald
Contact : liesse@telecom-paristech.fr
Intervenants : Thomas Bonald, enseignant-chercheur au département InfRes de Télécom ParisTech.
Page Web de présentation : maintenue par Télécom ParisTech
Seuil d'ouverture / Numerus clausus : 10 / 40

Programme

9h30 - 9h45 : Accueil (Hall Barrault)
9h45 - 10h00 : Présentation du stage
10h00 - 12h30 (avec pause) : Fondements théoriques des marches aléatoires sur les graphes : chaînes de Markov, réversibilité, propriétés spectrales
12h30 Déjeuner
13h30 - 17h00 (avec pause) : Application à l’analyse des graphes et illustration sur des exemples réels
17h00 : Clôture

Documents

Support de présentation de la formation (à venir).

Bibliographie

Pierre Brémaud. Markov Chains, Gibbs fields, Monte Carlo simulation, and queues, Springer 1999
Remco van der Hofstad, Random graphs and complex networks, 2014. En ligne ICI
Albert-Laszlo Barabasi, Network science, 2016.