Spatialisations (FR)
Bienvenue sur ce tutoriel avancé.Vous apprendrez ici les techniques avancées de spatialisation de réseaux dans Gephi et notamment l’utilisation d’algorithmes qui déterminent la position des noeuds dans l’espace graphique.
Ce tutoriel se base sur la version 0.8alpha de Gephi.
Télécharger Gephi
Il est nécessaire d’installer des plug-ins supplémentaires.
~~ Image : blog_geolayout1_FR.png ~~
- Dans le menu Outils, cliquez sur Plug-ins.
- Dans l’onglet Plug-ins disponibles, cochez :
- OpenOrdLayout
- CircularLayout
- GeoLayout
- Geometric Transformation
- NoverlapLayout
~~ Image : tutorial_quickstart1_FR.png ~~
- Téléchargez le fichier LesMiserables.gexf
- Dans la barre de menu, allez dans le menu Fichier et cliquez sur Ouvrir....
- Lorsque votre fichier est ouvert, le rapport récapitule les données trouvées et les problèmes rencontrés.
- Nombre de noeuds
- Nombre de liens
- Type de graphe
Format du graphe
- GEXF
- GraphML
- Pajek NET
- GDF
- GML
- Tulip TLP
- CSV
- Netdraw VNA
- Archives ZIP/GZ
Nous avons importé l’ensemble de données du graphe LesMiserables.gexf1. Il s’agit d’un réseau pondéré des apparitions simultanées des personnages du roman Les Misérables de Victor Hugo.
~~ Image : ? ~~
Les noeuds sont d’abord placés de manière aléatoire, la présentation que vous voyez peut donc différer légèrement.
1D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing, Addison-Wesley, Reading, MA (1993).
La fonction principale des algorithmes de spatialisation est de définir la forme du graphe.
- Dans le volet à gauche de l’écran, affichez le module Spatialisation.
~~ Image : tutorial_quickstart6_FR.png ~~
- Sélectionnez Force Atlas.
Vous pouvez voir les propriétés de la spatialisation sous son nom. Laissez les valeurs par défaut.
- Pour lancer l’algorithme, cliquez sur Exécuter.
- Vous voyez à présent les positions des noeuds qui changent en temps réel.
Algorithmes de spatialisation
La spatialisation des graphes est généralement réalisée à partir d’algorithmes basés sur les forces. Ils suivent un principe simple : les noeuds reliés s’attirent et les noeuds non reliés se repoussent.
Les propriétés de spatialisation vous permettent de contrôler l’algorithme afin de générer une représentation lisible.
~~ Image : tutorial_quickstart9_FR.png ~~
- Pour agrandir le graphe, réglez la Force de répulsion sur 10 000.
- Pour valider la valeur modifiée, appuyez sur la touche Entrée de votre clavier.
- Vous pouvez maintenant Arrêter l’algorithme.
Conseils
Si vous ne voyez plus le graphe, cliquez sur l’icône Centrer sur le graphe situé dans le coin inférieur gauche de la fenêtre de visualisation.
~~ Image : ? ~~
Exécutez à nouveau la spatialisation puis déplacez les noeuds de façon à mieux les distinguer.
~~ Image : mouseselect_FR.png ~~
- Repérez le bouton Déplacement situé dans l’angle supérieur gauche de la fenêtre de visualisation.
- Ajustez le diamètre de sélection dans la fenêtre ou à l’aide du raccourci « Ctrl + molette de la souris ».
Dans les propriétés de la spatialisation, réglez la Force d’auto-stabilisation à 100 000, puis déplacez les noeuds. Cela permet de réduire les déformations du graphe.
- Vous pouvez maintenant Arrêter l’algorithme.
~~ Images : ??? ~~
Gephi propose différents algorithmes de spatialisation. Ils permettent de définir la forme du graphe.
- OpenOrd
~~ Image : ? ~~ - Force Atlas 2
~~ Image : ? ~~ - Radial Axis
~~ Image : ? ~~ - GeoLayout
~~ Image : ? ~~
Sélectionnez une spatialisation en fonction des caractéristiques de la topologie que vous souhaitez mettre en avant :
- mise en avant
DIVISIONS
OpenOrd - mise en avant
COMPLÉMENTARITÉS
ForceAtlas, Yifan Hu, Fruchterman-Reingold - mise en avant
CLASSEMENT
Circular, Radial Axis - mise en avant
RÉPARTITION GÉOGRAPHIQUE
GeoLayout
Ajustements graphiques
- Ajustement des labels
- Noverlap
- Expansion
- Contraction
Cette spatialisation propre à Gephi permet de spatialiser des réseaux sans échelle et des réseaux petit-monde. Elle est centrée sur la qualité (elle doit ainsi « être utile pour explorer des données réelles ») afin de permettre une interprétation rigoureuse des graphes (avec le plug-in Social Network Analysis par exemple) le plus directement et lisiblement possible malgré un temps d’exécution assez long.
| Auteur : | Mathieu Jacomy |
| Date : | 2007 |
| Type : | Basé sur les forces |
| Complexité : | O(N²) |
| Taille du graphe : | 1 à 10 000 noeuds |
| Gestion de la taille des liens : | Oui |
~~ Image : ? ~~
Exécuter la spatialisation en appliquant les réglages suivants étape par étape :
- Force d’auto-stabilisation = 2 000
Plus elle est élevée, plus les noeuds se déplacent lentement. - Force de répulsion = 1 000
Force avec laquelle les noeuds se repoussent. - Force d’attraction = 1
Force avec laquelle les paires de noeuds connectés s’attirent. - Gravité = 100
Attire tous les noeuds vers le centre pour éviter la dispersion des composants déconnectés. - Attraction distribuée = coché
Repousse les noyaux (nombre important de liens sortants) à la périphérie et rapproche les autorités (nombre important de liens entrants) du centre.
Vous pouvez maintenant Arrêter l’algorithme.
Ajustement par taille
Cette option permet d’éviter le chevauchement des noeuds, en fonction la taille de chaque noeud.
Elle permet au graphe de simuler un système de particules de masse. Les noeuds représentent les particules de masse et les liens représentent les ressorts entre ces particules. Les algorithmes tentent de minimiser l’énergie de ce système physique. L’utilisation de cette spatialisation est devenue une pratique courante même si elle demeure très lente.
| Auteur : | Thomas Fruchterman et Edward Reingold1 |
| Date : | 1991 |
| Type : | Basé sur les forces |
| Complexité : | O(N²) |
| Taille du graphe : | 1 à 1 000 noeuds |
| Gestion de la taille des liens : | Non |
~~ Image : ? ~~
1Fruchterman, T. M. J., et Reingold, E. M. (1991). Graph Drawing by Force-Directed Placement. Software: Practice and Experience, 21(11).
Exécuter la spatialisation en appliquant les réglages suivants étape par étape :
- Zone = 100
- Zone = 100 000
Zone de la taille du graphe. - Gravité = 1 000
- Gravité = 100
Attire tous les noeuds vers le centre pour éviter la dispersion des composants déconnectés.
Vous pouvez maintenant Arrêter l’algorithme.
Position des noeuds instable
Il arrive parfois que l’algorithme ne converge pas, ce qui rend alors le graphe instable. Réduisez le réglage Vitesse afin d’améliorer la précision.
Il s’agit d’un algorithme très rapide et de très bonne qualité pour les grands graphes. Il combine un modèle basé sur les forces et une technique de simplification de graphes (algorithme multi-niveaux) pour réduire la complexité. Les forces de répulsion entre un noeud et un groupe de noeuds distants sont calculées approximativement avec l’algorithme de Barnes-Hut qui les traite comme un super-noeud. La spatialisation s’arrête automatiquement.
| Auteur : | Yifan Hu1 |
| Date : | 2005 |
| Type : | Basé sur les forces + multi-niveaux |
| Complexité : | O(N*log(N)) |
| Taille du graphe : | 100 à 100 000 noeuds |
| Gestion de la taille des liens : | Non |
~~ Image : ? ~~
1Y. F. Hu, Efficient and high quality force-directed graph drawing. The Mathematica Journal, 10 (37-71), 2005.
Exécutez la spatialisation en appliquant les réglages suivants étape par étape :
- Ratio du pas = 0.99
Ratio utilisé pour mettre à jour la taille du pas. Son augmentation permet d’obtenir une meilleure qualité (au dépend de la vitesse). - Distance optimale = 200
Longueur naturelle des ressorts. Son augmentation permet d’éloigner les noeuds les uns des autres. - Theta = 1.0
Approximation de l’algorithme de Barnes-Hut. Les faibles valeurs augmentent la précision.
Elle implique l’utilisation de grands graphes non orientés et a pour objectif de mieux distinguer les groupes de noeuds. Elle peut être exécutée en parallèle d’une accélération du traitement informatique et s’arrête automatiquement. L’algorithme est basé sur la spatialisation Fruchterman Reingold et fonctionne avec un nombre déterminé d’itérations contrôlées par le biais d’une méthode de type recuit simulé (options liquid, expansion, cool-down, crunch et simmer du plug-in). Les liens longs sont coupés pour permettre aux groupes de noeuds de se séparer.
| Auteur : | S. Martin, W. M. Brown, R. Klavans, et K. Boyack1 |
| Date : | 2010 (VxOrd) |
| Type : | Basé sur les forces + recuit simulé |
| Complexité : | O(N*log(N)) |
| Taille du graphe : | 100 à 1 000 000 noeuds |
| Gestion de la taille des liens : | Oui |
~~ Image : ? ~~
1S. Martin, W. M. Brown, R. Klavans, et K. Boyack, « OpenOrd: An Open-Source Toolbox for Large Graph Layout, » SPIE Conference on Visualization and Data Analysis (VDA)., 2011
Exécutez la spatialisation en appliquant les réglages suivants étape par étape :
- Edge cut = 0.95
De 0 (Fruchterman Reingold standard) à 1. Pourcentage correspondant à la plus grande distance entre deux noeuds sur le graphe. Une valeur de coupe élevée entraîne la formation d’un plus grand nombre de groupes de noeuds. - Num iterations = 100
Contracte les groupes de noeuds. - Num iterations = 850
Étend les groupes de noeuds. - Random seed = -6308261588084905834
Utilisez cette valeur pour produire exactement la même forme que celle précédemment affichée.
Verrouillage du placement d’un noeud
Pour verrouiller la position d’un noeud (ou d’un groupe de noeuds sélectionnés), cliquez avec le bouton droit sur un noeud, puis cliquez sur Fixer. Fonctionne pour toutes les spatialisations sauf Yifan Hu. Pour OpenOrd, utilisez le paramètre Fixed time du volet Spatialisation pour configurer le temps de verrouillage des noeuds.
~~ Image : tutorial-layouts15_FR.png ~~
OpenOrd est très utile pour les grands graphes.
~~ Image : tutorial_quickstart1_FR.png ~~
- Importez le fichier internet_routers-22july06.gml.zip
Ce réseau est constitué de 22 963 noeuds et de 48 436 liens. Il s’agit d’un snapshot symétrique représentant la structure d’Internet au niveau des systèmes autonomes, reconstruit à partir des tables BGP postées par l’université d’Oregon dans le cadre du projet Route Views. Ce snapshot a été créé à partir de données par Mark Newman le 22 juillet 2006.
Si vous possédez un ordinateur avec processeurs multi-coeurs :
Augmentez le nombre de fils pour l’exécuter en parallèle et par conséquent accélérer l’exécution de l’algorithme. Il est recommandé de régler le nombre de coeurs de votre processeur sur le nombre de coeurs moins un, afin de conserver un fil pour l’affichage.
- Réglez le paramètre Num Threads (Nb fils) ou laissez les paramètres par défaut.
- Cliquez sur Exécuter et patientez jusqu’à l’arrêt.
~~ Image : tutorial-layouts33.png ~~
OpenOrd s’exécute en un nombre déterminé d’itérations, vous pouvez donc voir sa progression dans l’angle inférieur droit de l’écran.
~~ Image : ? ~~
Une fois le deuxième ensemble de données importé, un nouvel espace de travail est créé automatiquement. Vous vous situez en ce moment dans le « Workspace 2 ». Retournons maintenant dans le « Workspace 1 » où le graphe LesMiserables.gexf est encore présent.
~~ Image : tutorial-layouts32.png ~~
- Repérez la zone qui permet de basculer entre les espaces de travail dans l’angle inférieur droit de l’écran.
- Vous pouvez voir le nom de l’espace de travail en cours d’utilisation.
- Cliquez dessus et sélectionnez « Workspace 1 ». Vous pouvez aussi cliquer sur les flèches pour changer d’espace de travail.
Version améliorée de la spatialisation Force Atlas pour gérer de vastes réseaux tout en conservant une très bonne qualité. La répulsion des noeuds est calculée approximativement avec l’algoritme de Barnes-Hut, qui réduit par conséquent la complexité de l’algorithme de spatialisation. Remplace les forces d’attraction et de répulsion par un paramètre Échelle.
| Auteur : | Mathieu Jacomy1 |
| Date : | 2011 |
| Type : | Basé sur les forces |
| Complexité : | O(N*log(N)) |
| Taille du graphe : | 1 à 1 000 000 noeuds |
| Gestion de la taille des liens : | Oui |
~~ Image : ? ~~
1https://gephi.wordpress.com/2011/06/06/forceatlas2-the-new-version-of-our-home-brew-layout/
Cette page est disponible uniquement en anglais.
Exécuter la spatialisation en appliquant les réglages suivants étape par étape :
- Mode LinLog = activé
- Mode LinLog = désactivé
L’attraction linéaire et la répulsion logarithmique (lin-lin par défaut), contractent les groupes de noeuds. - Échelle = 100
Plus la valeur est élevée, plus le graphe est clairsemé. - Influence du poids des liens = 0
De 0 (pas d’influence) à 1 (normal). La valeur 0 permet de calculer les forces sans tenir compte du poids des liens.
Vous pouvez maintenant Arrêter l’algorithme.
Performance
~~ Image : tutorial-layouts18_FR.png ~~
Activez Répulsion Approximative uniquement sur les grands graphes. Nous allons cependant tester ce paramètre dans ce tutoriel. Activez-le, définissez le paramètre Tolérance sur 0.04 et exécutez l’algorithme puis observez l’oscillation des noeuds !
Il permet de tracer des noeuds en cercle selon leur identifiant, une mesure (degré, betweenness centrality...) ou un attribut. Utilisez cette spatialisation pour afficher une distribution des noeuds et leurs liens.
| Auteur : | Matt Groeninger1 |
| Date : | 2010 |
| Type : | Circulaire |
| Complexité : | O(N) |
| Taille du graphe : | 1 à 1 000 000 noeuds |
~~ Image : ? ~~
1https://gephi.org/gephi-plugins-front/#/plugin/circular-layout
Cette page est disponible uniquement en anglais.
- Sélectionnez Circular Layout dans le volet Spatialisation
- Définissez le paramètre Order Nodes by sur Degree.
- Exécuter la spatialisation.
~~ Image : tutorial-layouts22.png ~~
- Dans le volet Classement, sélectionnez Degree (Degré) comme paramètre de classement.
- Pour régler la taille, sélectionnez l’icône en forme de diamant dans la barre d’outils.
- Réglez la taille minimale à 10 et la taille maximale à 50.
- Pour visualiser la distribution du degré, cliquez sur Exécuter
~~ Image : tutorial-layouts21_FR.png ~~
- Exécuter de nouveau la spatialisation pour éviter un chevauchement de noeuds.
Cette spatialisation est fournie avec le plug-in Circular Layout. Elle permet de regrouper les noeuds et de tracer les groupes selon des axes (ou des courbes) qui rayonnent vers l’extérieur depuis un cercle central. Les groupes sont générés à partir d’une mesure (degré, betweenness centrality...) ou d’un attribut. Utilisez la spatialisation pour étudier l’homophilie en affichant les distributions des noeuds dans des groupes avec leurs liens.
| Auteur : | Matt Groeninger1 |
| Date : | 2011 |
| Type : | Circulaire |
| Complexité : | O(N) |
| Taille du graphe : | 1 à 1 000 000 noeuds |
~~ Image : ? ~~
1https://gephi.org/gephi-plugins-front/#/plugin/circular-layout
Cette page est disponible uniquement en anglais.
Nous souhaitons maintenant étudier la structure communautaire de ce réseau : est-il naturellement séparé en groupes de noeuds avec des connexions denses au sein des groupes et des connexions espacées entre les groupes ?
~~ Image : ? ~~
Dans le volet Statistiques, cliquez Exécuter sur en regard de la ligne Modularité1.
L’algorithme de détection de communauté a créé une valeur Modularity Class pour chaque noeud.
Le module Partition peut utiliser ces nouvelles données pour mettre en couleur les communautés.
~~ Image : tutorial_quickstart30_FR.png ~~
- Repérez le module Partition dans le volet à gauche de l’écran.
- Cliquez sur le bouton Rafraîchir pour remplir la liste de partitions.
- Dans la liste de partitions, sélectionnez Modularity Class.
~~ Image : ? ~~
Dans l’exemple ci-contre, neuf communautés ont été trouvées. Ce nombre peut être différent pour vous. Une couleur a été définie au hasard pour chaque identifiant de communauté.
- Pour colorer les noeuds, cliquez sur Exécuter.
1Blondel V, Guillaume J, Lambiotte R, Mech E (2008) Fast unfolding of communities in large networks. J Stat Mech : Theory Exp 2008:P10008. (http://findcommunities.googlepages.com)
Exécuter la spatialisation en appliquant les réglages suivants étape par étape :
- Group Nodes by = Degree
Homophilie par degré ? - Group Nodes by = Modularity Class
- Order Nodes in Spar/Axis by = Degree
Distribution des noeuds par degré dans chaque communauté. - Draw Spar/Axis as Spiral = coché
Meilleure visualisation des liens dans les communautés - Draw Spar/Axis as Spiral = décoché
- Ascending Order of Spar/Axis = coché
Meilleure visualisation des liens entre les communautés
~~ Images : ???? ~~
GeoLayout utilise les coordonnées de latitude et de longitude pour définir la position des noeuds dans le réseau. Plusieurs projections sont disponibles, dont celle de Mercator qui est utilisée par Google Maps et d’autres services en ligne. Les deux colonnes d’attributs des noeuds doivent être au format numérique pour les coordonnées.
| Auteur : | Alexis Jacomy1 |
| Date : | 2010 |
| Type : | Cartographie |
| Complexité : | O(N) |
| Taille du graphe : | 1 à 1 000 000 noeuds |
~~ Image : ? ~~
1http://gephi.org/2010/map-geocoded-data-with-gephi/
Cette page est disponible uniquement en anglais.
- Téléchargez le fichierairlines-sample.gexf et ouvrez-le.
~~ Image : tutorial_quickstart1_FR.png ~~
Le réseau est un graphe non-orienté qui comporte 235 noeuds et 1 297 liens. Chaque noeud se caractérise par sa latitude et sa longitude qui sont exprimées en degrés.
- Dans le module Spatialisation, sélectionnez Geo Layout dans la liste.
Cliquez sur Exécuter.
~~ Image : blog_geolayout3_FR.png ~~ ~~ Image : blog_geolayout4_FR.png ~~
Il arrive que la spatialisation ne soit pas totalement satisfaisante. En effet, des noeuds de grande taille chevauchent parfois des noeuds plus petits. Trois techniques différentes permettent d’éviter ce désagrément.
L’algorithme Force Atlas dispose d’une option qui permet de prendre en compte la taille des noeuds lors de l’application de la spatialisation.
~~ Image ? ~~
- Retournez au Workspace 1.
- Dans le volet Spatialisation, sélectionnez Force Atlas.
- Pour réinitialiser les paramètres de spatialisation, cliquez sur Réinitialiser en bas du volet.
- Exécuter l’algorithme.
- Vérifiez l’option Ajustement par taille (Empêcher le Recouvrement dans Force Atlas 2) et exécutez à nouveau l’algorithme pendant un court instant.
- Réglez la Force de répulsion sur 1 000.
- Réglez la Force d’auto-stabilisation sur 500.
- Arrêter l’algorithme.
~~ Image : tutorial_quickstart26_FR.png ~~
Les noeuds ne se chevauchent plus désormais.
Instabilité !
Cette option rend la position des noeuds très instable et perturbe le processus de spatialisation. Utilisez cette option à la fin pour améliorer votre spatialisation.
Utilisez cette option après n’importe quelle spatialisation afin d’éviter le chevauchement des noeuds tout en conservant la forme de votre graphe. Cette spatialisation est optimisée pour les graphes de grande taille.
~~ Image : blog_geolayout9_FR.png ~~
- Tout d’abord, exécutez la spatialisation Yifan Hu.
- Sélectionnez l’algorithme Noverlap, puis exécutez-le jusqu’à ce qu’il s’arrête.
- Pour améliorer la qualité, réduisez le paramètre speed à 0.1.
- Pour augmenter l’espacement entre les noeuds, augmentez le paramètre ratio à 2 et la paramètre margin à 10.
Les noeuds ne se chevauchent plus désormais.
~~ Images : ?? ~~
Cette spatialisation ajuste la taille du texte pour repousser les noeuds et ainsi rendre chaque label lisible. Elle fonctionne uniquement sur les noeuds visibles dans le volet Visualisation.
- Repérez les réglages du volet Visualisation.
- Pour activer l’affichage du texte, cliquez sur T.
- Augmentez la taille du texte au maximum.
~~ Image : tutorial_visualization11_FR.png ~~
~~ Image : tutorial-layouts13_FR.png ~~
- Allez sur la fenêtre Spatialisation.
- Sélectionnez l’algorithme Ajustement des labels, puis exécutez-le jusqu’à ce qu’il s’arrête.
~~ Images : ?? ~~
Aucun point cardinal n’est indiqué sur les spatialisations et les distances sont toujours relatives. Si une spatialisation est utilisée à plusieurs reprises dans un graphe, elle peut produire des formes avec des orientations et une échelle différentes. Les transformations sont parfois utiles pour comparer des graphes orientés.
Pour effectuer des transformations de base sur le graphe, utilisez les spatialisations suivantes :
- Rotation sens horaire avec un angle égal à -90°
- Rotation sens anti-horaire avec un angle égal à -45°
- Expansion avec un facteur d’échelle égal à 1.2
- Contraction avec un facteur d’échelle égal à 0.8
Spatialisation Transformation
Le plug-in Geometric Transformation permet d’associer à la fois des rotations, des homothéties et des transpositions.
L’enregistrement de votre projet regroupe l’ensemble des données et des résultats dans un fichier de session unique.
~~ Image : ? ~~
~~ Image : tutorial_quickstart48_FR.png ~~
Avec ce tutoriel, vous avez appris à utiliser différentes spatialisations dans Gephi en fonction de la caractéristique que vous souhaitiez mettre en avant dans la topologie et la taille du réseau, à éviter le chevauchement des noeuds et à effectuer des transformations géométriques.
~~ Images : ??? ~~
D’autres plug-ins de spatialisation sont disponibles via le Centre de plug-ins Gephi.
Pour en savoir plus :
- Site Web Gephi
- [Wiki Gephi] (http://wiki.gephi.org/)
- [Forum Gephi] (http://forum.gephi.org/)
Ces pages sont uniquement disponibles en anglais.
Dernière mise à jour le 13 juin 2011
- Developer Handbook
- Build
- Code Style
- Localization
- Datasets
- Import CSV Data
- Import Dynamic Data
- Scripting Plugin
- Quick Start
- Démarrage rapide (FR)
- Layout
- Spatialisations (FR)
- Statistics
- Import
- Spigot importer with Wizard
- Export
- Generator
- Filter
- Extend Data Laboratory
- Preview renderer
- Add a module panel
- Add a submenu
- Build a plugin without Gephi source code
- Update a plugin
- Code Sharing Strategy
- Graph Streaming