Algorithmes PageRank et HITS

PageRank et HITS sont des algorithmes d'analyse de liens qui estiment l'importance ou l'autorité des pages web à partir de la structure du graphe hyperlien plutôt que du seul contenu de la page.

Definition

PageRank attribue à chaque page un score d'importance indépendant de la requête, égal à sa probabilité stationnaire sous l'hypothèse d'un surfeur aléatoire qui suit les liens sortants avec une probabilité d'amortissement et se téléporte autrement, tandis que HITS calcule, pour un sous-graphe dépendant de la requête, des scores d'autorité pour les pages au contenu précieux et des scores de hub pour les pages qui renvoient à de bonnes autorités, chacun renforçant l'autre.

Scope

Ce sujet couvre les deux algorithmes fondamentaux d'analyse de liens : PageRank, une mesure d'importance de page indépendante de la requête basée sur un modèle de surfeur aléatoire avec téléportation, et HITS, un schéma dépendant de la requête qui calcule des scores de hub et d'autorité se renforçant mutuellement. Il aborde les formulations sous-jacentes de marche aléatoire et de vecteur propre, le rôle de l'amortissement et de la téléportation, la convergence, et les variantes sensibles au sujet. Il exclut la manière dont ces scores sont combinés avec des caractéristiques textuelles pour un classement final, ce qui relève du classement de recherche web.

Core questions

• Comment le modèle du surfeur aléatoire définit-il PageRank comme une distribution stationnaire ?
• Pourquoi un facteur d'amortissement ou de téléportation est-il nécessaire pour que PageRank soit bien défini ?
• Comment les scores de hub et d'autorité dans HITS se renforcent-ils mutuellement ?
• Comment ces scores sont-ils calculés de manière itérative, et quand convergent-ils ?
• En quoi PageRank et HITS diffèrent-ils en étant indépendants de la requête ou dépendants de la requête ?

Key concepts

• PageRank
• modèle du surfeur aléatoire
• facteur d'amortissement et téléportation
• distribution stationnaire / vecteur propre principal
• HITS
• hubs et autorités
• notation indépendante de la requête vs. dépendante de la requête
• itération de puissance et convergence

Key theories

Modèle du surfeur aléatoire de PageRank

La modélisation d'un surfeur qui suit les liens avec une probabilité égale à un facteur d'amortissement et saute autrement vers une page aléatoire produit une chaîne de Markov dont la distribution stationnaire unique attribue des scores aux pages en fonction de leur visitation à long terme, fournissant ainsi une mesure d'importance stable et indépendante de la requête.

Hubs et autorités HITS

Au sein d'un sous-graphe ciblé par une requête, HITS attribue à chaque page un score d'autorité proportionnel aux scores de hub des pages qui y renvoient et un score de hub proportionnel aux scores d'autorité des pages vers lesquelles elle renvoie, calculés en itérant ces relations mutuellement renforçantes jusqu'à convergence.

Clinical relevance

PageRank a été essentiel à l'essor de la recherche web à grande échelle et demeure un point de référence conceptuel pour l'importance et l'autorité sur les graphes. Les concepts d'analyse de liens se généralisent au-delà du web aux réseaux de citations, à l'influence des réseaux sociaux, à la détection de fraudes et à la recommandation, partout où des liens de type « approbation » véhiculent de l'information.

History

En 1998 et 1999, deux propositions quasi simultanées ont démontré que les hyperliens encodent l'autorité : HITS de Kleinberg et PageRank de Page et Brin. Les scores de PageRank, indépendants de la requête et calculés globalement, se sont avérés bien adaptés au service à l'échelle du web et ont sous-tendu un moteur de recherche de premier plan, tandis que HITS a influencé la distillation de sujets et la recherche ultérieure sur le classement de graphes.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

Quelle est la différence entre PageRank et HITS ?

PageRank calcule à l'avance un score d'importance unique et indépendant de la requête pour chaque page à partir du graphe web entier, tandis que HITS calcule des scores de hub et d'autorité dépendants de la requête sur un petit sous-graphe construit autour de la requête au moment de la récupération. PageRank s'adapte plus facilement au service web.

Pourquoi PageRank a-t-il besoin d'un facteur d'amortissement ?

Sans lui, le surfeur aléatoire pourrait se retrouver piégé dans des pages sans liens sortants ou dans des cycles, et la distribution stationnaire pourrait ne pas être unique ou bien définie. La probabilité d'amortissement (téléportation) permet au surfeur de sauter occasionnellement vers une page aléatoire, garantissant un score unique et bien défini.