Visualisation de réseaux et d’arbres

Plan

• Correction du TP#3
• Critique
• Réseaux et arbres
• Diagrammes noeuds - liens
• Matrices d'adjacence
• Partitions
• TP #4

2

Plan

• Correction du TP#3
• Critique
• Réseaux et arbres
• Diagrammes noeuds - liens
• Matrices d’adjacence
• Partitions
• TP #4

3

Critique

• À qui s’adresse la visualisation ?�-> 1 proposition
• À quelle question la visualisation permet elle de répondre ? �-> 1 proposition
• Pourquoi (n’)aimez vous (pas) cette visualisation ?�-> 2 raisons
• Quelles améliorations apporter ? -> 3 propositions

https://web.archive.org/web/20060901105122/http://jacobsschool.ucsd.edu/news_events/releases/release.sfe?id=299

Plan

• Correction du TP#3
• Critique
• Réseaux et arbres
• Diagrammes noeuds - liens
• Matrices d’adjacence
• Partitions
• TP #4

5

Rappels graphe / arbre

Graphe :

• Modélise des relations (liens) entre entités (noeuds).

�Arbre

• Graphe hiérarchique,
• Graphes connecté avec n-1 liens (pour n noeuds)
• Relation parent-enfant entre les noeud

Typologie

• Homogènes
• Grilles
• Hierarchiques
• Arbres, Forêts
• Graphes bipartis
• Cycliques
• Polaires
• Multipolaire: e.g., “Small-world” graph

​

Ou trouve t’on ces données ?

• Tournois
• Organigrammes
• Généalogie
• Diagrammes
• Interactions entre entités (en biologie : gènes, protéines)
• Réseaux sociaux
• ...

Utilité

• Visualise la relation entre individus/objets (e.g., réseaux sociaux, hierarchies)
• Visualise l’échange d’information
• Visualise la mobilité (e.g., traffic aérien, véhicules, …)
• Visualise le fonctionnement d’algorithmes (e.g., réseaux de neurones, chaînes de Markov, réseaux bayésiens...)

Stratégies de visualisation pour les données réseaux ou arborescentes

Diagramme noeud-lien

​

Matrice d’adjacence

​

�Partitions

Noeud lien simple : �Arbre

Ici layout radial ->�(structure d’une bibliothèque logicielle)

Un point par noeud, un lien par connexion, distance au centre: profondeur

Tâches:

• Comprendre la topologie,
• suivre des chemins

Marche jusqu’à des milliers de noeuds

http://mbostock.github.com/d3/ex/tree.html

Diagramme noeud-lien simple

Positionnement par force (système masse-ressort)

• Permet d’explorer la structure, suivre des chemins, identifier des clusters.
• La position n’encode pas d’information en elle-même, seulement de façon relative. Et des éléments proches spatialement peuvent ne pas être proche sémantiquement

​

http://mbostock.github.com/d3/ex/force.html

Diagramme noeud lien complexe

Données: réseau + hiérarchie de noeuds

• Meilleur algorithme pour le même encodage visuel que précédemment,
• La hiérarchie est utilisée pour le placement, pas pour l’encodage visuel

Passe mieux à l’échelle, ~milliers de liens

​

Un peu de maths

Force-directed graph:

• Au plus simple: Système masse-ressort (1984)
• force attractives logarithmiques par arc
• force répulsive par sommets non adjacents en 1/r2
• Intégration Euler explicite
• Ajout de contraintes:
• Minimiser les intersections
• Minimiser la longueur des arcs, leur courbure

Problèmes quand la quantité d’éléments augmente

​

• Occlusion
• Arêtes qui se croisent

=> Suivi de chemin difficile�=> Difficile d’identifier des groupes�=> Interaction difficile (sélection, réorganisation, ...)

​

​

(hierarchical) edge bundling

Plan

• Correction du TP#3
• Critique
• Réseaux/graphes et arbres
• Diagrammes noeuds - liens
• Matrices d’adjacence
• Partitions
• TP #4

17

Matrice d’adjacence

Présence des personnage des Misérables dans le même chapitre

https://vega.github.io/vega/examples/reorderable-matrix/

Matrices d’adjacence

• Les noeuds sont positionnés en x et y
• Chaque lien est représenté par une marque à l’intersection entre les noeuds

=>

=>

Avantages / inconvénients

Matrice

• Pas de chevauchements de noeuds
• Pas de liens qui se croisent
• Navigation rapide
• Manipulation rapide
• Plus lisible pour certaines tâches
• Pas familier
• Consomme bcp d’espace
• Difficile de suivre des chemins

Noeuds-liens

• Familier
• Compact
• Efficace pour suivre des chemins
• Efficace sur les petits graphes
• Efficace sur les graphes avec peu denses
• Layout nécessaire
• Pbs d’occlusion
• Chaque manipulation implique un calcul complexe du layout

Mêler noeud-lien et matrice

Matlink

Mêler noeud-lien et matrice

http://www.michaelmcguffin.com/courses/vis/patternsInAdjacencyMatrix.png

Mêler noeud-lien et matrice

​

https://www.aviz.fr/Research/Nodetrix

Plan

• Correction du TP#3
• Critique
• Réseaux/graphes et arbres
• Diagrammes noeuds - liens
• Matrices d’adjacence
• Partitions
• TP #4

25

Treemap

Treemap

Pour des structures arborescentes�-> Conçus pour des systèmes de fichiers

1 attribut quantitatif par feuille (ex: taille du fichier)

• La surface encode la taille
• La zone englobante encode la hiérarchie

Passe très bien à l’échelle, jusqu’au million de feuilles

Exemple : https://vega.github.io/vega/examples/treemap/

​

Circle Packing Layout

Les noeuds sont des cercles

L’imbrication représente une relation parent-enfant

Problèmes :

• Mauvaise utilisation de l’espace
• La taille des parents n’est pas forcément indicative

Autres stratégies d’affichage d’arbres

Quantifying the Space-Efficiency of 2D Graphical Representations of Trees. McGuffin and Robert. Information Visualization 9:2 (2010), 115–140.

Collections

• Graph-visualization-introduction
• https://observablehq.com/@bstaats/graph-visualization-introduction
• A Visual Bibliography of Tree Visualization
• https://www.treevis.net/
• Dynamic Graph Visualization
• http://dynamicgraphs.fbeck.com/
• Visualizing Group Structures in Graphs
• http://groups-in-graphs.corinna-vehlow.com/