User Tools

Site Tools


bandres_buiquang:thomas_bandres_jean_bui-quang

Visual Analytics Course

Drawing dynamic networks I

Thomas Bandres & Jean Bui-Quang


Introduction :


Ce projet s'appuie sur l'étude de l'article « Online Dynamic Graph Drawing », par Yaniv Frishman et Ayellet Tal. Leur travail s'inscrit dans la problématique de construction de représentations dynamiques de graphes. L'algorithme présenté permet de construire une représentation plaisante, stable, tout en permettant à l'utilisateur de suivre l'évolution de son graphe en préservant sa « carte mentale » de celui-ci.

Notre but était de reproduire l'algorithme développé par cette équipe. Cet algorithme est dit « online » ou d'apprentissage incrémental en francais, il apprend à partir de données reçues au fur et à mesure du temps, ce qui est plus compliqué que lorsque l'entièreté des données à afficher est connue à l'avance.

L'algorithme :


Il s'agit d'un algorithme de dessin basé sur les forces qui permet de positionner les nœuds d'un graphe afin d'en faciliter sa visualisation. Chaque image du graphe doit respecter un ensemble de règles telles que la minimisation du croisement des arrêtes, la superposition des nœuds, et la symétrie.
Il a pour spécificités, en outre d'être online et dynamique, de passer la majorité de son temps d'exécution sur les parties du graphes à modifier. La stabilité de la représentation produite permet à l'utilisateur de devenir graduellement familier avec la structure du graphe.

Dans l'article, l'algorithme est aussi optimisé en utilisant le GPU, à l'aide de programmation parallèle. Notre algorithme n'implémente pas cette option.

Les données :


L'article présente deux exemples d'applications possibles pour cette algorithme :
- La visualisation de l'évolution à travers le temps d'un fil de discussion sur internet
- La visualisation de la croissance d'un réseau social
Nous avons choisis de reproduire le premier cas.

Pour cela, obtenir des données était nécessaire. Le site communautaire http://www.reddit.com/, sur lequel de nombreuses personnes postent des commentaires sur des sujets divers nous a fournit ces données. Les commentaires sur reddit peuvent être à plusieurs « niveaux », un utilisateur pouvant répondre spécifiquement à un autre.

Pour un sujet donné, les commentaires sont récuperables sous le format JSON (JavaScript Object Notation) qui est un format de données textuelles permettant de représenter de l'information structurée.

Voici un exemple de JSON :





Pour cela nous avons développer un script capable de lire les fichiers JSON de reddit. Ce scripts parcourt le fichier, analyse ses données et créer un graphe initial. Il est constitué d'une fonction récursive permettant, pour chaque commentaire, de trouver ses commentaires « fils » s'ils existent.
Un second script permet, à partir d'un json récuperer plus tard sur le même sujet, d'étendre le graphe initial en rajoutant uniquement les nouveaux commentaires.

Le graphe initial est ensuite soumis à plusieurs algorithmes de layout afin de produire un layout initial correct pour tester notre algorithme. Tout d'abord, un random layout va permettre de positionner aléatoirement les points, puis plusieurs itérations des algorithmes Kamada Kawai et Frutcherman Reingold vont permettrent de créer un layout initial correct.

Voici un exemple de résultat pour notre graphe initial :





Fonctionnement de l'algorithme :


L'algorithme présenté permet, à partir d'un graphe contenant de nouveaux points et de la dernière disposition du graphe - le layout - , de produire un nouveau layout. Pour simplifier, on peut dire que le layout est un graphe qui peut être visualisé grâce aux positions des points qu'il stocke.
Il faut donc d'abord rajouter au graphe existant les nouveaux nœuds à partir d'un nouveau jeu de données.

1) Merging

Tout d'abord il faut fusionner le layout précédent au nouveau graphe pour créer un layout initial. Les nouveaux nœuds non-positionnés sont ensuite positionnés en fonction de leur nœuds voisins qui ont déjà été positionnés. Un nouveau noeud est placé de la manière suivante :
- S'il possède plusieurs voisins alors on va le placer à la position du barycentre de ses voisins.
- S'il ne possède qu'un voisin alors on va le placer le long d'une droite imaginaire passant par le centre de la bounding box du layout (rectangle minimal englobant tout les points du layout) et son voisin. Etant donné que l'article ne précise pas à quelle endroit sur cette ligne, nous avons du choisir une distance qui sépare le voisin au nouveau point.
- Si aucun nœud voisin n'est positionné alors on place le point dans un cercle autour du centre de la bounding box.
Ce premier positionnement est approximatif mais assez représentatif et sera mis à jour plus loin a l'aide de forces.

Ce positionnement reçoit ensuite une note (entre 0 et 1) selon la méthode par laquelle il a été positionné.

2) Pinning

