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

  1. D. Auber, Y. Chiricota, F. Jourdan, and G. Melancon. Multiscale navigation of small world networks. In IEEE Symposium on Information Visualisation, pages 75-81, Seattle, GA, USA, 2003. IEEE Computer Science Press.
  2. M. Delest, J.M. Fédou, G. Mélancon, A Quality Measure for Multi-Level Community Structure, SYNASC 8th Internatinal Conference, Timisoara, Romania, September 2006.
  3. S. Mancoridis, B. S. Mitchell, C. Rorres, Y. Chen, and E. Gansner. Using automatic clustering to produce high-level system organizations of source code. In IEEE International Workshop on Program Understanding (IWPC'98), Ischia, Italy, 1998
  4. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physics Reviews E, 69(026113), 2004.
  5. Wikipedia, http://en.wikipedia.org/wiki/Q-analog