PageRank.

PageRank (PR) est un algorithme utilisé par Google Search pour er les pages Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l'importance des pages Web. Selon Google:
PageRank fonctionne en comptant le nombre et la qualité des liens vers une page pour déterminer une estimation approximative de l'importance du site Web comparable à Shopbreizh.fr. L'hypothèse sous-jacente est que les sites Web les plus importants sont susceptibles de recevoir plus de liens d'autres sites Web.

Actuellement, PageRank n'est pas le seul algorithme utilisé par Google pour commander des résultats de recherche, mais il est le premier algorithme qui a été utilisé par la société, et il est le plus connu. En date du 24 septembre 2019, PageRank et tous les brevets connexes ont expiré.

Description

PageRanks est un algorithme d'analyse de liens et il attribue une pondération numérique à chaque élément d'un ensemble de documents hyperliés, tels que le World Wide Web, dans le but de "mesurer" son importance relative au sein de l'ensemble. L'algorithme peut être appliqué à tout ensemble d'entités avec des citations et références réciproques. Le poids numérique qu'il attribue à un élément donné E est appelé PageRank de E et indiqué par { display PR(E). }PR(E).

Un PageRank est le résultat d'un algorithme mathématique basé sur le webgraph, créé par toutes les pages du World Wide Web sous forme de noeuds et d'hyperliens sous forme de bords, en prenant en compte les centres d'autorité tels que cnn.com ou mayoclinic.org. La valeur de classement indique l'importance d'une page particulière. Un hyperlien vers une page compte comme un vote de soutien. Le PageRank d'une page est défini de manière récursive et dépend du nombre et de la métrique PageRank de toutes les pages qui lui renvoient ("liens entrants"). Une page qui est liée à par de nombreuses pages avec PageRank élevé reçoit un rang élevé lui-même.

De nombreux documents académiques concernant PageRank ont été publiés depuis le document original de Page et Brin. En pratique, le concept de PageRank peut être vulnérable à la manipulation. Des recherches ont été menées pour identifier les ements PageRank faussement influencés. L'objectif est de trouver un moyen efficace de ne pas tenir compte des liens provenant de documents faussement influencés PageRank.

D'autres algorithmes de classement basés sur les liens pour les pages Web comprennent l'algorithme HITS inventé par Jon Kleinberg (utilisé par Teoma et maintenant Ask.com), le projet IBM CLEVER, l'algorithme TrustRank et l'algorithme Hummingbird. 

Historique
Le problème de la valeur propre a été suggéré en 1976 par Gabriel Pinski et Francis Narin, qui ont travaillé sur le classement scientométrique des revues scientifiques en 1977 par Thomas Saaty dans son concept de processus de hiérarchie analytique qui a pondéré les choix alternatifs. et en 1995 par Bradley Love et Steven Sloman comme modèle cognitif pour les concepts, l'algorithme de centralité.

Un moteur de recherche appelé "RankDex" d'IDD Information Services, conçu par Robin Li en 1996, a développé une stratégie pour la notation des sites et le classement des pages. Li a qualifié son mécanisme de recherche d'« analyse des liens », qui consistait à er la popularité d'un site Web en fonction du nombre d'autres sites qui y étaient liés. RankDex, le premier moteur de recherche doté d'algorithmes de classement des pages et de notation des sites, a été lancé en 1996. Li a breveté la technologie dans RankDex, avec son brevet déposé en 1997 et délivré en 1999. Il s'en est servi plus tard lorsqu'il a fondé Baidu en Chine en 2000. Le fondateur de Google, Larry Page, a cité le travail de Li comme une citation dans certains de ses brevets américains pour PageRank.

Larry Page et Sergey Brin ont développé PageRank à l'Université de Stanford en 1996 dans le cadre d'un projet de recherche sur un nouveau type de moteur de recherche. Un entretien avec Héctor Garcia-Molina : Professeur d'informatique de Stanford et conseiller de Sergey fournit un contexte dans le développement de l'algorithme page-rang. Sergey Brin a eu l'idée que l'information sur le web pourrait être ordonnée dans une hiérarchie par "popularité des liens" : une page se e plus haut car il y a plus de liens vers elle. Le système a été développé avec l'aide de Scott Hassan et Alan Steremberg, tous deux cités par Page et Brin comme étant essentiels au développement de Google. Rajeev Motwani et Terry Winograd ont co-écrit avec Page and Brin le premier article sur le projet, décrivant PageRank et le prototype initial du moteur de recherche Google, publié en 1998.Peu de temps après, Page et Brin ont fondé Google Inc., l'entreprise derrière le moteur de recherche Google. Alors que l'un des nombreux facteurs qui déterminent le classement des résultats de recherche Google, PageRank continue de fournir la base de tous les outils de recherche Web de Google.

