Force-based layout

Les algorithmes de dessin basé sur les forces (Force-based ou Force-directed algorithms) permettent de positionner les nœuds d'un graphe pour faciliter sa visualisation en utilisant un système de force appliqués entre les nœuds et les arcs.

Visualisation de réseaux sociaux à l'aide d'un algorithme de dessin de graphe basé sur les forces[1].

Méthode

L'algorithme peut être décrit comme une analogie physique des composants du graphe :

  • Les nœuds sont représentés par des particules de même charge
  • Les arcs sont assimilables à des ressorts

À chaque passe, l'algorithme fait la somme des forces appliquées sur chacun des nœuds puis les déplace suivant des règles de physique classique jusqu'à trouver un état stable.

Avantages
  • Interactivité: les nœuds peuvent être replacés à la volée pendant le calcul, être ajoutés ou supprimés.

Inconvénients
  • Ce sont des algorithmes souvent coûteux en puissance de calcul.
  • Ces algorithmes souffrent pour la plupart de terminer dans un état qui n'est qu'un minimum local du problème d'optimisation à l'origine de la modélisation physique, et non dans l'état minimum absolu.

Références
  1. Martin Grandjean, Introduction à la visualisation de données, l'analyse de réseau en histoire

Voir aussi
  • icône décorative Portail de la géométrie
  • icône décorative Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.