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.