Aller au contenu

Force-based layout

Un article de Wikipédia, l'encyclopédie libre.
Visualisation de réseaux sociaux à l'aide d'un algorithme de dessin de graphe basé sur les forces[1].

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.

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.

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

Inconvénients

[modifier | modifier le code]
  • 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

[modifier | modifier le code]