Graphe capsule
2023-06-21
Une image vaut mille mots.
À mesure que ma capsule Gemini s'agrandit, il m'apparaît nécessaire de garder un œil sur ce que j'y écris, et d'observer le réseau construit d'idées. Devenu presque commun dans le domaine scientifique – ou bien c'est moi qui ai eu un éclair de truand –, il est possible de créer des réseaux de citations entre articles de sorte à pouvoir trouver facilement les articles populaires – c'était sûrement un éclair de truand.
Réseau en graphe
Un réseau en graphe est composé de nœuds N (ou sommets), ou des paires peuvent être liées par des arêtes A. Un graphe G est ainsi défini tel que G = (N,A), pouvant ainsi générer de multiples isomorphes.
Dans ses formes plus complexes, c'est un concept utilisé pour le pathfinding.
Sachant que les arc entre mes billets sont orientés et peuvent être réciproques, le résultat obtenu sera un graphe simple – un même lien n'est pas utilisé plusieurs fois dans un billet[1].
Format de données
De façon arbitraire, j'utilise ici le programme Gephi[2]. Le logiciel est capable de prendre en charge différent formats, dont GEXF que le groupe a développé, par simplicité je m'orienterai une fois de plus vers le CSV.
Données complémentaires
En plus des liens entre documents, des informations complémentaires seraient intéressantes à mettre en évidence à savoir :
- le nom de domaine des documents : Savoir si des documents proviennent d'une même source ;
- le protocole des documents : Comparer le type de documents (Gemini, HTTP, Git, DOI, etc…).
Ces informations ne semblent à priori pas pouvoir être prises en charge par Gephi sous format CSV. Ce n'est que partie remise, les deux informations étant facilement récupérables via regex.
Extraction des données
Dans le fichier attendu par Gephi chaque ligne, représentant un lien, nécessite un identifiant source et un identifiant cible.
Je dois ainsi extraire de chacun de mes fichiers textes les liens, et les apparier en ligne. Pour ce faire, j'utilise `grep`.
Sur Gemini chaque lien est défini par une ligne (^), commençant par les symboles =>, et suivi de l'URL. Le programme `grep` retournant automatiquement la ligne entière `^=>` suffit à la recherche. Et une approche récursive, fouillant dans les fichiers d'un dossier, peut-être utilisée via l'argument `-r`.
Il me suffit ainsi d'appliquer la commande suivante sur mon dossier principal : `grep -r '^=>' NomDeDossier > output.csv`, pour obtenir un fichier où chaque ligne est au format suivant : `AdresseFichier:LigneRésultat`.
./posts/20230621_grapheCapsule.gmi:=> https://gephi.org/ [2] Gephi, Gephi Consortium 2022
Traitement des données
Des transformations sont nécessaires pour dégager les deux colonnes demandées par Gephi à savoir `URLDépart:URLCible`. Chaque URL doit être absolue, plutôt que relative, une étape (certe accessible) que je m'épargne en n'utilisant que des URLs absolues.
- Suppression du marqueur de lien `:=> ` remplacé par une virgule via `sed s/:=> /,/g` ;
- Conservation uniquement du premier membre de chaque ligne, composé des deux URLs, via l'outil `cut -d ' ' -f 1`. Les membres sont séparés par des espaces, seulement le premier « champ » est conservé ;
- Pour raisons techniques la sortie de l'opération précédente est enregistrée sous un nouveau fichier qui remplace ensuite le fichier initial via `mv` ;
- Remplacer `^./` (qui est mon répertoire parent où j'ai un sous-répertoire `/posts/`) vers l'adresse du répertoire parent via `sed -e 's/^\.\//\/lejun\//g'`. Cela modifie uniquement les membres de la première colonne, utilisant des adresses relatives ;
- Préfixer le nom de domaine à mon répertoire via `sed 's/\/lejun\/gemini:\/\/unbon.cafe\/lejun\//g'`.
Un script est disponible pour gagner une dizaine de secondes à réaliser ces étapes manuellement[4]. Le script est a exécuter directement dans le dossier racine de la capsule.
Import Gephi
Une fois sur Gephi, j'entre dans le « Laboratoire de données » où j'importe une feuille de calcul.
Mon fichier utilise la virgule comme séparateur de données, et correspond à une liste d'adjacence (Appariement me paraît plus adéquat m'enfin, de ce que j'en dis…). Comme dit plus haut, tous les liens sont dirigés, ce sont des arcs.
Mise en forme
L'étape de mise en forme est importante pour pouvoir lire ce qui s'apparente autrement à un sac de nœuds – littéralement.
La méthode la plus efficace que j'ai trouvé pour dégrossir le travail est de procéder par un déchevauchement des labels, suivi d'un Yifan Hu. L'algorithme de Fruchterman Reinold donne un résultat particulièrement plaisant sur le plan visuel, sans réellement aider à l'interprétation des données.
Ce faisant j'ai retrouvé un billet qui se baladait seul depuis juin 2022. Suivi d'un petit déchevauchement des labels et on y voit déjà plus clair.
Dans l'onglet Statistiques, de droite, la modularité permet de créer des communautés dans les nœuds. Les couleurs peuvent alors être appliquées via l'onglet Partition de l'Aspect des Nœuds.
Par la suite, il serait intéressant de chercher à affiner les résultats afin de :
- mettre en évidence les liens internes ;
- puis les liens par protocole.
Références
[1] Bases de la théorie des graphes, Algue-Rythme 2016
[2] Gephi, Gephi Consortium 2022
[3] Lien absolu, et relatif, LeJun 2023
Source