PageRank, BookRank et comportement des internautes.

Mes lecteurs les plus fidèles savent déjà tout ou presque du pagerank (voir ici et ici). A quoi sert le PageRank ? A classer les pages d’une manière qui serait cohérente avec le comportement naturel d’un internaute moyen, qu’on appelle le surfeur aléatoire, que j’appelle l’internaute crétin : il parcourt le web en suivant les liens au hasard, sauf dans certains cas où il se téléporte sur une page choisie au hasard au sein de toutes les pages présentes sur le web.

Naturellement, on comprend que cette hypothèse de comportement totalement aléatoire n’a que peu de chance de correspondre au comportement réel de l’internaute. Il reste à comprendre quel peut être ce comportement réel, et à quel point il diffère du modèle proposé par le PageRank pour être capable de proposer un modèle plus réaliste, qui donnera au final un classement plus en adéquation avec la popularité réelle des sites.

Des travaux en ce sens ont été effectué par plusieurs personnes et sont résumés dans les articles suivants :

B. Goncalves, M. Meiss, J. Ramasco, A. Flammini, and F. Menczer. Remembering what we like: Toward an agent-based model of Web traffic. late-breaking result session at WSDM 2009.

M. Meiss, F. Menczer, S. Fortunato, A. Flammini, and A. Vespignani. Ranking Web sites with real user traffic. Proc. 1st Intl. Web Search and Data Mining Conference, 2008 (WSDM 2008 ).

Les travaux effectués sont habiles : ils ont construit un graphe du web avec des poids sur les arcs (les liens entre pages donc) qui correspondent à des données tirées des utilisateurs réels. Grâce aux données obtenues ils ont pu exhiber les caractéristiques fondamentales de ce que je vais appeler l’expérience utilisateur sur le web. L’idée de cette analyse était donc de pouvoir valider le modèle de navigation sous-jacent au PageRank, et on va voir qu’il n’est pas valide.

D’où viennent les données de l’étude ?

De manière très simple, elles viennent du graphe du web (un crawl comme celui de Yahoo ou Altavista fait l’affaire), de plusieurs sources dynamiques (toolbars, graphes de flot de données, logs des serveurs web) et aussi de l’analyse du trafic qui passe sur les gros switchs de plusieurs hubs du web.

Quelles sont les conclusions de l’étude ?

• Moins de la moitié des visites sur des pages web viennent de clicks sur des liens ! Cela veut dire que le modèle du surfeur aléatoire qui visite les pages les unes après les autres en cliquant au hasard est largement biaisé ! Cela veut aussi dire que la moitié du trafic vient de la téléportation !
• 5% du trafic global provient des moteurs de recherche (et oui grosse surprise, non ?). Moi je ne suis pas surpris outre mesure. Attention, cela ne signifie pas que 5% seulement du trafic de tout site vient des moteurs, car l’étude nous apprend aussi que la règle est l’hétérogénéité.
• Je ne résiste pas à vous mettre la figure suivante :

On y voit que sur une année, le mois de mars est celui avec le plus gros volume alors que septembre est un mois pourri. Là je suis plus circonspect, mais bon…

• Au final, si on compare le ranking des pages web en utilisant le PageRank (c’est-à-dire l’algo standard que nous connaissons tous), le pagerank pondéré (PRW – on pondère chaque lien selon son importance) et le classement des pages selon le trafic réel reçu on obtient la courbe suivante :

Plus la courbe est proche de 1 plus les méthodes ont des résultats proches, si le PageRank était efficace alors la courbe en pointillés bleus devrait être près du haut de la figure en permanence… Je vous laisse conclure sur l’efficacité !

Il y a bien sur plein d’autres choses dans les articles mais je ne vais pas en rajouter plus que nécessaire. Je vais juste conclure sur la proposition des auteurs : le Bookrank.

Le Bookrank ?

Il s’agit du même algo que le PageRank, sauf que le comportement du surfeur aléatoire est modifié de la façon suivante :

• A chaque nouvelle visite d’une page, on la rajoute aux bookmarks. La liste des sites bookmarkés est classée par ordre de fréquence de visite.
• A chaque étape, le surfeur va avec une certaine probabilité se téléporter sur une page qu’il a bookmarké. Il choisit dans ses bookmarks selon la fréquence (pour coller à la politique rich-get-richer)
• Sinon (c’est-à-dire si il ne se téléporte pas), il choisit au hasard entre les liens disponibles sur la page qu’il est en train de visiter plus le bouton de retour en arrière pour décider de la prochaine page qu’il va visiter.

Vous l’aurez compris le but est de satisfaire les hypothèses que nous avons vu plus haut (notamment les 50% de chance de téléportation). Je spoile l’article de 2009, mais le résultat est un classement beaucoup plus proche de ce qui est attendu dans la réalité, malgré tout certains paramètres ne sont pas encore bons, mais on s’approche bien mieux qu’avant du graal…