Visualisation de graphes

Logo Esipe-mlv Logo Esipe-mlv

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:

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

À 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

 

Yifan Hu

 

Force Atlas 2

Force Atlas 2 Layout

 

OpenOrd

Open Ord Layout

 

Circular Layout

Circular Layout

 

Geographic Map

Geographic Map Layout