Représentation de graphes par ACP granulaire
Abstract
L'extraction d'information de grands graphes repose le plus souvent sur leur représentation dans des espaces de dimension réduite et on utilise généralement des méthodes factorielles appliquées à des mesures de dissimilarités calculées à partir des matrices associée du graphe ou l'analyse spectrale de leur Laplacien discret. Efficaces pour dégager les structures globales, ces représentations sont parfois peu exploitables dès lors que l'on s'intéresse à une perspective du graphe à partir de certains sommets privilégiés. Or l'information recherchée a souvent un caractère "local". Pour représenter le graphe du point de vue d'un ou plusieurs sommets sélectionnés, nous proposons une méthode d'Analyse en Composantes Principales "Granulaire" consistant à appliquer une A.C.P. "filtrée" à un tableau de proximités. La visualisation d'un graphe de dictionnaire dont la mesure de proximité est obtenue à partir d'un algorithme original illustre notre propos.