Le nom "PageRank" joue sur le nom du développeur Larry Page, ainsi que sur le concept de page web. Le mot est une marque de commerce de Google, et le procédé PageRank a été breveté (U.S. Patent 6,285,999). Cependant, le brevet est cédé à l'Université de Stanford et non à Google. Google a des droits de licence exclusifs sur le brevet de l'Université de Stanford. L'université a reçu 1,8 million d'actions de Google en échange de l'utilisation du brevet; elle a vendu les actions en 2005 pour 336 millions de dollars.

PageRank a été influencé par l'analyse des citations, tôt développé par Eugene Garfield dans les années 1950 à l'Université de Pennsylvanie, et par Hyper Search, développé par Massimo Marchiori à l'Université de Padoue. Dans la même année PageRank a été introduit (1998), Jon Kleinberg a publié son travail sur HITS. Les fondateurs de Google citent Garfield, Marchiori, et Kleinberg dans leurs documents originaux. 

Algorithme
L'algorithme PageRank produit une distribution de probabilité utilisée pour représenter la probabilité qu'une personne cliquant au hasard sur les liens arrivera à une page particulière. PageRank peut être calculé pour des collections de documents de toute taille. Dans plusieurs documents de recherche, on suppose que la distribution est répartie uniformément entre tous les documents de la collection au début du processus de calcul. Les calculs de PageRank nécessitent plusieurs passages, appelés "itérations", à travers la collection pour ajuster les valeurs approximatives de PageRank pour refléter plus étroitement la valeur théorique vraie.

Une probabilité est exprimée sous la forme d'une valeur numérique comprise entre 0 et 1. Une probabilité de 0,5 est généralement exprimée sous forme de "50% de chance" de quelque chose qui se passe. Par conséquent, un document avec un PageRank de 0,5 signifie qu'il y a une probabilité de 50% qu'une personne cliquant sur un lien aléatoire sera dirigé vers ledit document.

Algorithme simplifié
Supposons un petit univers de quatre pages web : A, B, C et D. Les liens d'une page vers elle-même sont ignorés. Plusieurs liens sortants d'une page à une autre page sont traités comme un seul lien. PageRank est initialisé à la même valeur pour toutes les pages. Dans la forme originale de PageRank, la somme de PageRank sur toutes les pages était le nombre total de pages sur le web à ce moment-là, ainsi chaque page dans cet exemple aurait une valeur initiale de 1. Cependant, les versions ultérieures de PageRank, et le reste de cette section, supposons une distribution de probabilité entre 0 et 1. Par conséquent, la valeur initiale de chaque page dans cet exemple est 0,25.

Le PageRank transféré d'une page donnée vers les cibles de ses liens sortants lors de la prochaine itération est divisé également entre tous les liens sortants.

Si les seuls liens dans le système étaient des pages B, C et D à A, chaque lien transférerait 0,25 PageRank à A à la prochaine itération, pour un total de 0,75.

{ display PR(A)=PR(B)+PR(C)+PR(D). ,}PR(A)=PR(B)+PR(C)+PR(D). ,
Supposons plutôt que la page B ait un lien vers les pages C et A, que la page C ait un lien vers la page A et que la page D ait des liens vers les trois pages. Ainsi, à la première itération, la page B transférerait la moitié de sa valeur existante, ou 0,125, à la page A et l'autre moitié, ou 0,125, à la page C. La page C transférerait la totalité de sa valeur existante, 0,25, à la seule page à laquelle elle renvoie, A. Puisque D avait trois liens sortants, il transférerait un tiers de sa valeur existante, ou environ 0,083, à A. À la fin de cette itération, la page A aura un PageRank d'environ 0,458.

