Force-based layout

Cet article est une ébauche concernant la géométrie et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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.