Comment fonctionne un moteur de recherche ? (3ème partie : Popularité et PageRank)

Il se dit aussi que « le PageRank considère qu’un lien vers un site est un vote pour ce site ». Cette phrase est plutôt vraie, pour une raison que nous allons maintenant expliquer. Remontons le temps en 1998, date de la création de Google par Sergey Brin et Larry Page. L’objectif des moteurs était déjà de présenter aux utilisateurs des pages pertinentes pour leurs requêtes. Mais à cette époque les moteurs savaient seulement déterminer la pertinence d’une page pour une requête, sans être capable d’arbitrer quelle page choisir entre deux documents de pertinence égale. Or, cet arbitrage est crucial car il n’y a que dix places disponibles sur la première page de résultat.

L’idée de Larry Page (d’où le nom - assorti d'un jeu de mots - de PageRank) est de quantifier la popularité des pages : plus une page pertinente est populaire, plus on la présentera avant les autres.

La question est donc : comment quantifier la popularité, qui est une notion liée au comportement des internautes, de manière formelle et quantifiable par un calcul ?

La véritable définition du PageRank

L’idée derrière le PageRank, quand on observe la formule canonique, peut sembler très obscure. Pourtant, elle est intuitivement excessivement simple. Quand on y réfléchit, déterminer qu’un site web, et plus précisément une page spécifique d’un site web, ou n’importe quelle page du Web, est populaire, est quelque chose de très logique et évident : une page est populaire si les internautes s’y attroupent ! Ce n’est pas une surprise, une page qui est visitée est une page qui attire, qui est populaire.

La seule façon, a priori, de savoir si beaucoup d’internautes visitent une page, consiste à suivre le flux des visiteurs. Si, de nos jours, une solution comme Google Analytics est embarquée par de nombreux sites web, et permet au webmaster de connaître le trafic de son site, elle permet aussi à Google, par effet de bord, de comparer le trafic de chaque site web entre eux. Vu le taux d’utilisation de cette solution d’analytiques, on pourrait imaginer que le PageRank est fabriqué activement à partir de ce flux gracieux de datas.

Mais en 1998, Google en est seulement à ses débuts. Il n’est pas possible pour lui de monitorer le trafic du Web. Il s’agit donc de réussir à trouver un subterfuge pour déterminer le trafic d’une page, sans pour autant le connaître réellement.

C’est curieux, et pourtant loin d’être insoluble. Larry Page l’a bien compris. Si on n’a pas la possibilité de monitorer les flux de visiteurs, peut-être qu’on peut théoriser la façon dont ils parcourent le Web. Ainsi, au lieu de surveiller un trafic réel, on surveille un trafic théorique, répondant à un comportement attendu des internautes.

Ce modèle, c’est le modèle du visiteur virtuel, appelé "Surfeur aléatoire". Cet internaute "modèle" a un comportement de voyageur passant de pages en pages au fil des liens rencontrés.

Au départ, on place un surfeur sur une page web, choisie au hasard, puis on considère qu’il liste tous les liens sortants présents sur cette page, et en choisit un, au hasard, qu’il va suivre, pour arriver sur une autre page. Parfois, le surfeur va souhaiter s’intéresser à quelque chose d’autre, qui n’est pas en lien avec cette page. Il va repartir d’une page web tirée au hasard sur le web. On aime à dire qu’il se "téléporte" puisque même sans la présence d’un lien, un chemin qui le guiderait, il va ailleurs, sur le Web.

Imaginons maintenant que le surfeur aléatoire n’est plus tout seul sur le Web. Pas un surfeur, ni deux, ni trois, mais des milliers, voire des milliards de surfeurs, sont de sortie. Que se passe-t-il ? A un instant I, quand on observe le trafic d’une page web, on sait aussitôt qu'elle est populaire si elle accueille beaucoup de surfeurs. Au contraire, si peu de surfeurs sont présents, c’est qu’elle est peu populaire.

Maintenant, au lieu de parler de foules de surfeurs, revenons à un seul surfeur. Si on suit suffisamment longtemps son parcours, on va le voir revenir parfois sur certaines pages, tandis qu’il n’en verra jamais d’autres, ou très peu. Il a donc une certaine probabilité, à un instant donné, d’être sur une page donnée. Plus la probabilité est élevée, plus on a de chances de le rencontrer, plus on peut considérer que c’est une page qu’il aime visiter. C’est donc une page populaire. Si au contraire la probabilité est faible, la page sera peu populaire.

Le PageRank, c’est cette probabilité. Ni plus, ni moins.

Retour aux mathématiques

Maintenant que le concept du PageRank n’a plus de secret pour vous, on a bien envie de savoir comment calculer le PageRank d’une page… Pour connaître la probabilité de présence du surfeur aléatoire, on calcule la distribution stationnaire de la chaîne de Markov associée au graphe du Web. Et de cette distribution, en épargnant les détails le plus techniques, on en déduit la formule "traditionnelle", celle de la figure 1.

Fig. 1. La formule du PageRank.

Cette formule du PageRank a quelque chose de notable, qu’il faut bien prendre en compte pour l’appliquer efficacement : c’est une formule dite itérative, c’est à dire qu’on l’applique plusieurs fois de suite, jusqu’au moment où les résultats se stabilisent.

Regardons en détail cette formule. Au moment de l’initialisation, chaque page du web se voit donner la même valeur de PageRank, c’est à dire (1/N), N étant le nombre total de pages sur le Web. Ensuite, les règles de transmission s’appliquent et le PageRank de la page évolue à chaque tour, en fonction notamment d’une variable c, qui est appelée le Damping Factor, qui vaut, dans l’article original de Brin et Page, 85% [1].

Le facteur (1-c)/N permet, à chaque tour, de redonner du PageRank à chaque page du Web.

Le second côté de l’addition permet le transfert de PageRank d’une page à l’autre en fonction du nombre de liens présents sur la page dont les liens sont issus.

On retient de cette formule que la valeur de PageRank pour une page vaut entre 0 et 1, et que la somme des PageRanks de toutes les pages du web vaut 1.

Quel impact pour le référencement web ?

A partir de cette définition on peut en déduire quelques conséquences particulièrement intéressantes pour le référencement web, c’est-à-dire pour maximiser la popularité d’une page.

La première conséquence, souvent vue comme contre-intuitive, est qu’on peut gagner du PageRank en faisant un lien sortant.

C’est quelque chose de généralement assez surprenant puisqu’on pense avant tout à faire des liens entrants pour améliorer le PageRank d’une page. Pourtant, quand on réfléchit au concept du surfeur aléatoire, on se rappelle que la popularité d’une page est avant tout la fréquence de passage du surfeur sur la page. Mettre en place davantage de points d’accès fonctionne, bien sûr, mais ce n’est pas l’essentiel : il faut avant tout permettre au surfeur de revenir souvent. Et pour qu’il puisse revenir, cela implique d’accepter, aussi, de le laisser partir.

On peut donc faire des chemins qui bouclent autour d’une même page afin de faire revenir le plus souvent possible le surfeur aléatoire, ce qui maximise la valeur du PageRank de cette page.

Fig. 2. Faire un lien sortant pour augmenter son PageRank.

Sur la figure 2, on s’intéresse à la page rouge. A gauche, le surfeur arrive sur la page verte, il a deux comportements possibles seulement : soit il se téléporte pour aller ailleurs sur le web. Soit il suit le lien et va sur la page rouge, puis il ne peut que se téléporter. Le surfeur passe une seule fois sur la page rouge.

Sur le schéma de droite sur la figure 2, le surfeur aléatoire, une fois arrivé sur la page rouge, possède une autre option : revenir sur la page verte. Une fois de retour sur la page verte, il peut encore retourner, pourquoi pas, sur la page rouge, puis verte, etc. Le surfeur passe bien plus souvent sur la page rouge.

Le PageRank de la page rouge est donc plus haut sur le schéma de droite que sur celui de gauche. En ajoutant un lien sortant de la page rouge, on a augmenté le PageRank de la page rouge.

Ce type de schéma de lien, en boucles très courtes, permet de faire revenir fréquemment le surfeur aléatoire, et donc d’augmenter la popularité de la page. Plus les boucles sont courtes, plus l’optimisation est forte. Lors de l’acquisition de liens, internes ou externes, il faut toujours penser en termes de boucles. Faire des liens vers l’extérieur est utile si cela permet de faire revenir le visiteur après quelques rebonds.

Une seconde conséquence est que l’on peut gagner du PageRank grâce à un lien entre deux pages sur des sites qui ne sont pas les nôtres.

Après avoir vu qu’un lien sortant pouvait amener un gain de PageRank, cela devient plus facile à imaginer, mais tout de même, il faut insister : on peut aussi faire gagner du PageRank à une page en mettant en place un lien entre deux pages sur des sites qui ne sont pas les nôtres.

Fig. 3. Lier des pages de sites extérieurs pour augmenter le PageRank.

La figure 3 montre deux  structures dont la page rouge est celle qui nous appartient. Les deux autres pages sont à des tiers. Sur le schéma de gauche, un tiers fait un lien vers notre page, tandis que nous faisons un lien vers un autre tiers.
En arrivant depuis la page verte, le surfeur aléatoire passe éventuellement par notre page puis s’en va et ne revient jamais.

Sur le schéma de droite, nous avons contacté le webmaster du site bleu et lui avons indiqué qu’un lien vers le site vert serait une bonne chose. Aussitôt, une boucle se forme. Le surfeur aléatoire peut maintenant revenir sur la page verte, puis être de retour sur notre page. Le cycle est bien présent, avec rebond. Le PageRank de la page rouge augmente, ainsi que le PageRank des autres pages de la boucle.

Il s'agit d'une façon discrète de faire de l’amélioration de PageRank puisqu’on ne fait pas pointer en direct des liens vers nos pages. Comment soupçonner le site rouge d’essayer de manipuler sa popularité ? Cependant, l’amplification n’est pas aussi forte qu’en cas de liens réciproques directs.

Comment pratiquer l’acquisition de liens quand on pense surfeur aléatoire ?

Les bonnes pratiques qui se déduisent du concept de surfeur aléatoire sont peu nombreuses : faire de l’acquisition réfléchie de liens est largement accessible à tout le monde. Quels sont les schémas à mettre en place ? Pensons surfeur aléatoire et tout devient plus clair, avec ces quelques règles :

1. Les meilleurs schémas d’amplifications sont le lien réciproque, la boucle et le lien classique.
2. Limiter le nombre de liens sortants à un seul par page est l’idéal. Mais ce n’est dans les faits pas réalisable à cause des éléments de navigation et de l’expérience utilisateur : on limite au maximum les liens, tout lien superflu doit être évité (on se limite aux liens qui font revenir le surfeur aléatoire) .
3. On évite de faire des liens sur toutes les pages d’un même site vers un tiers. Il vaut mieux pointer vers une page interne au site et y placer le lien vers l’extérieur. Cela permet de limiter la fuite du surfeur, tout en lui permettant tout de même de quitter le site (il faut bien lui donner l’opportunité de pouvoir revenir).

Le Surfeur n’est-il pas en réalité plus intelligent ?

La modélisation proposée par Brin et Page a quelque chose de fascinant : elle semble pouvoir dicter avec une belle précision la popularité des pages. Mais on imagine bien qu’en réalité, le surfeur n’est pas aussi aléatoire. Il ne clique sans doute pas complètement au hasard sur des liens, il doit certainement être influencé par des éléments contextuels. Va-t-on avoir moins de chance de suivre un lien particulier sur une page parce qu’il y a 100 liens sur cette page plutôt qu’un seul ? Imaginons un lien textuel en gras, dans une grosse police, placé en haut de page, dans un cadre clignotant, et 99 autres liens en dessous, plus petits dans une couleur difficile à percevoir. Où le surfeur va-t-il cliquer ? Les chances de cliquer sont-t-elles les mêmes selon l’emplacement des liens ?

De même, peut-on penser qu’un internaute consultant un site de petites annonces pour trouver un appartement va donner autant de valeur à un lien l’amenant vers une petite annonce qu’à un lien le conduisant à une page de calcul de prêt immobilier ?

Il est facile d’imaginer que le surfeur est en réalité bien moins aléatoire qu’on ne pourrait le croire via une modélisation simple. Les contenus des pages, les thématiques, sont des éléments à prendre en compte si l’on souhaite obtenir une idée plus précise de la popularité.

Le PageRank Thématique

Il existe de nombreuses manières d’obtenir des surfeurs aléatoires qui modélisent de manière plus réaliste le comportement des internautes. L’approche qui semble la plus efficace est d’embarquer des informations thématiques dans le modèle.

Parmi toutes les approches qui ont été envisagées à partir de 2000, c’est le PageRank thématique de Taher Haveliwala qu’il faut retenir. Ce dernier avait mis au point la notion lors de sa thèse, mais il avait transféré la propriété intellectuelle dans la start-up Kaltix (cofondée avec Glen Jeh et Sep Kamvar). Kaltix a ensuite été achetée par Google, qui a tiré tous ses algorithmes de personnalisation des réalisations de Kaltix (le BlockRank et le PageRank adaptatif sont des produits de Kaltix par exemple).

Dans le contexte du PageRank thématique, chaque page a une popularité différenciée par thématique. Ainsi une même page peut être populaire pour, par exemple, la thématique sport, mais pas pour la thématique people. Le surfeur aléatoire sensible à la thématique a des comportements plus riches que le surfeur aléatoire classique (voir la figure 4) :

1. Lorsqu’il est sur une page donnée, il peut soit se téléporter soit suivre des liens (jusqu’ici, rien de nouveau).
2. S'il se téléporte, ce sera vers une page tirée au hasard, mais en s’intéressant spécifiquement à une des thématiques (par exemple la thématique vacances).
3. S'il suit un lien, il peut soit continuer à s’intéresser à la même thématique (par exemple la voiture) ou au contraire changer de centre d’intérêt (passer de la voiture aux vacances).

Comme chaque page possède des scores thématiques, on sait quelles sont les thématiques portées par la page, et dans quelle mesure elles sont importantes ou pas au sein du contenu de la page. Continuons sur l’exemple d’une page qui aborde le sujet du sport et des people. elle se verra attribuée par exemple une adéquation de 70% dans la thématique sport, et une adéquation de 30% pour la thématique people. Il s’agit donc par exemple d’une page qui parle de football, mais aussi des folles soirées des joueurs dans des boites de nuits branchées.

Fig. 4. Les comportements du surfeur thématique.

Sans rentrer dans les détails techniques, on peut dire que cette ventilation de la popularité thématique pour chaque page est stockée dans un vecteur qui a autant de composantes qu’il y a de thématiques considérées dans l’index du moteur. Et le PageRank thématique a un avantage : pour faire les calculs de PageRank thématique au niveau de l’index Web complet, on va faire un calcul de PageRank standard pour chaque thématique, ce qui fait que le surcoût du PageRank thématique est très faible. Notez cependant qu’on manipule deux vecteurs : l’un contient les PageRanks thématique par thématique tandis que l’autre contient les pourcentages d’adéquation à chaque thématique.

Mettre en action le PageRank thématique au niveau du moteur

A ce stade de nos explications, il ne semble pas y avoir de rapport entre les requêtes et les deux vecteurs qui sont créés pour chaque page. Nous allons voir au travers d’un exemple comment cela fonctionne.

1. Quand une requête est tapée par un utilisateur, le moteur va créer un vecteur d’adéquation au contenu pour cette requête. Par exemple, la requête « Jaguar » va être considérée comme étant à 70% dans la thématique « animal » et à 30% dans la thématique « voiture ».

2. Le moteur prend alors le PageRank de chaque page pour les thématiques de la requête et va faire la somme pondérée de ces PageRanks pour construire un score global. La figure 5 schématise tout cela. On voit quatre pages web avec des PageRanks différents dans les thématiques auto et animaux. Le PageRank “à l’ancienne” est la somme des PageRank thématiques de chaque page et est inscrit dans la deuxième ligne du tableau (PR). Si on veut calculer le score de la page 2 (par exemple) pour la requête “jaguar”, on doit prendre 70% du PageRank de la page 2 pour la thématique animaux (0,28 ici) et 30% du PageRank de la page pour la thématique auto (0 ici car la page a un PageRank de 0 sur cette thématique - c’est-à-dire une adéquation de 0%), et faire la somme des deux. Pour la requête “jaguar”, la popularité de la page 2 est donc de 0,28.

3. Les pages sont alors classées par score. On a donc un classement potentiellement différent pour chaque requête. Vous pouvez voir dans la figure 5 la différence entre le PageRank thématique (TS-PR sur la figure) et le PageRank standard (PR).

Fig. 5. Exemple de calcul de score thématique.

Maintenant que l’on sait comment ça marche, qu’est ce qu’on peut retirer de tout cela quand on est SEO ?

Le PageRank thématique est la base théorique du cocon sémantique

Vous vous posez peut-être la question de savoir si le PageRank thématique a le moindre rapport avec la fameuse notion de cocon sémantique. Sans vous expliquer les détails méthodologiques de ce qu’est le cocon sémantique (Nous vous renvoyons vers les divers articles dont ceux de Laurent Bourrelly sur le sujet), on peut néanmoins dire que le PageRank thématique est le moteur théorique du cocon sémantique.

En effet, lorsque vous faites un lien d’une page vers une autre, si vous faites bien attention à ce que les pages source et cible soient dans la même thématique, ou dans des thématique proches (notion de “glissement sémantique”), alors vous maximisez la transmission de popularité.

Vous l’avez compris, le PageRank thématique est une valeur associée aux pages web (et pas aux sites), mais étant donné que les liens externes sont plus puissants que les liens internes, il est pertinent d’utiliser la notion de PageRank thématique pour faire des cocons de sites. C’est là où vous aurez des transmissions de popularité maximales. Par ailleurs, la logique de cocon entre sites permet de faciliter nettement les opérations de netlinking, en s’éloignant des domaines les plus commerciaux d’une thématique pour se rapprocher des domaines informationnels. Par exemple, au lieu de chercher des liens sur des sites parlant de vente de machine à café, vous pouvez prendre des liens sur des sites parlant du détartrage desdites machines. Grâce à la logique de cocon, et donc grâce au PageRank thématique, les liens auront de la valeur, et sont plus faciles à obtenir que des liens chez vos concurrents.

Enfin, cette logique d’entourage par des pages moins “agressives” de la thématique améliore l’expérience utilisateur puisque les internautes viendront naturellement chez vous via un entonnoir de conversion qui commencera par des pages d’information (un bon point de départ pour déclencher une impulsion d’achat).

Les bonnes pratiques SEO à retenir concernant le PageRank thématique

Les bonnes pratiques sont les mêmes que pour le PageRank standard, sauf qu’il faut garder à l’esprit que la source et la cible d’un lien doivent être proche thématiquement.
Pour cela vous pouvez utiliser différentes sources de données de thématisation, comme par exemple Majestic.
Imaginons les trois pages web suivantes (avec les données Majestic associées) :

1. www.site1.com a un Trust Flow (TF) de 39, un Citation Flow (CF) de 48 et ses deux principaux Topical Trust Flow (TTF) sont de 31 en thématique informatique et 30 en business/food.
2. www.site2.com a un TF de 52 et un CF de 50, et ses trois premiers TTF sont 52 en shopping, 22 en news et 21 en informatique.
3. www.site3.com est votre site, il parle de réparation de PCs et il a un TF de 8, un CF de 15 et ses deux premiers TTF sont 8 en informatique et 5 en business.

Si vous devez choisir entre site1 et site2, lequel allez-vous prendre pour vous faire un lien ? Sur le papier le site2 a l’air plus puissant, mais sa proximité thématique sur vos deux thématiques principales est moins bonne que celle de site1. Dans une logique de PageRank thématique, il est plus judicieux de choisir site1 comme source d’un lien vers votre site.

D’autres algorithmes de popularité ?

Il existe bien d’autres algorithmes pour quantifier la popularité ou autorité d’une page web. Parmi ceux-là, on trouve par exemple (sans ordre particulier) :

1. HITS, un algorithme mis au point par Jon Kleinberg en 1998 et qui va utiliser en plus de la notion d’autorité la notion de pages “hub”, qui sont des pages qui mettent en avant de nombreuses pages intéressantes (des sortes d’annuaires donc, ou des sites comme wikipedia).
2. L’AncestorRank de Wang et Davison qui va compter les ancêtres d’une page, c’est-à-dire additionner le nombre de pages qui pointent vers la page avec le nombre de pages qui pointent vers les pages qui pointent vers la page avec les pages qui pointent vers les pages qui pointent vers les pages qui pointent vers la page etc.
3. Indegree : on se contente de compter le nombre de liens entrants (c’est Marchiori qui a utilisé l’idée en 1997).
4. Salsa, par Lempel et Moran (deux grands spécialistes du PageRank) en 2000. C’est un mix entre HITS et le PageRank.
5. HubAvg (hub averaging) qui est un algorithme qui va éviter un problème de HITS, qui est que certains hubs sont trop puissants à tort. On va donc moduler leur puissance pour éviter que des sites ridicules ne se retrouvent dans les premières positions.
6. Iceberg, qui est un algorithme de popularité mis au point et utilisé par Qwant. Il est basé sur la raffinage successif des popularités des pages (et nous n’en dirons pas plus).

Il existe donc de très nombreux autres algorithmes, qui aboutissent tous aux mêmes types de classements, modulo quelques pages qui sont plus ou moins favorisées selon l’algorithme.

Conclusion

Ce mois-ci nous avons vu comment un moteur de recherche moderne peut caractériser la popularité d'une page web de manière à ne présenter que les pages les plus populaires parmi celles qui sont pertinentes pour une requête donnée. Nous avons vu qu'au delà du PageRank de 1998, il existe des algorithmes plus évolués, dont le fameux PageRank thématique. La connaissance de ces algorithmes permet de comprendre les bonnes pratiques SEO (en matière de liens entrants et sortants) et aussi pourquoi les notions de silo ou cocon sont importantes en terme de structuration d'un site et de son entourage. Le mois prochain, nous aborderons le sujet de l’analyse de la pertinence. Vous n'en avez pas fini avec nos explications de ce qui se passe sous le capot d'un moteur de recherche !

Références

Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: bringing order to the Web.
http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

Largillier, T., & Peyronnet, S. (2014). Algorithmique du web: autour du PageRank. Informatique Mathématique Une photographie en 2014. Presses Universitaires de Perpignan.

Bianchini, M., Gori, M., & Scarselli, F. (2005). Inside PageRank. ACM Transactions on Internet Technology (TOIT), 5(1), 92-128.
http://www.di.ens.fr/~vergnaud/algo0910/PageRank.pdf

Gyöngyi, Z., & Garcia-Molina, H. (2005, August). Link spam alliances. In Proceedings of the 31st international conference on Very large data bases (pp. 517-528). VLDB Endowment.
http://ilpubs.stanford.edu:8090/679/1/2005-15.pdf

Avrachenkov, K., & Litvak, N. (2004). Decomposition of the google PageRank and optimal linking strategy.
http://doc.utwente.nl/80247/1/RR-5101.pdf

De Kerchove, C., Ninove, L., & Van Dooren, P. (2008). Maximizing PageRank via outlinks. Linear Algebra and its Applications, 429(5), 1254-1276.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.8108&rep=rep1&type=pdf

Richardson, M., & Domingos, P. (2001). The Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank. In NIPS (pp. 1441-1448).
http://alchemy.cs.washington.edu/papers/pdfs/richardson-domingos02a.pdf

Haveliwala, T. H. (2003). Topic-sensitive PageRank: A context-sensitive ranking algorithm for web search. Knowledge and Data Engineering, IEEE Transactions on, 15(4), 784-796.
http://ilpubs.stanford.edu:8090/750/1/2003-29.pdf

Nie, L., Davison, B. D., & Qi, X. (2006, August). Topical link analysis for web search. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 91-98). ACM.

J. Wang & B. D. Davison. (2009). Counting Ancestors to Estimate Authority. Poster summary in Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.

Borodin, A., Roberts, G. O., Rosenthal, J. S., & Tsaparas, P. (2005). Link analysis ranking: algorithms, theory, and experiments. ACM Transactions on Internet Technology (TOIT), 5(1), 231-297.
http://snap.stanford.edu/class/cs224w-readings/borodin05pagerank.pdf