Représentation de graphes par ACP granulaire

Bruno Gaume (1, 2) , Louis Ferré (3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 CLLE-ERSS - Cognition, Langues, Langage, Ergonomie
3 IMT - Institut de Mathématiques de Toulouse UMR5219

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 de 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.

Mots clés: complex network; graph visualisation

Domaines: Statistiques [math.ST]; Intelligence artificielle [cs.AI]; Informatique et langage [cs.CL]; Vision par ordinateur et reconnaissance de formes [cs.CV]; Linguistique

Bruno Gaume, Louis Ferré. Représentation de graphes par ACP granulaire. journées d'Extraction et de Gestion des Connaissances (EGC), Jan 2004, Clermont Ferrand, France. ⟨hal-01321959⟩