Comment calculer le page rank ? 14


Sommaire

Madeline
Sur twitter

Cet article n’a rien de révolutionnaire, je voulais juste partager un document excel qui permet de calculer le pagerank pour un site de 12 pages. Pour plus de pages, il suffit de changer les formules et adapter un peu le tableau. C’est donc plus ludique qu’autre chose. Si vous souhaitez en savoir plus sur le pagerank, pour calculer le page rank interne sur un site de plus grande ampleur, je vous encourage à suivre les formations des frères peyronnet, que ce soit les masterclass ou bien les ix-labs.

Pour faire la démonstration, je me suis inspirée d’un vieil article « Comment Google classe les pages ? » paru sur le CNRS.

Pour ne pas faire durer le suspens, le tableau final est ici : démonstration calcul du page rank

On imagine donc ce site web de 12 pages, avec cette structure :

Je ne prends pas celui qui a la Terre comme image de fond parce qu’il manque un lien (et qu’elle est un peu kitsch). Le lien vers de la page 5 vers la page 7 n’est pas présent, alors qu’il doit l’être.

Un site web est donc un graphe orienté, chaque page est un nœud, chaque lien est une arête.

Calculer le nombre de liens entrant

Se dire que la page la plus populaire est celle qui accueille le plus de liens entrant est une fausse bonne idée. C’est indicateur est trop facilement manipulable.

Cela donne ceci sur excel :

PR-comptagenaif

Sur chaque ligne, on note les liens sortants. Sur chaque colonne, on a donc les liens entrants. Ici, les pages 1 et 9 seraient les plus populaires. Or, la structure laisse penser que ce devrait être la page 5.

Calculer en pondérant les liens entrants par les liens sortants

2e idée simple pour essayer de faire sortir les pages importantes : donner du poids à chaque lien. Chaque page ne reçoit pas un lien, mais 1 lien divisé par le nombre de liens sortant de cette page.

La page 1 a 4 liens sortants, chaque lien vaut donc 1/4 = 0.25.

PR-comptagepondere

Ce n’est toujours pas top car facilement manipulable. On a toujours les pages 1 et 9 qui sont les mieux « notées ». Le classement ne change pas trop par rapport au 1er tableau.

Le page rank : un modèle récursif

C’est ici que les choses se compliquent. La formule du pagerank initiale est maintenant connue :

pr-formuleoù PR est e pagerank, DF est le Damping Factor, N le nombre de pages, Nb le nombre de liens sortants.

Dans le tableau, j’ai juste inversé car DF = 0.15 et non 0.85. Mais ca revient au même, il faut juste inverser DF et 1-DF.

Ceux qui font des maths remarqueront que le pagerank est en fait une probabilité, donc un nombre compris entre 0 et 1. Le pagerank est la probabilité pour le surfeur aléatoire de tomber sur la page.

Le page rank d’une page est égal à la somme des pagerank des pages faisant des liens divisés par le nombre de liens sortant, avec également un damping factor, c’est à dire la probabilité que l’internaute ne suive pas du tout les liens présents sur la page.

On est bien avancé mais ce n’est pas évident à calculer. Car pour calculer le pagerank d’une page, il faut connaitre le pagerank des autres, du coup, on se trouve bêtement coincé : comment caculer le pagerank initial ??

On va faire un ensemble d’itération. Autrement dit, on imagine que le surfeur que nous appellerons Brice se trouve sur la page 1. C’est la 1er ligne du tableau « parcours surfeur aléatoire ».

Ensuite, nous allons nous aider du tableau « probabilité surfeur », qui calcule la probabilité d’aller sur une autre page. Si Brice est sur la page 1, il a 0.225 chance d’aller sur la page 2, soit 0.15/12 + (1-0.15)*1/4 . Ou bien autrement dit, Brice a 0.225 chance d’arriver sur la page 2 en venant de la page 1.

