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 Mercredi 18 avril 2018

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 physique (réseau routier, réseau des liaisons aériennes, réseau électrique) ou numérique (réseaux sociaux, Web, Wikipedia, bases de données). 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 prédire de futures connexions entre les noeuds ?

Nous verrons que ces informations s'obtiennent à partir d'une simple marche aléatoire dans le graphe, le temps moyen d'atteinte d'un noeud étant une bonne mesure de son importance absolue ou relative à un autre noeud.

Le stage comportera deux parties :
un cours sur les fondements théoriques des marches aléatoires (chaînes de Markov, réversibilité, analyse spectrale) et leur application aux graphes (notion de Laplacien, interprétation physique) ;
une séance de travaux pratiques (programmation python) permettant de se familiariser avec ces outils et de les tester sur des données réelles.

INSCRIPTION

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

Informations générales

Thème : Promenades aléatoires dans les graphes
Dates de la session : Mercredi 18 avril 2018
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 mathématiques de CPGE et les bases de la programmation Python.
Lieu : Télécom ParisTech, 46, rue Barrault, 75013 Paris
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 ICI
Seuil d'ouverture / Numerus clausus : 10 / 40

Programme

Matin
9h15 - 9h30 : Accueil (Hall Barrault)
9h30 - 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) : Travaux pratiques (en python)
17h00 : Clôture