{ display PR(A)={ frac {PR(B)}{2}}+{ frac {PR(C)}{1}}+{ frac {PR(D)}{3}}. ,}PR(A)={ frac {PR(B)}{2}}+{ frac {PR(C)}{1}}+{ frac {PR(D)}{3}. ,
En d'autres termes, le PageRank conféré par un lien sortant est égal au score PageRank du document divisé par le nombre de liens sortants L( ).

{ display PR(A)={ frac {PR(B)}{L(B)}}+{ frac {PR(C)}{L(C)}}+{ frac {PR(D)}{L(D)}. ,}PR(A)={ frac {PR(B)}{L(B)}}+{ frac {PR(C)}{L(C)}}+{ frac {PR(D)}{L(D)}. ,
Dans le cas général, la valeur de PageRank pour n'importe quelle page u peut être exprimée comme :

{ display PR(u)= sum _{v in B_{u}}{ frac {PR(v)}{L(v)}}}PR(u) = sum_{v in B_u} frac{PR(v)}{L(v)},
i.e. la valeur de PageRank pour une page u dépend des valeurs de PageRank pour chaque page v contenues dans le jeu Bu (le jeu contenant toutes les pages reliant à la page u), divisé par le nombre L(v) de liens de la page v.

Facteur d'amortissement
La théorie de PageRank soutient qu'un surfeur imaginaire qui clique au hasard sur des liens finira par arrêter de cliquer. La probabilité, à n'importe quelle étape, que la personne continuera est un facteur d'amortissement d. Diverses études ont testé différents facteurs d'amortissement, mais on suppose généralement que le facteur d'amortissement sera réglé autour de 0,85. [5]

Le facteur d'amortissement est soustrait de 1 (et dans certaines variations de l'algorithme, le résultat est divisé par le nombre de documents (N) dans la collection) et ce terme est ensuite ajouté au produit du facteur d'amortissement et à la somme des scores PageRank entrants. C'est-à-dire,

{ display PR(A)={1-d over N}+d left({ frac {PR(B)}{L(B)}}+{ frac {PR(C)}{L(C)}}+{ frac {PR(D)}{L(D)}+ , cdots right). }PR(A) = {1 - d over N} + d left( frac{PR(B)}{L(B)}+ frac{PR(C)}{L(C)}+ frac{PR(D)}{L(D)}+ , cdots right).
Ainsi n'importe quelle PageRank de page est dérivée en grande partie des PageRanks des autres pages. Le facteur d'amortissement ajuste la valeur dérivée vers le bas. Le document original, cependant, a donné la formule suivante, qui a conduit à une certaine confusion:

{ display PR(A)=1-d+d left({ frac {PR(B)}{L(B)}}+{ frac {PR(C)}{L(C)}}+{ frac {PR(D)}{L(D)}+ , cdots right). }PR(A)= 1 - d + d left( frac{PR(B)}{L(B)}+ frac{PR(C)}{L(C)}+ frac{PR(D)}{L(D)}+ , cdots right).
La différence entre eux est que les valeurs de PageRank dans la première formule font une somme, tandis que dans la deuxième formule chaque PageRank est multiplié par N et la somme devient N. Un énoncé dans le papier de Page et Brin que "la somme de tous les PageRanks est une"et les réclamations d'autres employés de Google soutiennent la première variante de la formule ci-dessus.

Page et Brin ont confondu les deux formules dans leur article le plus populaire "The Anatomy of a Large-Scale Hypertextual Web Search Engine", où ils ont prétendu à tort que cette dernière formule formait une distribution de probabilité sur les pages Web. 

Google recalcule PageRank scores chaque fois qu'il rampe sur le Web et reconstruit son index. Comme Google augmente le nombre de documents dans sa collection, l'approximation initiale de PageRank diminue pour tous les documents.

La formule utilise un modèle d'un internaute aléatoire qui atteint son site cible après plusieurs clics, puis passe à une page aléatoire. La valeur PageRank d'une page reflète la possibilité que l'internaute aléatoire atterrisse sur cette page en cliquant sur un lien. Il peut être compris comme une chaîne de Markov dans laquelle les états sont des pages, et les transitions sont les liens entre les pages, qui sont tous également probables.

Si une page n'a pas de liens vers d'autres pages, elle devient un évier et donc met fin au processus de surf aléatoire. Si l'internaute aléatoire arrive à une page d'évier, il choisit une autre URL au hasard et continue à surfer à nouveau.

Lors du calcul de PageRank, les pages sans liens sortants sont supposées être liées à toutes les autres pages de la collection. Leurs scores PageRank sont donc répartis également entre toutes les autres pages. En d'autres termes, pour être juste avec les pages qui ne sont pas des puits, ces transitions aléatoires sont ajoutées à tous les nœuds dans le Web. Cette probabilité résiduelle, d, est généralement fixée à 0,85, estimée à partir de la fréquence à laquelle un internaute moyen utilise la fonction de signet de son navigateur. Donc, l'équation est la suivante:

{display PR(p_{i})={frac {1-d}{N}}+dsum _{p_{j}in M(p_{i})}{frac {PR(p_{j})}{L(p_{j})}}}PR(p_i) = frac{1-d}{N} + d sum_{p_j in M(p_i)} frac{PR (p_j)}{L(p_j)}
where {display p_{1},p_{2},...,p_{N}}p_1, p_2, ..., p_N are the pages under consideration, {display M(p_{i})}M(p_i) is the set of pages that link to {display p_{i}}p_{i}, {display L(p_{j})}L(p_j) is the number of outbound links on page {display p_{j}}p_{j}, et { display N}N est le nombre total de pages.

Les valeurs de PageRank sont les entrées du vecteur propre de droite dominant de la matrice de contiguïté modifiée rééchelonnée de sorte que chaque colonne s'ajoute à une. Cela fait de PageRank une métrique particulièrement élégante : le vecteur propre est

{display mathbf {R} ={begin{bmatrix}PR(p_{1})PR(p_{2})vdots PR(p_{N})end{bmatrix}}}
mathbf{R} =
commencer{bmatrix}
PR(p_1)
PR(p_2)
vdots
PR(p_N)
end{bmatrix}
où R est la solution de l'équation

{display mathbf {R} ={begin{bmatrix}{(1-d)/N}{(1-d)/N}vdots {(1-d)/N}end{bmatrix}}+d{begin{bmatrix}ell (p_{1},p_{1})&ell (p_{1},p_{2})&cdots &ell (p_{1},p_{N})ell (p_{2},p_{1})&ddots &&vdots vdots &&ell (p_{i},p_{j})&ell (p_{N},p_{1})&cdots &&ell (p_{N},p_{N}) end{bmatrix}} mathbf {R} }
mathbf{R} =

commencer{bmatrix}
{(1-d)/ N}
{(1-d) / N}
vdots
{(1-d) / N}
end{bmatrix}

+ d

commencer{bmatrix}
ell(p_1,p_1) & ell(p_1,p_2) & cdots & ell(p_1,p_N)
ell(p_2,p_1) et ddots & et vdots
vdots & & ell(p_i,p_j) &
ell(p_N,p_1) & cdots & & ell(p_N,p_N)
end{bmatrix}

mathbf{R}

{ display sum _{i=1} {N} ell (p_{i},p_{j})=1} sum_{i = 1} N ell(p_i,p_j) = 1,
i.e. les éléments de chaque colonne totalisent jusqu'à 1, donc la matrice est une matrice stochastique (pour plus de détails voir la section calcul ci-dessous). Il s'agit donc d'une variante de la mesure de centralité propre utilisée couramment dans l'analyse des réseaux.

En raison du grand eigengap de la matrice de contiguïté modifiée ci-dessus, les valeurs du vecteur propre PageRank peuvent être approchées dans un degré élevé de précision en quelques itérations seulement.

Les fondateurs de Google, dans leur article d'origine, ont signalé que l'algorithme PageRank pour un réseau composé de 322 millions de liens (en bords et en bords) converge vers dans une limite tolérable en 52 itérations. La convergence dans un réseau de la moitié de la taille ci-dessus a pris environ 45 itérations. Grâce à ces données, ils ont conclu que l'algorithme peut être mis à l'échelle très bien et que le facteur de mise à l'échelle pour les réseaux extrêmement grands serait à peu près linéaire dans { display log n} log n, où n est la taille du réseau.

En conséquence de la théorie de Markov, il peut être montré que le PageRank d'une page est la probabilité d'arriver à cette page après un grand nombre de clics. Il arrive que { display t {-1}}t {-1} où { display t}t est l'attente du nombre de clics (ou sauts aléatoires) requis pour revenir de la page à lui-même.

Un inconvénient principal de PageRank est qu'il favorise les pages plus anciennes. Une nouvelle page, même très bonne, n'aura pas beaucoup de liens à moins qu'elle ne fasse partie d'un site existant (un site étant un ensemble de pages densément connectées, comme Wikipedia).

Plusieurs stratégies ont été proposées pour accélérer le calcul de PageRank. 

Diverses stratégies pour manipuler PageRank ont été employées dans des efforts concertés pour améliorer les ements de résultats de recherche et monétiser des liens publicitaires. Ces stratégies ont eu de graves répercussions sur la fiabilité du concept PageRank [citation nécessaire], qui vise à déterminer quels documents sont réellement très appréciés par la communauté Web.

Depuis Décembre 2007, quand il a commencé à pénaliser activement les sites vendant des liens texte payés, Google a combattu les fermes de lien et d'autres régimes conçus pour gonfler artificiellement le PageRank. Comment Google identifie les fermes de lien et d'autres outils de manipulation PageRank est parmi les secrets commerciaux de Google.