Démos
Graphipédia
Wikipedia contient une base de donnée de grande taille, construite intégralement à la main, ce qui offre un potentiel de découverte élevé, sans redondance. La base étant librement accessible sur les serveurs FTP de l'encyclopédie, il y a des choses intéressantes à faire avec.
Quelques statistiques :
- Version Française (FR) de Wikipedia (08/06/2018) :
- 3.5 millions de pages environ, dont 1.5 million de redirections.
- 135 millions de liens.
- Version Anglaise (EN) de Wikipedia (fin 2018) :
- 14 millions de pages environ, dont 8.3 millions de redirections.
- 463 millions de liens.
Visualisation et forme de Wikipédia
Il est possible d'envisager une représentation visuelle, en 2D ou en 3D d'un graphe, grâce à une technique de relaxation physique permettant d disposer les points de manière équilibrée dans l'espace : le graphe peut être considéré comme une simulation de NBody avec des noeuds qui se repoussent et leurs liens qui les rapprochent de force. Lien sur le sujet
La relaxation a été accélérée via un solveur CUDA. la visualisation se fait ensuite en lignes OpenGL. La complexité du graphe rendant l'ensemble illisible, il a fallut donc passer en transparence additive, pour dissimuler les liens individuels et mettre en valeur les zones de fortes densité. Voici les rendus finaux d'un sous-ensemble de quelques dizaines de milliers de pages :
Certaines parties du motif sont très étranges et possèdent une apparence quasi-organique.
Chacun des point visible sur cette image, vers lesquels convergent les mince fils qui traversent l'écran, est un fragment de connaissance humaine, et qu'aucune de ces ligne, traduisant un lien logique, n'a été placée au hasard.
La forme du graphe est assez chaotique, la plupart des pages étant facilement reliées à n'importe-quelle autre. Avec juste 300000 pages (soit à peine plus qu'un dixième de la version FR), l'image se résume à une gigantesque forme sphérique peu exploitable, et le temps de relaxation, même accéléré par GPU, devient très long.
Questions intéressantes
Le principe de base de Wikipedia repose sur les liens hypertextes, lesquels amènent à un profusion de pages de toutes tailles comportant un nombre très varié de liens.
Compte tenu de la partie précédente, on peut donc se demander quelles sont les pages qui pointent le plus d'autres pages, quelles pages sont les plus pointées par les autres, ou tout simplement quelle est la page la plus longue de chaque version du site.
Pour cela, il faut faire un peu d'analyse de données. Après l'import des bases SQL particulièrement colossales issues du backup, quelques requêtes amènent aux résultats suivants :
Pages les plus longues de Wikipedia
- Wikipedia FR :
- Wikipedia EN :
Pages les plus pointées par d'autres
- Wikipedia FR :
- Wikipedia EN :
Pages pointant le plus d'autres pages
Ces pages se résument souvent à des kilomètres de liens et peu de descriptions.
- Wikipedia FR :
- Wikipedia EN :
Recherche de chemin
Un jeu populaire sur internet consiste à trouver le chemin le plus court entre une certaine page de Wikipedia et une autre choisie au hasard. Le jeu est souvent rendu plus difficile lorsqu'il est interdit de passer par la page de la Seconde Guerre mondiale.
Bien sûr, en disposant des bonnes données, cette tâche est totalement automatisable et en tant que graphe orienté, non connexe et multipôlaire, Wikipedia est le terrain de test idéal d'un système de recherche de chemin.
L'algorithme utilisé pour la recherche de chemin est Breadth-first. La plus grosse limitation en performances est la bande passante mémoire. Breadth-first ne fait usage d'aucun calcul mathématique lourd, la seule logique se résumant à la comparaison de valeurs (pour trouver l'arrivée).
La lecture et l'écriture sont les parties les plus intensives de l'algorithme, et la version tronquée de wikipedia, avec 65536 pages permettant l'usage d'identifiants 16 bits pour les pages, est pratiquement deux fois plus rapide que la version avec identifiants 32 bits, avec 4000 chemins aléatoire calculés par seconde en moyenne sur de la mémoire DDR3.
Le plus long des plus courts chemin
L'étape suivante consiste à trouver le plus long des plus courts chemins au sein de ce graphe géant. La recherche exhaustive ne suffit pas, il faut trouver une autre solution.
Copyright © Pierre Geissler, 2019 - Tous droits réservés