Force Directed Graph - Qu'est ce que c'est ?

Un Force-Directed Graph, ou graphique fondé sur les forces, est un type de mise en page couramment utilisé dans divers secteurs d'application : la visualisation de réseau, la visualisation de larges graphiques, la représentation des connaissances, la gestion de système, ou encore la visualisation de maillage.

Il permet de visualiser les connexions entre les objets d'un réseau. En regroupant les objets connectés entre eux de façon naturelle, un Force-Directed Graph est visuellement intéressant et permet aussi de découvrir des relations subtiles entre les groupes.

Ces graphiques présentent la particularité d'être dessinés par des algorithmes dénommés " force-directed graph drawing algorithms " ou " algorithmes de tracé de graphiques force-directed " en Français.

 

Force-directed-graph-1

On parle aussi parfois d'algorithme " spring-embedder " ou d'algorithme " de placement basé sur l'énergie ". Cet algorithme arrange les graphiques de façon naturelle et esthétiquement plaisante. En règle générale, le résultat est symétrique et présente une structure en grappe. La distribution des différents " noeuds " est harmonieuse et bien équilibrée.

L'algorithme est basé sur un modèle physique. Il calcule la disposition du graphique en se basant uniquement sur les informations contenues dans la structure du graphique plutôt que de reposer sur des connaissances liées à un domaine spécifique.

Les noeuds sont représentés par des points qui se repoussent entre eux comme des aimants. Les bordures quant à elles connectent ces points en simulant une force de ressort pour attirer les noeuds adjacents.

Le modèle détermine les forces agissant sur les noeuds de façon itérative et les déplace dans le but d'approcher le plus possible d'un équilibre où la position des noeuds reste stable.

L'algorithme de Tutte, créé en 1963, est l'une des premières méthodes de tracé de graphique basées sur des représentations barycentriques. Auparavant, la méthode de mise en page de Eades et l'algorithme de Frucherman et Rein-gold reposaient déjà sur des forces de ressort similaires à celles de la loi de Hooke.

SocialNetworkAnalysis

source : wikipédia

Les forces entre les noeuds peuvent aussi être calculées en se basant sur leurs distances théoriques, déterminées par la longueur du chemin le plus court entre eux. L'algorithme de Kamada et Kawai utilise des forces de ressort proportionnelles aux distances théoriques du graphique.

Le grand avantage de ce type d'algorithme de tracé de graphique Force-Directd est la simplicité de son implémentation. Cependant, il fonctionne davantage pour les graphiques où le nombre de lignes est similaire au nombre de points. Les graphiques plus denses avec de nombreuses lignes ou les graphiques déstructurés sont moins adaptés.

Si les directions des lignes sont trop importantes, ce n'est pas non plus le meilleur choix. Pour cause, cette méthode de visualisation ne prend pas en compte ces directions.