Cette étape permet de modifier le layout uniquement dans les zones du graphe dont les points ont étés déplacé, ou ajoutés.
Chaque nœud va se voir attribuer un poids particulier entre 0 et 1, un “pinning weight”, en fonction de sa distance à un nouveau nœud. Plus les nœuds seront proches d'une modification (pinning weight = 0) plus ils bougeront, à l'inverse les nœuds les plus éloignés (pinning weight = 1) ne bougeront pas.
Une première étape consiste à regarder le score de position du nœud et de ses voisins pour attribuer un premier pinning weight.
Ensuite on va parcourir le graphe et remplir des classes de distances par rapport au zone de modification : D0 correspond aux nœuds ajoutés, a ceux qui sont adjacents, et aux nœud ayant un pinning weight inférieur à 1. Ensuite on propage les classes : D1 seront les nœuds adjacents aux nœuds D0 etc. On recalcule ensuite le pinning weight avec une autre formule décrite dans l'article.

3) Coarsening

Le but de cette étape est de créer une version réduite “grossière” de notre graphe, qui correspond au squelette de la forme finale et qui servira ensuite de base aux étapes suivantes. Il est construit par des séries de remplacement de deux nœuds et de l'arrête qui les relies par un seul nœud, au centre deux deux.

L'odre dans lequel les nœuds sont choisis va dépendre de leur degré, ainsi que de leurs poids. (différent du pinning weight). Il s'agit là d'un autre problème rencontré en essayant de reproduire l'algorithme présenté dans l'article : notre graphe n'était nullement pondéré. Un graphe qui représente des fils de discussion n'a aucun poids.
N'ayant pas trouvé de réponse à ce problème, nous avons décidé de nous en tenir aux choix des points par leur dégré croissant.

Voici un exemple de layout apres coarsening :




4) Geometric partitioning

Le graphe « grossier » produit va ensuite être découpé en partitions, qui permettront d'accélerer l'étape de calcul du layout. Cette étape permet de créer des partitions au seins du graphe qui seront géometriquement localisées, avec un nombre de nœuds équivalents et relativement proches les uns des autres.

Pour créer ce partitionnement, les nœuds sont triés par leur abscisse pour former deux ensembles. Ensuite de manière récursive, chacun de ses ensemble est trié par l'ordonnée, pour donner deux sous-ensembles qui seront à leurs tours triés de manière alterné entre l'abscisse et l'ordonnée, jusqu'à ce que la taille des sous-ensembles soit en dessous de la taille de partition requise.
Là encore, cette taille de partition requise reste un mystère, nous avons du choisir aléatoirement une variable qui pouvait s'accorder avec notre graphe.

Voici un exemple de layout apres coarsening :




5) Layout

Cette étape permet de calculer les forces qui seront appliquées aux nœuds en utilisant les nœuds du graphe réduit précédemment calculé.
Le partitionnement n'est pas nécessaire à chaque incrémentation, mais plutôt lorsqu'il y a de grands changements.

L'algorithme calcul les centres de gravités des partitions, les forces appliquées à chaque noeuds. La méthode usuelle est de calculer les forces appliquées sur toutes les paires de nœuds du graphes : les forces de répulsion et d'attraction. Par manque de temps nous n'avons pas implémenté la méthode utilisant le parallélisme sur GPU.

Ici on se sert du partitionnement pour calculer uniquement les forces appliquées entre les paires de nœuds d'une même partition, alors qu'un calcul approximatif sera fait pour des nœuds de différentes partitions. Cela permet d'accélérer la vitesse d'execution, tout en gardant une précision presque identique. C'est la force entre le nœud et le centre de gravité de la partition qui est alors calculée.

L'algorithme calcule ensuite la nouvelle position des points du squelette grâce aux vecteurs de forces calculés.

6) Interpolation

Dans cette étape l'algorithme calcule le déplacement nécessaire à tous les nœuds pour prendre leur place finale en fonction du déplacement des nœuds du squelette du graphe réduit.
Chaque nœud du graphe initial va se déplacer en fonction de la force calculée pour le noeud du graphe “grossier” dont il avait été remplacé.

7) Morphing

La dernière étape consiste à transformer l'ancien graphe vers le nouveau, et ceci de manière harmonieuse, lisse. Pour cela, les positions des points sont interpolés linéarement.


Conclusion :


Bien qu'il fut interessant de se mesurer à un algorithme complexe, le cruel manque de certaines données ont rendu le travail très laborieux.
Notre algorithme final n'est pas encore au point, certaines étapes fonctionnent bien tandis que d'autres ne rendent pas un résultat comme nous pouvions l'espérer. Il est très difficile de savoir, dans un algorithme aussi vaste, quelle partie, quelle paramètre est défaillant.
Etant donné qu'il nous a fallu aller jusqu'à deviner certains paramètres, il était fort peu possible que le résultat soit identique à de celui des auteurs.
Néanmoins, cela nous a permis d'apprendre à essayer d'innover, de combler le manque de données pour atteindre un résultat malgré tout.

Les scripts sont disponibles ici : frishman.zip

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/bandres_buiquang/thomas_bandres_jean_bui-quang.txt · Last modified: 2014/01/17 09:49 by tbandres