septembre 26, 2022
L'algorithme PageRank de Google, expliqué – Search Engine Watch

L'algorithme PageRank de Google, expliqué – Search Engine Watch

Plus tôt dans la journée, Dixon Jones de Majestic a partagé sur Twitter une explication complète et digeste du fonctionnement réel du PageRank.

Je lui ai donné une montre moi-même, et j'ai pensé que c'était le bon moment pour revisiter ce calcul sauvage qui a fait une grosse brèche sur le monde au cours des 20 dernières années.

En remarque, nous savons à partir de 2017 que si le PageRank était supprimé de la barre d'outils en 2016, il constitue toujours une partie importante de l'algorithme de classement global, et vaut donc la peine d'être compris.

Jones commence par la formule simple – ou du moins, directe – formule.

Pour ceux qui n'adorent pas les maths, ou qui ont peut-être oublié quelques termes techniques depuis le dernier cours de calcul, cette formule serait lue à voix haute comme ceci :

« Le PageRank d'une page dans cette itération est égal à 1 moins un facteur d'amortissement, plus, pour chaque lien dans la page (à l'exception des liens vers elle-même), ajoutez le classement de la page de cette page divisé par le nombre de liens sortants sur le page et réduit b y le facteur d'amortissement.”

Retour à l'original Google papier

À ce stade, Jones avance dans la vidéo à une version plus simple et toujours utile du calcul. Il sort Excel, un visuel simple à 5 nœuds, et trace l'algorithme de classement sur 15 itérations. Super trucs.

Personnellement, je voulais un peu plus de maths, alors je suis retourné et j'ai lu la version intégrale de « L'anatomie d'un moteur de recherche Web hypertextuel à grande échelle” (une première étape naturelle). C'était l'article écrit par Larry Page et Sergey Brin en 1997. Aka l'article dans lequel ils ont présenté Google, publié au département d'informatique de Stanford. (Oui, c'est long et je vais travailler un peu tard ce soir. Tout en s'amusant bien !)

papier, nous présentons Google, un prototype de moteur de recherche à grande échelle qui fait un usage intensif de la structure présente en hypertexte.”

Décontracté, selon leur style général et continu.

En plus Fait amusant, notre propre Search Engine Watch a été cité dans ce premier article de Google! Par nul autre que Page et Brin eux-mêmes, déclarant qu'il y avait déjà 100 millions de documents Web en novembre 1997.

Quoi qu'il en soit, reprenez le travail.

Voici comment le calcul du PageRank a été défini à l'origine:

«La littérature universitaire sur les citations a été appliquée au Web, en grande partie en comptant les citations ou backlinks vers une page donnée. Cela donne une approximation de l'importance ou de la qualité d'une page. PageRank étend cette idée en ne comptant pas les liens de toutes les pages de manière égale et en normalisant par le nombre de liens sur une page. Le PageRank est défini comme suit:

Nous supposons que la page A a des pages T1…Tn qui pointent vers elle (c'est-à-dire qu'il s'agit de citations). Le paramètre d est un facteur d'amortissement qui peut être réglé entre 0 et 1. On règle généralement d à 0,85. Il y a plus de détails sur d dans la section suivante. Aussi C(A) est défini comme le nombre de liens sortant de la page A. Le PageRank d'une page A est donné comme suit :

PR(A) = (1-d) d (PR(T1)/C(T1) … PR(Tn )/C(Tn))

Notez que les PageRanks forment une distribution de probabilité sur les pages Web, donc la somme des PageRanks de toutes les pages Web sera de un.

PageRank ou PR(A)

peut être calculé en utilisant un algorithme itératif simple, et correspond au vecteur propre principal de la matrice de liens normalisée du web. En outre, un PageRank pour 26 millions de pages Web peut être calculé en quelques heures sur un poste de travail de taille moyenne. Il y a beaucoup d'autres détails qui dépassent le cadre de cet article.

Soyez avec nous! Voici à nouveau notre formule:

PR(A) = (1-d) d (PR(T1)/C(T1) … PR( Tn)/C(Tn))

Notez que c'est le même que l'image ci-dessus, sauf que la photo « simplifie » la deuxième partie de l'équation en substituant un sigma majuscule (∑), qui est le symbole d'une sommation mathématique, c'est-à-dire faites cette formule pour toutes les pages 1 à n puis additionnez-les.

Donc, pour calculer le PageRank de la page A donnée, nous prenons d'abord 1 moins le facteur d'amortissement (d). D est généralement défini sur 0,85, comme on le voit dans leur document d'origine.

Nous prenons ensuite les PageRanks de toutes les pages qui pointez vers et à partir de la page A, additionnez-les et multipliez par le facteur d'amortissement de 0,85.

Pas si mal, non? Plus facile à dire qu'à faire.

PageRank est un algorithme itératif

Peut-être que vos yeux étaient vitreux sur cette partie, mais Brin et Sergey ont en fait utilisé le mot « vecteur propre » dans leur définition. J'ai dû chercher.

Apparemment, les vecteurs propres jouent un rôle de premier plan dans les équations différentielles. Le préfixe « eigen » vient de l'allemand pour « propre » ou « caractéristique ». Il existe également des valeurs propres et des équations propres.

Comme

Rogers a souligné out dans son article classique sur le PageRank, le plus gros point à retenir pour nous à propos de la pièce de vecteur propre est qu'il s'agit d'un type de calcul qui vous permet de travailler avec plusieurs pièces mobiles. « On peut aller de l'avant et calculer le PageRank d'une page sans connaître la valeur finale du PR des autres pages . Cela semble étrange mais, fondamentalement, chaque fois que nous effectuons le calcul, nous obtenons une estimation plus précise de la valeur finale. Donc, tout ce que nous avons à faire est de nous souvenir de chaque valeur que nous calculons et de répéter les calculs de nombreuses fois jusqu'à ce que les nombres cessent de changer beaucoup. L'importance du vecteur propre est que PageRank est un algorithme itératif . Plus vous répétez le calcul, plus vous vous rapprochez des chiffres les plus précis.

PageRank visualisé dans Excel

Dans sa vidéo, Jones passe à peu près directement à la partie amusante, qui c'est pourquoi il est si efficace en seulement 18 minutes. Il montre comment le PageRank est calculé avec l'exemple de 5 sites Web qui sont liés les uns aux autres.

Il le ramène ensuite aux calculs dans excel :

Et montre comment vous itéreriez en prenant la rangée de nombres en bas et en répétant le calcul.

En faisant cela, les nombres commencent finalement à se stabiliser (c'était après seulement 15 itérations):

Ou comme certains pourraient sous-titrer cette photo, « Vecteurs propres dans le Sauvage. »

Autres observations intéressantes soulevées par Jones:

  • Nombre de liens (juste total nombres) sont une mauvaise métrique. Nous devons nous soucier davantage du classement de chaque page.
  • C'est le classement au niveau page qui compte, pas l'autorité de domaine . PageRank n'a jamais regardé que des pages individuelles.

  • La majorité des pages n'ont pratiquement aucun rang. Dans son exemple, les 3 premiers sur 10 représentaient 75 à 80 % du classement total.
  • Enfin, voici le tweet original qui m'a fait plonger dans ce long terrier de lapin captivant. J'espère que vous apprécierez tous la même chose !

    Voici. Comment PageRank fonctionne VRAIMENT https:// t.co/OO7J0KChsr cc @RyanJones et @JosephKlok et toute autre personne disposée à retweeter.

    — Dixon (@Dixon_Jones) 25 octobre 2018

    Laisser un commentaire

    Votre adresse e-mail ne sera pas publiée.