Ranking - PageRank

Master 1 Informatique - DataScale | Université Paris-Saclay (2025-2026)

Auteurs : Paria RAHMATPANAH & Emmy MARIE-JOSEPH

---

Projet de calcul du PageRank réalisé dans le cadre du cours de Ranking et Recommandation.

Le projet compare expérimentalement deux méthodes itératives :

• la méthode des puissances ;
• une version descendante de la méthode de Gauss-Seidel.

L’objectif est d’étudier leurs performances sur de grands graphes du Web en utilisant des structures de données creuses ainsi que plusieurs optimisations mémoire et calcul.

---

Fonctionnalités

Le projet permet :

• la lecture de grands graphes du Web ;
• le stockage creux des matrices de transition ;
• la gestion des pages mortes (\textit{dangling nodes}) ;
• l’implémentation de la méthode des puissances ;
• l’implémentation de la méthode de Gauss-Seidel descendante ;
• la génération automatique d’études expérimentales ;
• l’export des résultats au format CSV ;
• la génération de graphiques avec Python.

---

Arborescence du Projet

PROJET_PAGERANK/
├── generated/            # Contient les CSV et les graphiques générés       
├── src/                  # Code source C
│   ├── main.c            # Programme principal
│   ├── graphe.c / .h     # Construction de la structure creuse en mémoire
│   ├── utils.c / .h      # Fonctions d'étude expérimentale, tri, et export CSV
│   └── pagerank_*.c / .h # Implémentations de Puissance et Gauss-Seidel
├── plot_results.py       # Script Python pour tracer les graphiques
├── makefile              # Automatisation de la compilation
├── rapport.pdf
└── rapport.tex

---

Instructions d'utilisation

Etape 1 : Pré-requis et Dépendances

Pour faire tourner le projet complet, vous devez avoir installé un compilateur C, Make, et Python 3.

Pour les graphiques Python : Vous aurez besoin des bibliothèques pandas et matplotlib. Pour les installer, ouvrez un terminal et tapez :

pip install pandas matplotlib

Etape 2 : Configuration du chemin de la matrice

Pour changer la matrice à tester, ouvrez le fichier src/main.c et modifiez la macro située à la ligne 10 :

#define MATRICE_PATH "Matrices/votre_matrice.txt"

Etape 3 : Compilation et Execution

Dans le terminal, à la racine du projet, lancez la commande suivante pour compiler et exécuter le code :

make build

Le programme va afficher le temps d'exécution, le Top 20 des pages, puis générer les fichiers CSV dans le dossier generated/csv.

Etape 4 : Generation des Graphiques

Une fois l'exécution C terminée, générez les courbes de convergence en lançant :

python plot_results.py

Les deux images (courbe_alpha.png et courbe_epsilon.png) seront automatiquement créées et sauvegardées dans le dossier generated/images/.