Big Data - PageRank : Analyse et Personnalisation d'un Graphe Orienté
15 déc. 2024
Mise en œuvre l'algorithme PageRank pour analyser un graphe orienté à partir de données réelles issues du projet Wikispeedia. En utilisant la méthode de la puissance, les expérimentations ont permis d’étudier l’influence des paramètres clés, comme le facteur d’amortissement, et d'explorer des variantes, notamment un PageRank personnalisé pour cibler des nœuds spécifiques du graphe.
Implémenter et analyser l’algorithme PageRank, développé initialement pour évaluer l’importance relative des nœuds dans un graphe, en modélisant un processus de navigation aléatoire. Voici les étapes clés du projet :
Données utilisées :
Les données proviennent du projet Wikispeedia (SNAP), qui capture les parcours des utilisateurs entre articles Wikipédia via des liens hypertextes. Ces données ont été nettoyées et transformées en un graphe orienté.
Construction de la matrice de transition :
Les transitions entre pages sont comptées pour créer une matrice stochastique représentant les probabilités de passage entre nœuds. Les nœuds sans liens sortants sont gérés via une distribution uniforme.
Calcul du PageRank :
La méthode de la puissance est utilisée pour obtenir le vecteur PageRank. Les paramètres étudiés incluent :
Le facteur d’amortissement (β), influençant l’équilibre entre la structure du graphe et la téléportation aléatoire.
Le critère de convergence (ε), qui détermine la précision des calculs.
Expérimentations et analyses :
Les résultats montrent que β = 0.85 est un compromis optimal pour refléter à la fois la connectivité et les transitions aléatoires. Des valeurs plus faibles favorisent une répartition uniforme des scores, tandis que des valeurs élevées amplifient les liens dans le graphe, augmentant le temps de calcul.
Un PageRank personnalisé a été implémenté, permettant de prioriser des nœuds spécifiques en modifiant les vecteurs de personnalisation et initiaux. Cela s'est révélé particulièrement utile pour orienter les analyses vers des priorités spécifiques.
Ce projet illustre les forces et les limites de l’algorithme PageRank, tout en explorant ses variations pour répondre à des besoins analytiques spécifiques. Des perspectives futures incluent l’application sur des graphes complexes, l’intégration d’approches d’apprentissage automatique, et le développement d’outils de visualisation interactifs.