Visualisation de graphes

Algorithmes de modélisation de graphes

Dans ce chapitre, nous présenterons les principes de base d'une modélisation de graphes, notamment avec le Force-based algorithm. De nombreux algorithmes existent. Cette liste n'est en aucun cas exhaustive, cependant ces algorithmes sont implémentés par l'outil Gephi. Les données exposées dans cette partie proviennent de la présentation suivante: Gephi Layouts.

Force-based ou Force-directed algorithms

Cet algorithme sert de base pour la plupart des algorithmes de modélisation. Son principe est extrèmement simple:

Tous les nœuds se repoussent entre eux, respectant le principe des aimants. Plus les noeuds sont éloignés, moins ils se repoussent.
Les liens servent de ressort entre deux nœuds.

À chaque passe de l'algorithme, on applique la somme des forces sur chacun des nœuds. On déplace ces nœuds jusqu'à trouver un état stable.

Fruchterman Reingold

Utilisation: ancienne référence ⁄ devient obsolète
Auteurs: Thomas Fruchterman & Edward Reingold
Date: 1991
Complexité: O(N²)
Taille du graphe: 1 à 1 000 nœuds
Gestion de la taille des liens: non

Yifan Hu

Utilisation: pour une modélisation très rapide - analyse de complémentarités (si le temps n'est pas un paramètre important, Force Atlas 2 est plus adapté)
Auteur: Yifan Hu
Date: 2005
Complexité: O(N*log(N))
Taille du graphe: 100 à 100 000 nœuds
Gestion de la taille des liens: non