Visualisation de grands graphes dynamiques

Résumé : Dans ce travail, nous avons proposé une nouvelle approche pour explorer des graphes dynamique. Nous avons d'abord mis au point un algorithme de clustering qui permet d'extraire des clusters évoluant au cours du temps. Nous avons ensuite proposé deux visualisations. La première montre comment les clusters évoluent dans le temps et peut être utilisée comme une interface permettant de trouver et sélectionner les zones intéressantes. Le seconde représente un diagramme noeud-lien correspondant à un temps. Le clustering est utilisé pour calculer la projection des sommets dans le plan. Ceci permet d'assurer la stabilité de la visualisation et ainsi de préserver la carte mentale de l'utilisateur en minimisant le déplacement des sommets. Grâce au pré-calcul des clusters, la seconde vue peut être mise à jour en temps linéaire, ce qui donne une carte interactive pour plusieurs dizaines  de milliers de sommets.

timeline
20021027
20080810

Nous avons aussi développé un méthode égo-centrée permettant d'explorer de large graphes dynamiques en utilisant une représentation de type storyline. Celle-ci permet de résumer des structures locales dans le temps du graphe.

storylines

A. Sallaberry, C. Muelder, K.-L. Ma. Clustering, visualizing, and navigating for large dynamic graphs. Proceedings of the 20th International Symposium on Graph Drawing (GD 2012), W. Didimo and M. Patrignani (Eds.), LNCS 7704, pp. 487-498, Springer-Verlag Berlin Heidelberg, 2013.
C. Muelder, T. Crnovrsanin, A. Sallaberry, K.-L. Ma. Egocentric Storylines for Visual Analysis of Large Dynamic Graphs. Proceedings of the 1st IEEE Workshop on Big Data Visualization (BigDataVis 2013), 2013.

Dernière mise à jour le 20/01/2015