Comment amplifier le pagerank (3/3)

Comment amplifier le pagerank (3/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)
Comment amplifier le PageRank (2/3)
Comment amplifier le PageRank (3/3) (ce billet)

 Disclaimer pour les lecteurs qui sont 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.

Dans ce dernier billet sur le sujet (enfin pour la partie technique), je vais vous parler d'une méthode pour pousser la popularité d'un site. C'est à dire pour que la somme des pagerank soit maximale. N'ayez crainte, très prochainement Guillaume va vous faire un billet pour vous expliquer ce qu'il faut retenir intuitivement de ce qui a été dit dans ces billets compliqués.

Structure de lien optimale pour une communauté C

De Kerchove et al.  se sont appuyés sur les travaux d'Avrachenkov et Litvak [2] pour obtenir une généralisation à un ensemble de pages.  Comme dans les travaux précédents, ils vont partir du principe qu'il n'est pas possible de générer des pages à volonté. Ainsi, un certain nombre d'hypothèses "raisonnables" vont être demandées afin de fournir une structure optimale pour la somme des pagerank d'un ensemble de pages prédéterminées. La principale hypothèse, très naturelle, est le fait que chaque page doit avoir un accès au reste du web. Les trois résultats principaux de De Kerchove et ses collègues sont rassemblés dans les théorèmes ci-dessous.

Auparavant, il faut encore une fois poser une série de définitions qui simplifieront la compréhension des raisonnements pas la suite. Pour toute communauté C, on définit les ensembles suivants :

  • E_C = {(i, j) in E| i,j \in C}, représente l'ensemble des liens internes à C.
  • E_{out(C)} = {(i, j) in E| i \in C, j in overline{C}}, représente l'ensemble des liens sortants de C.
  • E_{in(C)} = {(i, j) in E| j in C, i in overline{C}}, représente l'ensemble des liens entrants de C.
  • E_{overline{C}} = {(i, j) in E| i,j in overline{C}}, représente l'ensemble des liens externes à C.

On note Z_C = Ze_{C}. L'interprétation du vecteur Z_C découle naturellement de celle de la matrice Z. Il représente en effet le nombre moyen de visites faites à la communauté C avant téléportation, en prenant chaque noeud du graphe comme point de départ.

 

Théorème
Soient E_{mathcal{C}}, E_{mathrm{in}(mathcal{C})} et E_{overline{mathcal{C}}} donnés. En supposant que le sous-graphe G_{mathcal{C}} soit fortement connexe et E_{mathcal{C}} ne emptyset, la structure optimale pour E_{mathrm{out}(mathcal{C})} est constituée d'un seul lien sortant vers une page n'appartenant pas à l'ensemble mathcal{C}.

 

Théorème
Soient E_{mathrm{out}(mathcal{C})}, E_{mathrm{in}(mathcal{C})} et E_{overline{mathcal{C}}} donnés. En supposant qu'il n'y ait qu'un seul noeud de mathcal{C} faisant un lien vers l'extérieur, la structure optimale pour E_{mathcal{C}} consiste en une chaîne aboutissant au noeud avec le lien sortant, et telle que chaque noeud possède des liens vers tous les noeuds le précédant le long de cette chaîne.

 

Les deux théorèmes ci-dessus peuvent être combinés pour obtenir la structure optimale sur les liens, présentée dans la figure visible plus loin. Il s'agit d'un exemple pour un ensemble C de 5 pages. Cette structure permet d'obtenir le pagerank maximal pour l'ensemble C, mais elle n'est pas très réaliste en terme de schéma de navigation interne pour un site web.

Théorème
Soient E_{mathrm{in}(mathcal{C})} et E_{overline{mathcal{C}}} donnés. Alors la structure de liens optimale consiste pour E_mathcal{C} en une chaîne avec tous les liens arrières possibles et pour E_{mathrm{out}(mathcal{C})} en un unique lien sortant depuis l'extrémité de la chaîne.

 

Les preuves de ces trois théorèmes sont une fois de plus omises et le lecteur intéressé pourra consulter l'article [1] pour plus de détails.

Nous allons maintenant nous intéresser à plusieurs résultats intermédiaires permettant d'obtenir une intuition sur les résultats contenus dans les théorèmes ci-dessus.

 

deker

Structure optimale pour maximiser le pagerank d'un ensemble de 5 pages (noeuds gris)

De Kerchove et al. ont regardé l'effet d'une modification des liens sortants d'une page i in V sur le pagerank d'un ensemble de pages C in V. Pour cela, ils comparent deux graphes G = (V, E) et tilde{G} = (V, tilde{E}) sur le même ensemble de pages. Dans la suite tout élément faisant référence au graphe tilde{G} sera écrit avec un tilde. tilde{P} représente sa matrice de transition, tilde{pi} son vecteur de PageRank, tilde{d}_i = |{ j | (i, j) in tilde{E}}| le degré sortant du noeud i dans tilde{G} et j tilde{leftarrow} i veut dire qu'il existe un lien de i vers j dans tilde{G}.

Supposons que ces deux graphes diffèrent uniquement sur un lien dont l'origine est la page i, c-a-d forall k ne i, quad {j | (k, j) in E} = {j | (k, j) in tilde{E}}. Leurs matrices de transitions P et tilde{P} sont donc reliées par une correction de rang 1. Le vecteur delta est défini de la manière suivante :

delta = sum_{j tilde{leftarrow} i} frac{e_j}{tilde{d}_i} - sum_{j leftarrow i} frac{e_j}{d_i},

et donne la correction à apporter à la matrice P pour obtenir tilde{P}.

 

Théorème [PageRank et nombre moyen de visites avant téléportation]
Soient deux graphes G = (V,E) et tilde{G} = (V, tilde{E}) et soit i in V tel que forall k ne i, quad {j | (k, j) in E} = {j | (k, j) in tilde{E}}. Alors

tilde{pi}^Te_C > pi^Te_C, quad mathrm{ssi}quad delta^TZ_C > 0 ;

tilde{pi}^Te_C = pi^Te_C, quad mathrm{ssi}quad delta^TZ_C = 0.

 

Proposition[Ajout d'un lien]
Soit i in C et j in V tels que (i,j) notin E et Z_{C_i} le Z_{C_j}. Supposons que tilde{E} = E cup {(i, j)}, alors

tilde{pi}^Te_C ge pi^Te_C.

L'égalité a lieu uniquement dans le cas où i n'a pas accès à overline{C}.

 

Proposition[Retrait d'un lien]
Soit i in V et j in mathrm{argmin}_{k leftarrow i} Z_{C_k}. Soit tilde{E} = E setminus {(i, j)}, alors

tilde{pi}^Te_C ge pi^Te_C.

L'égalité se produit uniquement dans le cas où Z_{C_k} = Z_{C_j} pour tout k tel que (i, k) in E.

 

[1] De Kerchove, C., Ninove, L., & Van Dooren, P. (2008). Maximizing PageRank via outlinks. Linear Algebra and its Applications, 429(5), 1254-1276.

[2] Avrachenkov, K., & Litvak, N. (2004). Decomposition of the google pagerank and optimal linking strategy.

Comments ( 2 )

  • Bonjour,

    Le schéma décrivant la structure optimale pour maximiser le PR d’un ensemble de pages, ne correspondrait-il pas (de près ou de loin) au « cocon sémantique »décrit par Laurent Bourrelly ?

  • Bonjour Pierre,

    Si je me rappelle bien de la structure préconisée par Laurent, on ne doit pas être loin, quand on souhaite booster la page d’accueil du site. J’ai un doute sur les liens transverses, mais ce serait à vérifier.