User Tools

Site Tools


blanchaud_brout:marc_de_blanchaud_marie_brout

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Marc de Blanchaud & Marie Brout's corner

Project d'étude de l'article : A bayesian paradigm for dynamic graph layout

Introduction


La représentation de graphes est un problème important qui combine la géométrie algorithmique et la théorie des graphes. Les applications peuvent être trouvées dans une variété de domaines, y compris des configurations de circuits, gestion de réseau, génie logiciel, et des graphiques. La motivation pour l'étude des algorithmes de représentation de graphe dynamique se pose lorsque de très grands graphes doivent être visualisés dans un environnement dynamique, où les sommets et les arêtes sont insérés et supprimés, et des sous-graphes doivent être affichés.

Notre travail consistait à effectuer un état de l'art à partir de ce document : il fallait donner La liste des articles à lire avec une description de l'article expliquant son importance dans la compréhension de l'article principal (par son contenu, son nombre de citations, les algorithmes implémentés, etc.).

Article [BW97] - Random field models for graph layout


Dans cet article, le random field model est abordé de manière plus précise et détaillé que dans l’article référent. Les random fields sont des vecteurs aléatoires pour lesquels une relation de voisinage est définie sur leurs ensembles d'indices. Toutes les dépendances entre les variables aléatoires de leurs composants sont locales a l’égard du voisinage.

Les random fields sont utilisés comme framework pour des layouts de graphe représenté en ligne droite (tous les edges sont représentés par un segment de ligne droite) mais sont adaptables pour d’autres types de représentations.L’article parle également des modèles de random fields de Gibbs (GRFM) et donne la formule de son potentiel réutilisée dans l’article référent.

Cet article parle également du Spring Embedder et de ses variants, qui sont les layouts utilisés dans l’article référent. Pour chacun des deux modèles, l’article décrit le modèle, fournit la formule de calcul de potentiel d’une clique et la formule de minimisation de l’énergie. Le Spring Embedder normal consiste à simuler un système de cercles représentant les sommets qui sont toujours repoussés ou rejoints par un ressort algorithmique (les arrêtes/edges). De nombreuses autres variantes du spring embedder sont également rapidement décrites.

  • Nombre de références dans l'article : 4
  • Article des mêmes auteurs : Ulrik Brandes et Dorothea Wagner
  • Références pour des travaux connexes pour le Spring Embedder et ses variantes : [Ead84], [KK89], [FR91] ,[DH96], [Tun94], [FLM95], [SM95]

L'article : bw97_.pdf

Article [DH96] - Drawing Graphs Nicely Using Simulated Annealing


Cet article fournit l'implémentation d'un algorithme basé sur la méthode d'optimisation d’annealing qui est compétitive avec d'autres méthodes dont le spring embedder. L’article référent utilise les forces attractives et répulsives détournées à partir de cet algorithme. Des exemples de graphiques tirés par la mise en œuvre de l'algorithme sont fournis.

L’objectif principal du document est de définir des critères généraux applicables à différents types de graphiques afin d’obtenir un graphe de bonne qualité esthétiquement parlant. Ces critères sont les suivants: la distribution des noeuds de façon égale, l’uniformisation des longueurs des edges, la minimisation des bords, le maintien des nœuds pour qu’ils ne s’approchent pas trop près des bords .

Le critère qui nous intéresse est celui de la distribution uniforme des nœuds dans la représentation. L’article fournit une fonction d'énergie qui permet d’empêcher les nœuds de s'approcher trop près les uns des autres et des frontières de l'espace de représentation. Cette fonction d’énergie est ce qui permet de calculer les forces attractives ou répulsives.

  • Nombre de références dans l'article : 2
  • Références pour des travaux connexes qui aborde le problème dans sa généralité, notamment le “spring-méthode” Eades [1984], et Fruchterman Reingold [1991], Kamada [1989] et Kamada et Kawai [1989].

L'article : dh96_.pdf

Article [Lyo92] - Cluster busting in anchored graph drawing


La partie qui nous intéresse plus particulièrement dans ce rapport est le modèle de ressort ancré utilisé pour un graphe statique et l'algorithme de GeoForce.

Ce rapport décrit en détail deux algorithmes basés sur une approche d'ajustement de layout appelée cluster busting dans une représentation de graphe ancré. Les objectifs de cluster busting dans une représentation de graphe ancré sont d’améliorer la distribution des noeuds dans le nouveau layout (le processus de cluster busting) tout en essayant de minimiser les différences entre les deux layouts (le processus de représentation de graphe ancré).

