Annexe B — Petite étude du PageRank sur le site de l’INRIA

À partir d’une capture du graphe du site http://www.inria.fr, nous avons appliqué un algorithme de type PageRank pour voir quelles étaient les pages qui obtenaient le plus fort classement. Plusieurs observations intéressantes sont apparues :

• La justification de l’ablation, dans le calcul du PageRank, des feuilles du graphes (entendre par feuille noeud de degré sortant nul).

• Il est apparu vital d’enlever les liens d’une page vers elle-même, car cela provoque un phénomène de résonance. Sur le graphe de l’INRIA, avant de procéder à cette modification, le PageRank était largement dominé par

  qui cumule le rôle de page autoréférencée et de racine d’un puits.

• Le choix de l’importance du « click aléatoire » s’avère primordial : s’il est trop petit, les puits ou quasi-puits vont absorber tout le PageRank. S’il est trop grand, l’aspect itératif du PageRank va disparaître, et le classement sera à peu près un classement selon le degré entrant. Dans le cas de l’INRIA, un click aléatoire de à chaque itération paraît un bon compromis.

Résultats Il semble assez intéressant d’analyser les dix premières URLs renvoyées par notre algorithme de PageRank (voir Tableau 2.1). On constate que, tout en étant bien sûr corrélé au classement des degrés entrant, il s’en démarque significativement (comparer le Tableau 2.1 et le Tableau 2.2).

Au niveau de la pertinence, les pages renvoyées par notre PageRank apparaissent bien trouvées dans leur ensemble (page d’accueil en première place, pages de type « index » ou « plan »), à l’exception notable de deux pages :

Après vérification, et comme on pouvait s’y attendre, ces deux pages s’avèrent être les deux principaux noeuds d’un quasi-puits, à savoir rapportsactivite/RA94/. Ces deux pages, présentant à la fois un fort degré entrant et étant dans un quasi-puits, paraissent très difficiles à écarter simplement à l’aide d’un PageRank local.

Comparaison avec Google Google attribue un classement de 9/10 à la page d’accueil de l’INRIA et de 8/10 aux autres dix premières pages du PageRank local, à l’exception de

qui se voient attribuer la note de 6/10. Deux principales remarques :

• Les deux pages RA94 avaient un PageRank local quasi-égal aux autres pages, exception faite de la page d’accueil. Le PageRank global de Google a réussi à les isoler. On peut avancer comme explication l’existence probable de nombreux liens de pages extérieures vers les pages de type « index », alors qu’il est fort probable qu’il existe très peu de pages extérieures pointant vers RA94.

• La note de 6/10 attribuée à

  reste élevée, certainement plus élevée que ce que l’on voudrait. Beaucoup de pages d’accueil de sites considérés comme plus intéressants n’ont pas cette note.