Hubert Wassner

Petit historique

Les premiers moteurs (altavista ou yahoo) ne faisaient qu'indexer, c'est à dire trouver toutes les pages contenant le ou les mots clés recherchés. On pouvait retrouver les pages contenant un mot clé donné mais les résultats n'étaient pas triés efficacement. Le nombre de fois où apparaissait le mot clé faisait apparaître la page en haut de la liste de résultat, ce qui n'est pas pertinent. Le nombre de répétions du mot clé n'est pas un critère intéressant car aisément falsifiable. Il faut faire une analyse plus fine du web pour être capable de mesurer automatiquement l'importance de chaque site. Sergey Brin et Lawrence Page, étudiants à standford on trouvé une solution aussi originale que simple : utiliser l'information des liens entre les pages pour mesurer l'importance des sites, et être alors capable de classer correctement les résultat d'une recherche de mots clés. Cet algorithme s'appelle le « pagerank », il est finalement assez simple (niveau deuxième année d'étude supérieure, je le propose d'ailleurs dans mon cours). Sergey et Lawrence ont créé l'entreprise Google qui est alors le meilleur moteur de recherche du web. Google est devenu très rapidement (et sans aucune publicité) un des moteurs les plus influant du web, les autres (yahoo etc...) on rapidement suivit, mais bien sur cette avancé technologique leur à a permis d'être les « first to market » et donc de prendre une longueur d'avance sur la concurrence... Google essaye de garder cet avantage, en proposant toujours de réelles avancées technologiques, et bien sûr en améliorant l'algorithme pagerank qui est devenu un secret industriel aussi bien gardé que la fameuse recette exacte du coca-cola. La version que j'expose ici reste est une approche à la fois simple et instructive pour comprendre les bases du référencement vu que maintenant tous les moteurs de recherche utilisent des variantes de cet algorithme.

Le pagerank, comment ça marche ...

L'algorithme pagerank calcule un indice de popularité associé à chaque page web. C'est cet indice qui est utilisé pour trier le résultat d'une recherche de mot clé. L'indice est définit ainsi : L'indice de popularité d'une page est d'autant plus grand quelle à un grand nombre de pages populaires la référençant (ayant un lien vers elle). Cette définition est autoréférente car pour connaître le l'indice d'une page il faut d'abord connaître l'indice des pages ayant un lien vers elle... Il existe cependant un moyen assez simple d'approcher une valeur numérique de l'indice.

Tout d'abord il faut voir le web comme un graphe. Chaque page est un noeud du graphe, chaque lien entre page est un arc entre deux noeuds.

Un manière commode pour représenter de telles relations est d'utiliser une matrice (= un tableau) : chaque ligne et colonne représentant un noeud (donc un site) et chaque case de la matrice représente la présence d'un lien entre les 2 pages correspondantes.

Note : Pour savoir si il y a un lien entre 2 sites A et B, il suffit de regarder le contenu de la case positionné en ligne A et colonne B : 0 signifie qu'il n'y a pas de lien, 1 qu'il y en a un.

Nous allons appeler cette matrice M. On représente la probabilité de présence d'un internaute sur tous les noeuds de notre graphe par un vecteur V. Dire que l'internaute est sur la page « 1 » s'écrit : V = (0 1 0 0). (attention on commence à compter les pages par 0 c'est donc bien la deuxième valeur qui est à 1 dans ce vecteur).

Si on multiplie V par M :

V' = V*M

Si on faisait partir notre internaute de la page « 3 » : V = (0 0 0 1) le produit V par M donne (1 0 1 0), la somme des composante fait alors 2, c'est gênant pour représenter une probabilité de présence... . Dans la mesure où il impossible de savoir quel liens aura le plus de succès on va considérer qu'il ont tous la même probabilité d'être suivit, cela revient à normaliser la matrice (diviser chaque composante par la somme des valeur de la ligne correspondante), le problème est résolut. La matrice devient alors :