L'algorithme GeoForce utilise les forces et les ressorts pour modéliser des interactions entre des nœuds dans une représentation de graphe. La distance euclidienne entre les noeuds et la longueur du chemin le plus court entre les noeuds du graphe sont utilisés pour calculer la force de répulsion.

Un layout initial est calculé de manière aléatoire et les algorithmes sont itératifs : à chaque itération, les forces sont calculées sur les noeuds et les noeuds sont déplacés vers une nouvelle position selon les forces agissantes. Plusieurs techniques sont utilisées pour décider quand arrêter l'itération, comme le recuit simulé (annealing simulated).

La forme générale de la nouvelle représentation doit être similaire à la forme du dessin original donc les forces d'attraction appliquées entre les noeuds et leurs positions dans le layout doivent être similaires à la représentation originale. Comme les nœuds dans la fenêtre de représentation doivent être mieux répartis, les forces de répulsion sont appliquées entre chaque paire de noeuds, entre chaque noeud et les côtés de la fenêtre de représentation. L'algorithme de base GeoForce a subi plusieurs modifications et l’article détail comment assurer que les nœuds restent dans la fenêtre, quelles forces sont appliquées, etc.

  • Nombre de références dans l'article : 1

L'article : lyo92_.pdf

Article [CDTT95] - Dynamic Graph Drawing : trees, series-parallel digraphs, and planar st-digraphs


Ce document est intéréssant de par son contenu. Il décrit l’implémentation d’un modèle pour des algorithmes de graphes dynamique, basé sur l'exécution de requêtes (par exemple draw, offset, drawsubtree, etc) et les mises à jour de représentation implicite du dessin (par exemple MakeGraph, DeleteGraph, Link, etc). Il montre également comment appliquer ces modèles généraux à différents graphes.

Le document présente un modèle qui permet d'implémenter des algorithmes de représentations de graphes dynamiques. La mise à jour d'une représentation peut demander du temps, car il est possible de modifier les coordonnées de tous les sommets et de toutes les arêtes. L’objectif de ce modèle est donc de maintenir une représentation implicite du dessin d'un graphe pour effectuer certaines opérations efficacement.

Le document montre ensuite comment utiliser ce modèle pour un dessin d’arbres dynamiques, de diagrammes de séries parallèles et de graphes planaires. Pour chacun de ces trois cas, le document explique comment effectuer le dessin, quel est l’environnement dynamique avec ses requêtes et ses opérations de mise à jour, la structure de donnée pour maintenir une représentation implicite d'un dessin, et comment réaliser les opérations de requêtes et de mises à jour.

  • Nombre de références dans l'article : 1

L'article : cdtt-95.ps

Article [PT96] - Issues in Interactive Orthogonal Graph Drawing


L’intêret de cet article est qu’il se base sur une représentation de graphe interactive orthogonale, tout comme dans l’article référent qui donne un exemple graphe dynamique orthogonal. Un schéma orthogonal est un schéma dans lequel des sommets sont représentés par des points de coordonnées et les edges sont représentés par des chaînes polygonales, composées de segments horizontaux et verticaux.

Le problème est que dans tous les algorithmes existants, le graphe est donné en entrée et l’algorithme ne fait que le représenter. Ainsi si une insertion ou une suppression est effectuée sur le graphe, un nouveau graphique est créé. L'algorithme de nouveau exécuté donne lieu à une nouvelle représentation de graphe qui pourrait être très différente de la précédente. C'est un gaspillage de temps et de ressources: le temps pour exécuter l'algorithme sur le nouveau graphe, et l'utilisateur a probablement passé une quantité importante de temps de manière à comprendre et à analyser la précédente représentation de graphe.

