Stage LIESSE
|
|
Promenades aléatoires dans les graphes
|
N.B.: Ces
descriptif et programme sont
donnés à
titre indicatif et peuvent évoluer.
Table des
matières
Nouveautés
- 16/05/17 : clôture des inscriptions : 22 inscrits.
- 31/01/17 : création de cette fiche.
Informations
générales
- Thème
: Promenades aléatoires dans les graphes
- 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.
Inscription libre
mais obligatoire, voir ci-dessous.
- Lieu
: Télécom ParisTech, 46, rue Barrault, 75013 Paris (comment
venir?).
- 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
- Inscription
(libre mais obligatoire) : Inscription de préférence en ligne ici ou
par
mél à liesse@telecom-paristech.fr
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 noeuds du graphe les plus importants ? peut-on
identifier des communautés de noeuds plus fortement connectés ? peut-on
suggérer de nouvelles liaisons entre des noeuds ?
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...
Programme
- Matin
- 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
- Après-midi
- 13h30 - 17h00 (avec pause) : Application à l’analyse des graphes et illustration sur des exemples réels
- 17h00 : Clôture
Documents
Support de cours (PDF): en ligne ici.
Notebooks Python (format zippé): en ligne ici.
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.
dernière
modification 30-mai-2017