Visualisation de graphes et de réseaux
La visualisation de graphes et de réseaux représente des entités et leurs relations, le plus souvent sous forme de diagrammes nœuds-liens, aidant ainsi à percevoir des structures telles que des regroupements, des chemins et des nœuds centraux.
Definition
La visualisation de graphes et de réseaux est la représentation visuelle de données composées d'entités et des relations entre elles, utilisant des dispositions qui positionnent les nœuds et tracent les liens, ou des représentations matricielles, afin que les propriétés structurelles du réseau deviennent perceptibles.
Scope
Ce sujet couvre la représentation visuelle des données relationnelles : les diagrammes nœuds-liens et les algorithmes de disposition de graphes tels que les dispositions par force dirigée et hiérarchiques, les représentations matricielles de graphes, les techniques pour les réseaux vastes et denses, ainsi que les critères de navigation et d'esthétique pour des graphes lisibles. Il ne traite pas de la théorie algorithmique des graphes en tant que structures de données, qui relève des algorithmes, ni des bases perceptives de l'encodage en général, abordées sous l'encodage visuel et la perception.
Core questions
- Comment les algorithmes de disposition positionnent-ils les nœuds pour révéler la structure ?
- Quand les diagrammes nœuds-liens sont-ils préférables aux représentations matricielles ?
- Comment rendre lisibles des réseaux très vastes ou denses ?
- Quels critères esthétiques facilitent l'interprétation d'un dessin de graphe ?
Key concepts
- diagramme nœuds-liens
- disposition par force dirigée
- disposition hiérarchique (par couches)
- représentation par matrice d'adjacence
- minimisation des croisements d'arêtes
- esthétique des graphes
- regroupement et agrégation
- extensibilité des grands réseaux
Key theories
- Disposition et esthétique des graphes
- Le dessin de graphes recherche des dispositions qui satisfont des critères esthétiques tels que peu de croisements d'arêtes, des arêtes courtes et uniformes, et une symétrie révélée ; les algorithmes par force dirigée et hiérarchiques produisent des dispositions qui rendent la structure visible.
- Représentations nœuds-liens versus matricielles
- Des expériences contrôlées montrent que les diagrammes nœuds-liens sont efficaces pour les graphes petits et clairsemés et les tâches de suivi de chemins, tandis que les représentations matricielles s'adaptent mieux aux graphes denses et de grande taille et aux tâches telles que la recherche du nœud le plus connecté.
- Navigation et extensibilité
- Les études sur la visualisation de graphes répertorient les méthodes de navigation et de simplification des grands réseaux, y compris le regroupement (clustering), le filtrage et la navigation focus-plus-contexte, afin de maintenir l'interprétabilité des graphes de grande taille.
Clinical relevance
La visualisation de réseaux est utilisée pour comprendre les relations dans les réseaux sociaux, les voies biologiques, les infrastructures et les graphes de connaissances ; le choix de la représentation et de la disposition appropriées aide les analystes à identifier des communautés, des centres (hubs) et des chemins qui seraient invisibles dans les données relationnelles brutes.
History
Le dessin de graphes a développé de solides fondations algorithmiques dans les années 1980 et 1990, résumées dans l'ouvrage de Di Battista et ses collègues en 1999. Herman, Melancon et Marshall ont passé en revue la visualisation de graphes pour la visualisation d'informations en 2000, et des études contrôlées ultérieures, telles que la comparaison nœuds-liens versus matrice, ont affiné les recommandations concernant les choix de représentation pour des réseaux de différentes tailles.
Debates
- Diagrammes nœuds-liens versus représentations matricielles pour les grands graphes
- Les diagrammes nœuds-liens sont intuitifs et largement préférés, mais ils deviennent encombrés à mesure que les graphes deviennent denses, tandis que les représentations matricielles restent lisibles à grande échelle mais sont moins naturelles pour le suivi de chemins ; le meilleur choix dépend de la taille, de la densité et de la tâche du graphe.
Key figures
- Ivan Herman
- Giuseppe Di Battista
- Peter Eades
- Roberto Tamassia
- Jean-Daniel Fekete
Related topics
Seminal works
- dibattista1999
- herman2000
- ghoniem2005
Frequently asked questions
- Qu'est-ce qu'une disposition par force dirigée ?
- Une disposition par force dirigée traite un graphe comme un système physique, où les arêtes agissent comme des ressorts qui attirent les nœuds connectés les uns vers les autres, et les nœuds se repoussent mutuellement. Laisser la simulation se stabiliser produit une disposition où les groupes fortement connectés se regroupent et la structure globale devient visible, sans placement manuel.
- Pourquoi utiliser une matrice plutôt qu'un diagramme nœuds-liens ?
- Pour les réseaux vastes et denses, les diagrammes nœuds-liens deviennent un enchevêtrement d'arêtes qui se croisent. Une représentation matricielle place les nœuds le long des lignes et des colonnes et marque chaque connexion dans une cellule, évitant ainsi l'encombrement des arêtes et facilitant, à grande échelle, des tâches telles que l'identification des nœuds fortement connectés ou des sous-groupes denses.