L’algorithme interactif de représentation graphique permet de créer une représentation d’un graphe donné sous forme de layout standard (par exemple, orthogonale, droite, etc.) et donne à l'utilisateur la capacité d'interagir avec la représentation (déplacer un sommet, déplacer un bloc de sommets et d'arêtes, insérer une arête entre deux sommets spécifiés, insérer un sommet avec ses arêtes incidentes, supprimer des sommets, des arêtes ou des blocs).

L’article met en avant des techniques qui minimisent les modifications de représentations dont la coordination relative (la forme générale de la représentation courante reste la même mais les coordonnées de sommets et de bords peuvent changer dû à l'insertion d’un nouveau sommet) et la représentation sans changement (le système de représentation ne ​​change jamais). Pour ces deux représentations, l’article fournit des scénarios de modifications de représentations.

  • Nombre de références dans l'article : 1

L'article : pt96_.pdf

Article [GM85] - Bayesian Image Analysis: A Application To Single Photon Emission Tomography


Cet article sert a aborder le principe du Bayesian framework, qui sert de base pour le Bayesian Paradigme.

Dans cet article, les auteurs nous disent que les analyseurs d'image possèdent de nombreux traitements d'images. Mais que chacun de ces traitements possèdent un code individuel. Les auteurs ont donc souhaité, dans cet article réunir tous ces codes en un seul, le Bayesian Framework. Une fois fait, le Bayesian Framework est comparé à un autre algorithme, le maximun likelihood and em pour tester son efficacité sur un exemple, le SPET(single photon emmision tomographic). Le maximun likelihood and em et le SPET sont également expliqué dans l'article.

  • Nombre de références dans l'article : 1

L'article : gm85.pdf

Article [Nor96] - Incremental Layout in DynaDAG


Cet article sert à donner un exemple de graphe dynamique admissible.

Cet article décrit DynaDAG un graphe incrémenté. Il corrige certains défauts des graphes automatiques. Notamment ceux qui apparaissent lorsque l'affichage des graphes est modifié comme dans les 3 cas suivants:

Lors de l'édition manuelle, Lorsqu'on surfe sur les grands graphes, Lorsqu'on visualise des graphiques dynamiques .

DynaDAG corrige aussi le manque de stabilité de la plupart des algorithmes de dessin graphique de l'époque. Un petit changement dans le jeu d'entrée pouvait produire des changements imprévisibles , instables entre dispositions successives. Les résultats pouvaient être source de confusion lors de la visualisation. Ce qui n'est plus le cas avec DynaDAG.

  • Nombre de références dans l'article : 2

L'article : nor96.pdf

Article [BP90] - Using constraits to achieve stability in automatic graph layout algorithms


Cet article sert à donner un exemple de graphe dynamique admissible.

Cet article décrit un modèle applicable aux algorithmes de graphe automatique sont communément utilisés dus au fait qu'ils font de bon dessin. Ces algorithmes possèdent de nombreux avantages. Toutefois, lors de la rédaction de cet article il existait les inconvénients suivants:

Il était impossible de spécifier des contraintes, L'algorithme effaçait les infos de l'ancien graphe pour en construire un nouveau, Le modèle décrit dans l'article s'attache à essayer de supprimer ces défauts.

Pour cela, les auteurs utilisent une approche en multicouche, chaque couche ayant ses propres contraintes. Voici les contraintes des différentes couches :

Les contraintes de bas niveau : position d'un point sur un graphe. 1.Le positionnement absolu : Contraindre la position du point par rapport à un système de coordonnées fixes. 2. Le positionnement relatif: Contraindre la position du point par rapport aux autres points. 3. Les clusters : Réunir un groupe de point dans un même sous-ensemble qui peut par la suite être agrandi. Se fait sur une dimension

Le gestionnaire de contrainte. 1. Contient une liste de contrainte ainsi que des fonctions d'ajout, d'effacement, et de modification des contraintes. 2. Évalue et garde la cohérence des contraintes. Dans le cas d'incohérence, le gestionnaire désactive les contraintes les moins prioritaires.

Les contraintes tri-dimensionnelles: Utilisation d'un module d'interface Pour finir, ils testent leur approche sur un algorithme.

  • Nombre de références dans l'article : 1

L'article : bp90.ps

Article [CDT+92] - A Framework for Dynamic Graph Drawing


L'article sert à donner un exemple de graphe dynamique admissible.

Il décrit l'élaboration d'un modèle pour des algorithmes de graphes dynamiques. Ce modèle se base sur l'exécution de requêtes et de mises à jour d'une représentation implicite du dessin. L'article montre également diverses applications de ce modèle. Plusieurs algorithmes efficaces de dessin dynamique pour les arbres, les digrammes de la série-parallèle, et des graphiques planes sont présenté puis testé en leur appliquant le modèle.

  • Nombre de références dans l'article : 1

L'article : cdt_92.pdf

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/blanchaud_brout/marc_de_blanchaud_marie_brout.txt · Last modified: 2014/01/17 02:07 by dracangel_m