Titre : Mesures et algorithmes de fragmentation
multi-échelle de grands ensembles de données
Directeurs de thèse : Maylis Delest (LaBRI) et
Jean-Marc Fédou (I3S)
Contact : maylis.delest@labri.fr
Thème - Equipe : Visualisation - MABioVis
Résumé :
Lorsqu'on est confronté à des masses de données structurables en graphes, de
nombreux algorithmes existent permettant de fragmenter en accord avec certains
paramètres. Il est fréquent d'exécuter ces algorithmes récursivement sur les
fragments obtenus. On pourra par exemple regarder un algorithme de
fragmentation pour des graphes petits mondes [1]. De nombreuses mesures de
qualité ont été proposées pour une étape de fragmentation mais aucune étude ne
concerne la mesure de qualité globale de l'arbre de fragmentation. Nous
proposons d'étudier dans cette thèse des généralisations de mesures de
fragmentation de graphes pour des fragmentations multi-niveaux.
Détail du sujet
L'approche envisagée est de définir et d'étudier des q-analogues de paramètres
ou de mesures de qualité connus et d'étudier la pertinence de leur utilisation
dans les problèmes de fragmentation de graphes. Les q-analogues [5] ont pour
particularité de spécialiser des séries. On en trouve de belles applications en
combinatoire énumérative où ils apparaissent naturellement comme fonctions
génératrices de chemins dans les arbres ou dans des mesures fractales. Une
fragmentation récursive de graphe conduisant à un arbre de fragments, il est
raisonnable de se tourner vers ce type d'outils.
Une première généralisation a été introduite dans [2] pour le paramètre MQ de Mancoridis [3] afin d'examiner la faisabilité de l'idée.
Des premières mesures sur des cas concrets montrent que sans être parfaite
l'approche permet effectivement de donner une mesure dont la valeur dépend du
poids que l'on souhaite donner aux fragments figurant en tant que feuilles de
l'arbre.
La particularité de la mesure de Mancoridis et de
reposer sur la densité d'arêtes entre fragments et à l'intérieur d'un fragment.
Bien d'autres mesures peuvent être envisagées notamment en se basant sur des
mesure de qualité connues par exemple celle du Q de Newman [4].
Cependant étant donné que beaucoup d'algorithmes sont conçus pour fragmenter en
accord avec des paramètres mesurables sur le graphe, la mesure de qualité est
dépendante de ces paramètres. Il sera donc intéressant de voir à quelle classe
d'algorithmes ce type de généralisation est applicable.
Un premier travail de cette thèse est donc :
- explorer les qualités et défauts de la première généralisation de MQ,
- explorer d'autres q-analogues possibles de MQ,
- explorer d'autres mesures par exemple celle de newman.
Enfin, une perspective importante est de voir dans quelle mesure on peut ainsi
réaliser des algorithmes de fragmentation multi-niveaux efficaces automatiques
ou guidés par l'utilisateur.
Références