JdS2012


 English   -  Français  

Résumé de communication



Résumé 162 :

Modélisations et extensions du formalisme de l’analyse Relationnelle Mathématique aux grands Graphes (Application au clustering de graphes)
Conde Céspedes, Patricia ; Marcotorchino, Jean François
LSTA-UPMC

Il existe aujourd'hui un renouveau incontesté de l'analyse de graphes essentiellement dû à l'engouement pour les "Réseaux Sociaux" (FaceBook, Twitter, Linkedln, etc.). Un graphe peut aussi décrire des réseaux complexes issus de divers domaines tels la biologie, l’informatique, etc. En effet, un graphe permet de modéliser tout système consistant en un ensemble d'objets similaires susceptibles d'être liés par une certaine "relation typée". Ceci pré?gure leur étude au moyen de l’Analyse Relationnelle. L'une des difficultés de l'étude de ces réseaux réside dans leur grande taille qui rend difficile, voire impossible, leur analyse directe. Il devient, alors indispensable de pouvoir les «partitionner» en sous-ensembles gérables et faciles à comprendre. Ce partitionnement incontournable appelé «modularisation» («recherche de communautés» dans le cas des réseaux sociaux), n’est autre que le «clustering» de graphes. «Modulariser» un Graphe consiste donc à le décomposer en classes homogènes ayant peu de relations entre elles. L'obtention de ce résultat nécessite un "bon" critère, qualifiant le processus de partitionnement. C'est le choix de ces critères potentiels qu'il importe de justifier et c'est l'ensemble des problématiques associées à leurs propriétés que nous aborderons dans cette présentation. Ce problème fort complexe peut néanmoins être modélisé mathématiquement par une unification Relationnelle, puissante, visant à comparer sur les mêmes bases un certain nombre de critères de modularisation (comme le critère de Girvan-Newman , de Mancoridis-Gansner , de Zahn-Condorcet , etc…), en en facilitant la compréhension, en interprétant plus clairement leurs finalités et en y associant la preuve de leur utilité dans certains contextes pratiques.