Notez que la somme de chaque ligne fait bien 1, et que le produit V * M donne alors V' = (½ 0 ½ 0) et représente alors correctement les probabilités de présence de l'internaute, partant de la page « 3 » et après avoir suivit un lien (« 1clic »). Si on re-itère l'opération , c'est à dire V'*M on obtient (1 0 0 0) au bout du deuxième « clic » de l'internaute. Si on continue on voit bien que le résultat ne changera plus... L'internaute est bloqué sur la page « 0 ». Cela n'est pas très réaliste, on considérera alors que l'internaute repart sur une autre pas, choisie au hasard. Cela revient à ajouter aux pages « cul de sac » des liens vers toutes les autres pages. Du point de vu de la matrice cela revient à trouver les lignes qui n'ont que des 0 et les replacer par des lignes avec 1/3 (dans ce cas précis) dans toutes les cases sauf sur la diagonale (lien d'une page vers elle même). Pourquoi 1/3 ? Tout simplement par ce qu'il y a 4 pages et qu'on considère que l'internaute reprendra son parcours aléatoirement sur n'importe quelle autre page (4(toutes les page) – 1 (celle ou il est actuellement « bloqué ») = 3).

Le processus tel qu'on la définit permet, maintenant, de modélisé raisonnablement un déplacement aléatoire d'internautes sur le réseau de page, modélisé par un graphe. Pour obtenir une vision globale et impartiale de la popularité des pages en fonction des liens qu'elles ont entre elles, il suffit maintenant de supposer que les internautes se répartissent initialement uniformément sur tout le réseau et on les laisse se déplacer jusqu'à ce que leur répartition (le vecteur V) se stabilise au fur et à mesure des itération de multiplication avec M. Dit autrement on commence avec un vecteur V dont toutes les composantes sont égales a 1/N, N étant le nombre total de pages (ou noeuds du graphe). Ensuite on multiplie itérativement V par M jusqu'à ce que le valeur du vecteur V n'évolue plus. On regarde alors la répartition des internautes sur le graphe, cela nous donne l'indice pagerank, plus il est élevé plus il y a d'internautes sur la page, donc plus la page est populaire...

Une recherche se décompose alors en deux étapes :

• la sélection des pages contenant les mots clés de la requête.

• Le classement , par ordre décroissant, des pages concernées en fonction de leur valeur de pagerank. Cette valeur aura bien sur été calculée précédemment et n'est pas recalculé à chaque requête.

Ces deux actions combinées font un moteur de recherche plutôt efficace...

On voit que algorithme pagerank (simplifié) est finalement assez simple:

	
initialisez toutes les composantes de V à 1/N (N étant
	le nombre de pages ou noeud du graphe)
	
calculer V'= V*M, (où M est la matrice représentant
	le graphe)
	
copier le contenu de V' dans V
	
reprendre en 2 sauf si les deux vecteurs V et V' sont très
	proche, dans ce cas l'algorithme est terminé

V ou V' (puisqu'il sont proche la fin de l'algorithme) contiennent les indices pagerank de chaque page. En pratique les valeurs de pagerank sont modifiés pour donner des valeurs entre 0 et 10, pour que cela soit plus « parlant ». Cela n'a que peu d'importance en pratique dans la mesure où on utilise cette valeur uniquement pour la comparaison entre les différents sites concerné par une recherche de mot clé.

Essayez vous même ...

La fenêtre qui s'est ouverte quand vous êtes arrivé sur cette page est une démonstration de cet algorithme réalisé par deux étudiants de deuxième année dans le cadre d'un TP de deuxième année (Vincent GERMAIN & Steevy MONTOUT).

Si vous avez fermée cette fenêtre, cliquez sur le bouton pour recharger la page, elle devrait re-apparaître. (Il faut que Java soit activé sur votre navigateur)

Ce démonstrateur est très simple d'utilisation :

• Cliquez avec le bouton gauche de la souris, quelque part dans le cadre vide pour créer des noeuds (représentation d'une page web).

• Faite un « drag&drop » (« glissé déplacé ») pour créer des liens entre les pages

• appuyez sur bouton gauche de la souris près du noeud de départ

• déplacez la souris vers le noeud d'arrivé en laissant le bouton enfoncé.

• Relâchez le bouton près du noeud d'arrivé. Le lien est alors crée.

• Pour supprimer des noeuds ou liens, faite la même opération que pour la création (clic ou drag&drop) mais avec le bouton de droite.

• Le bouton du milieu permet de déplacer un noeud.

• Cliquez sur le bouton «  Pagerank » pour lancer le calcul « pagerank » sur le graphe ainsi constitué.

Le résultat du pagerank est matérialisé en changeant la taille des noeuds et leur couleur : plus le noeud est grand et tend vers le rouge plus ce noeud regroupera des internautes (=plus sont indice pagerank est grand). Plus précisément le site avec le plus grand pagerank est affiché en rouge avec un grand rayon, tous les autres pages auront ,proportionnellement des cercles plus petits et un rouge moins marqué tendant progressivement vers le jaune plus le pagerank sera faible... Les exemples du paragraphe suivant vous aideront à comprendre la signalétique utilisée dans ce démonstrateur.

Quelques exemples d'analyse pagerank

Tout d'abord il est à noter que cette analyse n'est pas aussi intuitive qu'on puisse le penser. Voyez l'exemple de graphe ci-dessous :

Le résultat du pagerank n'est pas si simple à imaginer ...

Et des modifications simples peuvent amener à des résultats difficilement prédictible...

Un seul liens de plus entre 2 noeuds (qui est la seule différence entre les 2 graphes précédents) modifie considérablement le résultat.

Bref tout cela n'est pas si simple mais ce démonstrateur vous permettra quand même de comprendre quelques règles simples pour augmenter le pagerank d'un site...

Conseils pour augmenter le pagerank d'un site ...

Les liens entrants : toujours positifmais à des dégrés variables

Il est inutile de multiplier les liens provenant de sites avec un faible pagerank. Voir la partie droite du graphe ci-dessous, malgré 3 liens entrant, le site de de droite à un pagerank faible...

Un seul lien entrant, provenant d'un site ayant un pagerank élevé, est beaucoup plus efficace : voir l'exemple ci-dessous.

Notez que la page « donnant » le lien (en bas au milieu) ne perd pas vraiment d'indice pagerank (en tout cas proportionnellement aux autres, et c'est cela qui compte).

