2. Quel(s) algorithme(s) pour quel(s) objectif(s) de représentation ?

2.1. Mettre en avant des divisions entre différentes composantes de la cartographie
2.2. Mettre en avant des complémentarités entre les différents éléments de la cartographie
2.3. Mettre en avant une logique de classification des éléments du graphique
2.4. Autres algorithmes

📘

La logique des layouts "force based"

Les nœuds se repoussent comme des aimants, tandis que les liens attirent les nœuds qu’ils connectent, tels des ressorts.

Ces forces mettent les nœuds en mouvement, jusqu’à ce qu’un point d’équilibre soit atteint (les nœuds ne bougent plus).

2.1. Mettre en avant des divisions entre différents composantes de la cartographie

OpenOrd a pour objectif de mettre en avant des divisions entre les différentes parties de la cartographie.

2.2. Mettre en avant des complémentarités entre les différents éléments de la cartographie

📘

Algorithme Force Atlas

Force Atlas permet de spatialiser des réseaux small-world / sans échelle. Il est axé sur la qualité, pour explorer « des données réelles » et permettre une interprétation rigoureuse du graphique avec le moins de biais possibles, et une bonne lisibilité.

La valeur de la force de répulsion dépend de la densité des nœuds et de leurs relations, l’important étant de bien distinguer les nœuds et de pouvoir lire chaque label (qui s’affiche via le « T » en bas de l’écran). La variable d’ajustement par taille permet d’éviter les chevauchements.

  • de 1 à 10 000 noeuds. Opportunité de mettre en exergue le poids des noeuds.
556556

A noter la possibilité d’utiliser « Force Atlas 2 », une version de cet algorithme adaptée pour traiter des réseaux de plusieurs centaines de milliers de noeuds :

12231223

Ce qui nous donnera par exemple :

15371537

📘

Algorithme Fruchterman-Rheingold

Fruchterman-Rheingold, le layout classique. Les forces s’exercent entre noeuds voisins. Il simule le graphique comme un système de particules de masse. Les noeuds sont les particules de masse et les bords sont des ressorts entre les particules.

  • de 1 à 1 000 noeuds. Pas de poids pour les noeuds.
14641464

📘

Algorithme Kamada and Kawai

Kamada and Kawai utilise une force d’attraction entre deux noeuds proportionnelle à la taille du chemin le plus court les séparant.

📘

Algorithme Yifan Hu

Yifan Hu rassemble les noeuds en groupe, et applique une logique force-based à ces groupes. Il s’agit d’un algorithme très rapide avec une bonne qualité sur les grands graphes. Il combine un modèle de force dirigée par une technique graphique de grossissement (algorithme à plusieurs niveaux) pour réduire la complexité. Les forces de répulsion sur un nœud d’un cluster de nœuds distants sont approchées par un calcul Barnes-Hut, qui les traite comme un super-nœud.

  • de 100 à 100 000 noeuds. Pas de poids sur les noeuds.
15401540

2.3. Mettre en avant une logique de classification des éléments du graphique

📘

Circular Axis

Circular Axis Il attire les nœuds dans un cercle ordonné par ID, une métrique (degré, betweenness centralité …) ou par un attribut. A utiliser pour montrer une distribution de nœuds avec leurs liens.

  • de 1 à 1 000 000 noeuds

📘

Radial Axis Layout

Radial Axis Layout regroupe les nœuds et attire les groupes axes rayonnant vers l’extérieur à partir d’un cercle central. Les groupes sont générés à l’aide d’une métrique (degré, betweenness centralité …) ou un attribut. A utiliser pour étudier les rapprochements en montrant les distributions de nœuds à l’intérieur des groupes avec leurs liens.

  • de 1 à 1 000 000 de noeuds.

📘

GeoLayout

GeoLayout permet d’obtenir une répartition géographique sur un support de carte. Il utilise des coordonnées latitude/ longitude pour définir la position des noeuds sur le réseau. Plusieurs projections sont disponibles, y compris Mercator qui est utilisé par Google Maps et d’autres services en ligne. Les deux colonnes d’attributs de nœud pour les coordonnées doivent être au format numérique.

2.4. Autres algorithmes

  • Ajustement des labels/ noverlap : éviter que les noms se chevauchent sur votre réseau
  • Contraction/ expansion : augmente ou diminue l’espace entre les nœuds