Comment amplifier le PageRank (2/3)

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

 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.

Nous allons maintenant nous intéresser à la deuxième méthode d'amplification, qui donne la stratégie de création de liens optimale pour la maximisation du pagerank d'une page seule.

 

Structure de lien optimale pour une page seule

Avrachenkov et Litvak [1] ont regardé les effets de l'ajout de liens dans le graphe du web sur la valeur du pagerank.
Nous allons d'abord définir quelques objets importants.  Nous allons utiliser la matrice Z = [I - cP]^{-1}, et le vecteur e_k, qui est le vecteur colonne qui ne contient que des 0 excepté sur sa k-ième composante qui vaut 1. Les éléments z_{ij} de la matrice Z représentent le nombre moyen de visites effectuées sur la page j avant téléportation, lorsque que l'on part de la page i.

Considérons maintenant qu'une page qui fait déjà k_o liens sortant en ajoute k_1. Sans perte de généralité, supposons que la page qui ajoute ces liens est la page 1 et que ses nouveaux liens pointent vers les pages numérotées 2 à k_1+1. L'addition de ces nouveaux liens peut être vue comme une mise à jour de rang 1 de la matrice de transition des hyperliens

tilde{P} = P + e_1v^T,

avec v^T=frac{k_1}{k}left(frac{1}{k_1}sum_{i=2}^{k_1+1}e_i^T - p_1^Tright),k = k_0 + k_1, et p_1^T est le vecteur représentant la première ligne de la matrice P. Le théorème ci-dessous donne de manière explicite les formules de mise à jour du vecteur contenant les pagerank de chaque page.

Théorème
Supposons que la page 1 ajoute k_1 nouveaux liens sortants. Les éléments du vecteur PageRank sont donnés par les formules de mise à jour suivantes:

tilde{pi}_1 = frac{pi_1}{1 - frac{k_1}{k}left( 1 + frac{c}{k_1}sum_{i = 2}^{k_1+1}z_{i1} - z_{11}right)}

tilde{pi}_j = pi_j + pi_i frac{frac{k_1}{k}left( frac{c}{k_1}sum_{i = 2}^{k_1+1}z_{ij} - z_{1j}right)} {1 - frac{k_1}{k}left( 1 + frac{c}{k_1}sum_{i = 2}^{k_1+1}z_{i1} - z_{11}right)}, j = 2, cdots, n

Preuve
En appliquant la formule de Sherman-Morrisson-Woodbury à [I - ctilde{P}]^{-1}, on peut écrire:

[I - ctilde{P}]^{-1} = [I - cP]^{-1} + cfrac{[I - cP]^{-1}e_1v^T[I - cP]^{-1}}{1 - cv^T[I - cP]^{-1}e_1}

En multipliant l'équation ci-dessus par frac{1-c}{n}textbf{1}^T et utilisant l'expression du PageRank décrite plus haut, on obtient:

tilde{pi} = pi + pi_1frac{cv^T[I - cP]^{-1}}{1 -cv^T[I - cP]^{-1}e_1}

Après quelques manipulations, on peut trouver :

cv^T[I - cP]^{-1}e_j = cv^TZe_j = cfrac{k_1}{k}left( frac{1}{k_1}sum_{i=2}^{k_1+1}e_i^T - p_1^Tright)Ze_j

En notant que cPZ = Z - I, on a alors cp_1^TZ = z_1^T-e_1^T avec z_1^T la première ligne de la matrice Z, et donc cp_1^TZe_j = z_{1j} - e_1^Te_j, ce qui nous donne

cv^T[I - cP]^{-1}e_j = frac{k_1}{k}left(frac{c}{k_1}sum_{i=2}^{k_1+1} z_{ij} - (z_{1j} - e_1^Te_j)right)

En remplaçant l'expression de cv^T[I - cP]^{-1}e_j dans les équations vues plus haut, on obtient les équations du théorème.

 