0.15, c’est le DF, 12, c’est le nombre de pages, 1 c’est le lien présent et 4 c’est le nombre de liens sortants. Pour les pages où il n’y a pas de liens, la probabilité est de 0.0125, soit 0.15/12 (pour l’autre partie du calcul, on multiplie par 0, elle est donc annulée).

Les probabilités d’arriver sur une page

PR-proba

Pour calculer le parcours du surfeur aléatoire, on a un point de départ, la page 1 (c’est arbitraire). Donc il 100%  de chance d’être sur la page 1 parce qu’on a décidé arbitrairement de commencer ici. Il faut bien commencer quelque part.

Ensuite, pour la 1ère itération, on calcule la probabilité d’arriver sur la page 1, la page 2, etc.

En gros, on multiplie la probabilité du début par les probabilités d’arriver sur la page 1 :

1*0.0125+0*0.225+0.0.225+0*225+0*0.0125, etc.

Sur excel, on multuplie la 1ere ligne du tableau parcours surfeur aléatoire par la 1ère colonne du tableau probabilité surfeur aléatoire, et on fait la somme de ces produits. Et ainsi de suite.

 Le parcours du surfeur aléatoire PR-surfeur

On remarque qu’après un certain nombre d’itération (21 ici), les nombres se stabilisent, ils convergent.

PR-convergence

Voilà, c’est comme cela qu’on arrive au pagerank des pages. Et enfin, c’est bien la page 5 qui a le score plus élevé.

Bon, j’espère ne pas m’être trompée dans les calculs mais ca avait l’air cohérent avec l’article cité précédemment. Après ce n’est pas trop visuel comme représentation, mieux vaut utiliser Gephi pour mieux se rendre compte de la distribution du page rank au sein d’un site.

 

 


Laissez un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

14 commentaires sur “Comment calculer le page rank ?

    • Madeline Auteur de l’article

      Je connais mal gephi.
      Honte à moi (ou pas) mais pour le moment le me contente des fusion tables de google drive (avec les limites de volumétrie qu’on connait).
      Mais pourquoi pas, j’ai pas mal d’idées d’articles encore. Il faut juste du temps 🙂

  • LeMoussel

    Bonjour,

    Rapide contrôle avec mon outil perso. de calcul de Page Rank, et je te rassure (si besoin est), tes résultats sont correctes.
    Excell est utilisé dans ton article à titre pédagogique. Pour le calcul sur des centaines voir des milliers de liens, il faudra passer/utiliser autre chose 🙂

  • Simon Georges

    Je confirme que l’algo du PageRank est implémenté dans Gephi et fonctionne plutôt bien.
    Il suffit de l’alimenter avec la liste des liens internes (provenant d’un outil de crawl type Screaming Frog) et hop, le PR des pages est calculé.

    • Madeline Auteur de l’article

      Sinon, Netpeak Spider le calcule aussi. On peut meme cacluler le page rank sans tenir compte des liens sitewide. C’est pratique 🙂

  • HM

    Calcul direct possible !
    x=ProduitMatrice(Inverse(I-(1-m)A);Ligne_I)*m

    x pagerank recherché des pages (à normaliser éventuellement entre 0 et 1), vecteur colonne après calcul

    Scalaire m=0.15 par exemple
    I : matrice identité, avec 1 sur la diagonale
    A : votre matrice de liens, normalisée par ligne, somme des lignes=1
    Inverse(I-(1-m)A) : inverse de la matrice I-(1-m)A
    Ligne_I : vecteur ligne avec les 12 termes=1

    ProduitMatrice(Inverse(I-(1-m)A);Ligne_I) : produit de la matrice Inverse(I-(1-m)A) par le vecteur ligne : Ligne_I

    N° x Total: 12.00 x Normalisés(/12)
    1 1.44 0.120
    2 0.79 0.066
    3 0.79 0.066
    4 0.79 0.066
    5 1.80 0.150 page avec le score le plus élevé
    6 0.66 0.055
    7 1.22 0.102
    8 0.66 0.055
    9 1.44 0.120
    10 0.79 0.066
    11 0.79 0.066
    12 0.79 0.066