Les graphes
permettent de 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, etc.) ou du monde numérique (réseaux
sociaux, Web, Wikipedia, bases de données, e-commerce, etc.). De nombreuses questions émergent en pratique, comme par exemple
: quels sont les noeuds du graphe les plus importants ? peut-on
identifier des groupes de noeuds plus fortement connectés entre eux ?
peut-on prédire l’apparition de futurs liens entre les noeuds ?
L’analyse spectrale des graphes fournit des réponses précises à ces
questions. Chaque noeud est représenté par un vecteur obtenu à partir
des premiers vecteurs propres du Laplacien. La géométrie du nuage de
points ainsi formé s’interprète à la fois en termes de marches
aélatoires dans le graphe et de divers modèles de la physique
(thermodynamique, mécanique, électricité) permettant de guider
l’intuition et d’extraire les informations pertinentes sur le graphe.
Le stage comportera deux parties :
- un cours sur l’analyse spectrale des graphes (notion de Laplacien, interprétation physique, marches aléatoires) ;
- 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.