Dieses Dokuwiki verwendet ein von Anymorphic Webdesign erstelltes Thema.

Projet de Master (stage M2)

Février - Juillet 2017

  • Responsable: Guy Melançon
  • Equipe: Méthodes et Algorithmes pour la Bio-Informatique et la Visualisation
  • Mail: Guy.Melancon@u-bordeaux.fr

Approches (semi) automatisées pour la visualisation de réseaux multi-couches

En deux mots

  • On souhaite élaborer une méthode rigoureuse qui permettrait,
    • lors du chargement d'un réseaux multi-couches (des couches de liens et/ou de de types différents)
    • de configurer une interface pour le visualiser et le manipuler,
    • c'est-à-dire de proposer
      • des vues,
      • des variables pouvant être associés aux couleurs et attributs des sommets et des liens, que l'on pourrait activer en un clic,
      • des procédures de calcul “standard” que l'on pourrait solliciter en un clic.

Plus en détail

Contexte

La visualisation de données, et plus particulièrement des réseaux (des graphes), reste une tâche ardue, nécessitant souvent de nombreuses manipulations. L'objectif de ce projet est de se rapprocher de solutions “automatiques” comme ce que l'on trouve dans des logiciels d'analyse de données (données multi-dimensionnelles par opposition à des données relationnelles).

Le logiciel Tableau Software est un bon exemple à avoir en tête. De nombreuses fonctionnalités de ce logiciel suivent de travaux en visualisation d'information, sur la taxonomie de tâches et de techniques (caractérisation et catégorisation des tâches, ou des techniques de visualisation).

  • Mackinlay, J., P. Hanrahan, et al. (2007). “Show Me: Automatic Presentation for Visual Analysis.” Visualization and Computer Graphics, IEEE Transactions on 13(6): 1137-1144.
  • Card, S. K. and J. D. Mackinlay (1997). The Structure of the Information Visualization Design Space. IEEE Symposium on Information Visualization, IEEE Computer Society Press, 92-99.
  • Mackinlay, J. (1986). “Automating the design of graphical presentations of relational information.” Acm Transactions On Graphics (Tog) 5(2): 110-141.

Hormis quelques travaux, le cas de la visualisation des réseaux a reçu moins d'attention – probablement en raison de la complexité plus grande des objets visualisés. Les travaux de Frédéric Gilbert:

prennent comme point de départ des données tabulaires depuis lesquelles on tente d'inférer une (ou plusieurs) structure(s) de graphe(s) à visualiser et étudier. C'est un problème difficile, beaucoup plus difficile que la prise en main de données multi-dimensionnelles, puisqu'il faut “deviner” quelles sont les attributs depuis lesquels on peut inférer les liens d'un réseau.

Objectifs

Le point de départ de ce projet est différent, et d'une certaine manière plus “facile”. On suppose donné au départ un graphe équipé de propriétés. Ces propriétés sont des fonctions définies sur les sommets et/ou les arêtes du graphe $\pi: V \to \mathbb R$ (par exemple, mais les propriétés peuvent prendre leurs valeurs dans n'importe quel ensemble fini ou infini).

Nombre de manipulations effectuées sur un réseau lors de sa visualisation interactive consiste à en

  • filtrer certains éléments (pour n'en garder que certains)
  • dériver un sous-graphe (un graphe induit à partir d'une sélection, par exemple)
  • induire un autre graphe par projection (à partir d'un graphe biparti, par exemple)

(La littérature scientifique – dans le domaine de la visualisation – propose des approches rigoureuses de classification des tâches conduites sur une représentation graphique. Nous mentionnerons ici le travail de (Amar et al. 2005)

  • Amar, R. ; Eagan, J. ; and Stasko, J. . 2005. Low-level components of analytic activity in information visualization. IEEE Symposium on Information Visualization, 2005. , pp. 111–117.

La partie “facile” du projet consiste donc imaginer comment les propriétés du réseau, qui sont connues au départ, peuvent être utilisées pour spécifier les couches et les vues qu'on peut en donner:

  • des vues du graphe lui-même (on pense aux diagrammes noeuds-liens habituels)
  • des vues sur ses paramètres (on reprend ici ce que sait faire Tableau Software)

qu'on étend à toutes les synchronisation entre ces vues:

  • Des vues sur différentes couches du réseau qui pourront (ou non) partager certains éléments
  • Des vues sur le réseau et d'autres sur ses paramètres
  • Etc.

La partie moins “facile” consiste à imaginer une “algèbre” d'opérateurs sur le graphe pour en dériver d'autres graphes, et donc par suite d'autres vues.

  • La projection d'un graphe biparti en ses deux facettes est une cas assez classique.

Si par exemple un graphe associe des auteurs à des publications,

  • on pourra en déduire un graphe auteur-auteur liant deux auteurs d'une même publication. De même on peut projet ce graphe biparti sur un graphe liant des publications ayant un auteur en commun,
  • cette projection peut aussi emporter avec elle un calcul de cardinalité (sur ses arêtes, comptabilisant le nombre de publications commues qu'ont deux auteurs, par exemple)

Mais on peut imaginer d'autres mécanisme de dérivation plus sophistiqués. dans un graphe rendant compte des conversations sur un forum de discussions (stackoverflow, par exemple). Ce graphe n'est pas un graphe biparti. On pourra en dériver un graphe personne-personne, et lier deux personnes A et B si le commentaire de A fait réponse à un commentaire publier par B.

C'est ce type d'opérations assez communes qu'il s'agit de formaliser et de décrire à l'aide d'une “algèbre” (sans être trop strict sur l'interprétation de ce terme). A première vue, on peut penser que ces opérateurs correspondent à chaque fois à des réécritures de certains motifs dans le graphe.

C'est cet espace d'opérateurs, conjugué à l'espace des vues, qu'il sera intéressant d'explorer. On tentera d'en systématiser la mise à disposition à l'utilisateur par le biais d'une interface graphique. En deux mots, dès le chargement du graphe,

  • on doit pouvoir établir les vues que l'on peut en proposer – vraisemblablement à partir de la liste des propriétés;
  • puis des opérateurs qu'il sera possible d'y appliquer et de combiner afin d'en dériver d'autres graphes.
Travail attendu

Ce projet exigera un peu de lecture, pour se pencher sur le travail d'automatisation qui est fait dans Tableau Software, par exemple. On pourra aussi regarder les articles proposant des taxonomies de tâches.

Outre l'effort d'abstraction pour tenter d'arriver à la systématisation, il sera intéressant de tester certaines idées en développant des prototypes démontrant leur faisabilité et leur potentiel.

masters_project.txt · Last modified: 2017/01/14 12:23 by melancon
Trace: masters_project
Dieses Dokuwiki verwendet ein von Anymorphic Webdesign erstelltes Thema.
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0