Ces liens entrant sont d'autant plus intéressant que le nombre de liens sortant de la page d'origine sont peu nombreux.

La page en bas à droite bénéficie moins du lien entrant provenant de la page qui est a sa gauche (par rapport à la figure précédente) car cette page à maintenant plus de liens sortant.

Les liens sortant : positif ou négatif, selon la topologie

Négatif (si si c'est possible...)

Contrairement à ce qui est souvent cru, certain liens sortant peuvent faire baiser l'indice pagerank d'une page, en tout cas d'un point de vue théorique. Voyez l'exemple ci-dessous :

et après l'ajout d'un lien sortant :

La page en bas à droite à perdu une bonne partie de son indice pagerank... Il est à noter qu'il s'agit là d'un cas un peu particulier et qu'en général un lien sortant a peu de chance de réellement faire baiser le pagerank d'une page. Les exemples simplistes des deux figures précédentes sont peu représentatifs de la topologie du réseau des pages web.

Positif

Avant la création du lien :

après : Notez la différence de taille de la page à laquelle on a ajouté un lien sortant. Sont pagerank a bien augmenté, tout simplement parce que ce lien, retourne sur cette page après un court détour. Il est donc bon qu'un site relie bien ses pages entre elle (ce qui evidement en plus rend le parcours de l'internautre (réél) plus pratique. Cependant attention de ne pas en abuser et de ne pas générer une « link farm »

Les « link farm »

Des « link farm »sont parfois artificiellement crées pour accumuler artificiellement du pagerank. Il s'agit de pages reliées entre elles mais qui n'ont aucun liens vers d'autres pages, et aucune page « cul de sac ». Tout internaute (simulé par l'algorithme pagerank) y pénétrant n'en sort pas. Mettre un lien ver une telle page peu grandement faire baisser le pagerank d'une page et de celles qui y amène. Dans le schéma ci-dessous le réseau de gauche est un réseau « normal », celui de droite une « link farm » :

Avant le lien vers la « linkfarm »

Notez que cette configuration de « link farm » est artificielle (générée par des webmaster peu scrupuleux), pour des pages réelle il y a toujours des liens sortant vers le reste du réseau. Dans l'exemple ci-dessous, un seul lien sortant de la « link farm » retablit la situation.

C'estpourquoi les moteurs de recherche identifient ces sous-réseau particuliers (en remarquant qu'il sont isolé du reste du web) pour les pénaliser.

En résumé

Il est évidement malsain de faire des pages web sans aucun lien sortant ou ne reliant que des pages du même site, car cela forme ce qu'on appelle des « link farm » ce qui est fortement pénalisé par les moteur de recherche (si bien entendu ils s'en rendent compte...). En pratique il n'y a donc pas besoin d'avoir une réelle politique technique de liens sortants si ce n'est que ces liens soient intéressant pour l'internaute. Pour les liens entrant, plus il y en a mieux c'est. Il ne sont cependant pas tous aussi facile à générer et ils n'apportent pas tous le même gain cela dépend du pagerank de la page originaire du lien ainsi que du nombre de lien sortant de cette page.

Quelques exemples

En appliquant ces règles voici le résultat de recherches de mots clés sur google-france. Ces mots clés correspondent à des articles de ce blog, cependant vous pourrez noter que nombre de ces requêtes pourraient assez légitimement ne pas donner ces articles en premier. Il est aussi à noter que, très certainement, une partie du pagerank de ce blog est en partie héritée du site « www.esiea.fr ».

Voici une liste de requêtes sur Google où ce blog est très bien classé alors qu'il existe des pages certainement plus légitimes :

• « stratégie virus informatique »

• « création de map pour tremulous »

• « reconstruction de document »

• « utilisateur 2.0 »

• « logiciel de detection de fraude »

• «  limitation de la loi de Moore  »

Merci de voter pour cet article, qu'il vous ai plu ... ou non...