Avrachenkov et Litvak ont par la suite regardé ce qu'il advient des formules de mise à jour du théorème dans le cas où c est suffisamment proche de 1 et que la chaîne de Markov induite par la matrice des hyperliens P est irréductible. Cette approche asymptotique leur a permis de définir des conditions simples et naturelles pour savoir si une page créant des liens, et ses voisins, bénéficie des liens nouvellement crées. Ces conditions sont présentées dans le théorème suivant.

Théorème
Soit c suffisament proche de 1. Supposons que la page 1 ajoute k_1 liens sortants vers les pages {2, cdots, k_1+1}. Supposons que la chaîne de Markov induite par la matrice des hyperliens P soit irréductible, alors nous obtenons les conditions suivantes:

  • si m_{11} > 1 + frac{1}{k_1}sum_{i=2}^{k_1+1}m_{i1}, alors la création des nouveaux liens {1 rightarrow 2, cdots, 1 rightarrow k_1+1} augmente le pagerank de la page 1
  • si m_{1j} > 1 + frac{1}{k_1}sum_{i=2,ine j}^{k_1+1}m_{ij}, alors la création des nouveaux liens {1 rightarrow 2, cdots, 1 rightarrow k_1+1} augmente le pagerank de la page j pour jin {2, cdots, k_1+1}
  • si m_{1j} > 1 + frac{1}{k_1}sum_{i=2}^{k_1+1}m_{ij}, alors la création des nouveaux liens {1 rightarrow 2, cdots, 1 rightarrow k_1+1} augmente le pagerank de la page j, pour j >k_1+1

m_{ij} est le temps moyen de premier passage sur la page j en
partant de la page i si c = 1.

La preuve, très technique, est ici omise et le lecteur intéressé pourra se reporter à l'article d'Avrachenkov et Litvak pour les détails.
Les conditions présentées dans le théorème précédent sont assez naturelles à interpréter d'un point de vue probabiliste et le deviennent encore plus lorsque l'on ne considère l'ajout que d'un seul lien. La première condition devient alors m_{11} > m_{21} + 1, ce qui signifie que la longueur moyenne du chemin de 2 à 1 doit être plus courte d'au moins un saut par rapport à la longueur moyenne du chemin reliant 1 à elle-même. La condition 2 devient m_{12} > 1, ce qui est toujours vrai. Ce n'est pas surprenant puisque l'addition d'un seul lien dans le graphe du web augmente toujours le pagerank de la page qui en est la cible.

Le dernier résultat d'Avrachenkov et Litvak présente la structure optimale de liens sortants que doit adopter une page pour maximiser son pagerank.

Soit une page i qui possède des liens vers les pages i_1, cdots, i_ki_l ne i, forall l = 1, cdots, k. En utilisant la matrice tilde{P}, on obtient alors :

m_{ii} = 1 + frac{c}{k}sum_{l = 1}^{k}m_{i_li} + frac{1}{n}(1 - c)sum_{j=1, jne i}^{n} m_{ji},

m_{ij} est toujours le temps moyen de premier passage sur la page j en partant de i et c est la constante évoquée dans les billets précédents (sous le nom de c ou de alpha). L'objectif est de choisir les i_1, cdots, i_k de manière à minimiser m_{ii} tout en garantissant que pi_i = 1/m_{ii} soit maximisé. m_{ii} est une fonction linéaire des m_{ji} et les liens sortants de i n'affectent pas les m_{ji}. Dès lors, le mieux que puisse faire un utilisateur est de ne faire qu'un seul lien sortant vers une page j^* telle que m_{j^*i} = min_j{m_{ji}}.

On remarquera que le pagerank de la page j^* n'a aucun impact dans ce résultat. Ceci mène donc au théorème présenté ci-dessous.

Théorème
La stratégie optimale pour une seule page p consiste en un seul lien sortant vers la page du web q qui a le plus faible premier temps de retour moyen vers p.

Ce résultat théorique n'a pas un impact pratique très important. En effet, il est souvent très peu pratique de ne faire qu'un seul lien, par exemple car cela ne permet pas de mettre en place un système de navigation réaliste au sein du site. De plus, il est en pratique extrêmement difficile d'estimer la valeur de m_{ji} pour chaque page j.

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

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

 

Comments ( 4 )