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.