Comment amplifier le PageRank (1/3)

Comment amplifier le PageRank (1/3)

Le pagerank, qui permet de quantifier la popularité d'une page web, est au coeur d'un moteur de recherche moderne comme Google. Quantité algorithmiquement simple à définir, le pagerank devient complexe à calculer du fait même de la taille du web. Par ailleurs, les enjeux économiques liés aux sites web font qu'une large
communauté de personnes essaye de le manipuler.

Il y a maintenant presque un an, nous avions écrit (nous = Thomas et moi-même) un chapitre sur la notion de PageRank pour le livre "Informatique Mathématique une photographie en 2014" (je précise que je ne touche rien sur les ventes). Nous avons choisi de faire un mini cycle de billets à partir de ce chapitre sur le blog. Vous pourrez donc voir les choses suivantes :

Principe d’un moteur de recherche et taxonomie de la triche
L'intuition derrière le PageRank
Comment amplifier le PageRank (1/3) (ce billet)
Comment amplifier le PageRank (2/3)
Comment amplifier le PageRank (3/3)

 Disclaimer pour les lecteurs qui ne sont que dans le SEO opérationnel, sans un background costaud en maths/info théorique, ce billet est très probablement totalement incompréhensible, c'est normal, ne vous inquiétez pas.

Amplification du pagerank ?

