Classification spectrale de graphes

Abstract

La classification spectrale de graphes (graph spectral clustering) est une méthode éprouvée de détection de sous-ensembles cohésifs dans un graphe. Cette communication se propose d'en illustrer différentes variantes en s'appuyant sur la base de flux domicile-travail de l'Insee. Les valeurs propres d'un graphe encodent en effet de nombreuses propriétés du graphe dont elles sont issues et leur analyse permet ce faisant d'en dégager les structures. La factorisation du laplacien d'un graphe permet ainsi partitionner les sommets en maximisant le nombre de lien intra-grappes tout en minimisant le nombre de liens inter-grappes et donne de bon résultats sur des graphes réels. Elle peut être appliquée à des graphes dont les arêtes sont valuées et ne se limite pas aux matrices symétriques. D'un point de vue opérationnel, la méthode présente aussi l'avantage de pouvoir être mise en œuvre avec des outils courants d'algèbre linéaires. Elle peut donc être appliquée à des graphes de taille conséquente, particulièrement en utilisant des librairies pour matrices éparses et parallélisées. La pertinence de l'application de la méthode à ce type de graphe ne se limite toutefois pas à la seule question de leur taille. En effet, en grandissant, les graphes présentent des propriétés spécifiques comme des structures locales qui peuvent aussi être appréhendées au moyen de l'analyse spectrale. À partir de l'exemple des flux inter-communaux, différentes versions du laplacien seront présentées, notamment sa variante régularisée visant à corriger l'effet de l'asymétrie de la distribution des degrés des sommets courante dans les graphes complexes. Différentes propriétés de l'analyse spectrale seront présentées comme ses liens avec les Block Models stochastiques ou l’analyse factorielle des correspondances. La présentation constituera aussi l'occasion d'évoquer les avantages comparatifs de l'algèbre linéaire pour stocker, manipuler et analyser des graphes par rapport à d’autres approches.