Puisque la popularité sur le web dépend d'un classement obtenu via un algorithme précis, il n'est pas surprenant que certaines personnes aient réfléchi à des méthodes locales pour manipuler cet algorithme (sans blague ? c'est à cause de vous tout ça mes chers lecteurs !). L'objectif est alors de réussir à maximiser le score de popularité d'une ou plusieurs pages.

Nous allons maintenant nous intéresser à trois méthodes qui permettent de maximiser le pagerank d'une ou plusieurs pages. La première consiste à mettre en place une structure de liens spécifique au sein d'un unique site, en vue de maximiser le pagerank d'une seule page. La deuxième donne la stratégie de création de liens optimale pour la maximisation du pagerank d'une page seule. Enfin, la troisième présente la stratégie de création de liens optimale sur un ensemble de pages pour maximiser la somme des pagerank de ces pages.

Structure optimale pour amplifier le pagerank d'une page

Bianchini et al. ont étudié en profondeur le PageRank et ses mécanismes internes (voir l'article [1]). Cette étude leur a permis de mettre en évidence la structure optimale qui permet de maximiser la valeur du pagerank d'une page. Avant de dévoiler cette structure optimale, nous allons introduire certains concepts importants. Les auteurs de [1] définissent une communauté C comme étant n'importe quel sous-ensemble de pages du web. Ils notent G_C le graphe associé. Ils associent également à toute communauté C son énergie xi_C = sum_{p in C} pi_i. Il s'agit de la somme des pagerank des pages qui la composent. Soit overline{C} = V setminus C, in(C) est l'ensemble des pages de overline{C} avec au moins un lien vers une page de C et out(C) est l'ensemble des pages de C faisant un lien vers overline{C}. Enfin, dp(C) est l'ensemble des pages de C qui n'ont aucun lien sortant.

Théorème
Etant donné une communauté C, soit f_p la fraction des liens de chaque page p qui pointent vers des pages de C par rapport au nombre total de liens sortants de p. Soit xi_C^{in}, xi_C^{out} et xi_C^{dp} définis de la manière suivante :

xi_C^{in} = frac{c}{1-c}sum_{i in in(C)}f_ipi_i,quad xi_C^{out} = frac{c}{1-c}sum_{i in out(C)}(1 - f_i)pi_i,quad xi_C^{dp} = frac{c}{1-c}sum_{i in dp(C)}pi_i .

Le pagerank xi_C de la communauté C satisfait alors

xi_C = |C| - xi_C^{dp} + xi_C^{in} - xi_C^{out}

Preuve
Chers lecteurs, n'ayez pas peur, je ne vais pas vous infliger cette longue preuve calculatoire que vous trouverez dans le chapitre de livre ou dans l'article [1] si vous le souhaitez vraiment (mais le souhaitez vous ?).

A l'aide de ce résultat, Bianchini et al. ont pu exhiber la structure d'une communauté optimale pour la maximisation du pagerank de ses membres, mais aussi pour la maximisation d'une page en particulier.
Ces structures optimales sont présentées dans la figure suivante, qui différencie le cas où l'on peut faire un lien "bouclant" de celui où cela n'est pas possible. Notez que l'utilisation d'une page de boost (si vous êtes venus à la masterclass moteurs, vous devez bien vous en rappeler) permet de faire la même chose que la boucle.
Plus le nombre de pages composant ces communautés est important, plus le pagerank de la page 1 sera élevé. La valeur exacte de pi_1 est
précisé par le théorème qui se trouve après la figure.

biancThéorème
Soit pi_1^{(a)} et pi_1^{(b)} le pagerank de la page 1 dans la figure. Si l'on considère que ces communautés sont composées de N pages, on obtient :

pi_1^{(a)} =   1 + (N - 1) c
pi_1^{(b)} = frac{1 + (N-1) c}{c + 1}

La preuve de ce théorème est encore une fois omise.

Ces structures sont optimales lorsque l'on est capable de les mettre en place. Mais elles sont lourdes et facilement repérables par les principaux moteurs de recherches, Google en tête. Dès lors il est important de savoir ce qui peut être fait pour augmenter le pagerank d'une ou plusieurs pages cibles sans pour autant en créer des milliers d'autres.  Il est par exemple intéressant de partir du principe que l'on ne peut que manipuler la topologie du graphe du web autour des pages qui nous intéresse, sans jamais rajouter ou enlever de pages supplémentaires. Dans un tel contexte, le propriétaire d'une page web peut manipuler les liens sortants de ses pages. Il n'a en revanche aucun moyen de travailler les liens provenant de l'extérieur et dirigés vers ses pages.

Au prochain épisode, on verra un des résultats les plus techniques du domaine, qui a pourtant un impact proche de zéro pour le SEO opérationnel, car sa conclusion est un bel enfonçage de porte ouverte. Dis comme ça, ça ne vous fait pas très envie, n'est-ce pas ?

PS : Vous n'avez pas tout bien compris aux formules ? Suivez le lien, on vous dira tout.

[1] Bianchini, M., Gori, M., & Scarselli, F. (2005). Inside pagerank. ACM Transactions on Internet Technology (TOIT), 5(1), 92-128.

Comments ( 7 )

  • Petite question : la boucle de la page 1 sur la figure ci-dessus, cela représente un lien sur lui même ?

  • Oui, il s’agit bien d’un lien de la page vers elle-même. Il faut cependant noter que cette structure serait sans doute inopérante telle quelle au niveau d’un moteur comme Google, à cause de ce lien justement. La bonne pratique est de faire un lien circulaire avec une page externe, que l’on appelle une page de boost.

  • Pingback:Comment amplifier le PageRank (2/3) | Frères Peyronnet

  • Pingback:Les formules c'est bien. Les comprendre, c'est mieux ?! | Frères Peyronnet

  • Mathieu

    Bonjour.
    Pour moi, la transposition dans le réel des objets manipulés et les conclusions tirées sont claires, mais il me manque un détail pour comprendre/lire les théorèmes eux mêmes:
    que désigne le (petit) c qui apparait comme facteur un peu partout (par exemple dans le facteur c/(1-c) dans la définition des 3 pagerank de communauté du théorème 1) ?
    Est ce que c=|C| ?

  • Mathieu

    Mon commentaire précédent n’a plus lieu d’être, j’ai enfin compris que c’était le damping factor du PR. 😉
    Il serait peut être bon de le préciser, mais je note que ça doit être tellement évident pour tous les familiers des équations sur le PR que même dans [1] où ce facteur d’atténuation est noté d, on ne rappelle même pas ce que c’est. 😀

  • Oui, c’est bien la constante de téléportation / damping factor. Dans le papier de Larry Page sur le PR, elle vaut 0,85. Mais pour la preuve, la valeur n’est pas importante.