PageRank Random Surfer

Introduction

Dans le papier original de Google, Sergey Brin et Lawrence Page affirme que le le PageRank peut être considéré comme un modèle du comportement des utilisateurs :

Le PageRank peut être considéré comme un modèle de comportement de l'utilisateur. Nous supposons qu'il existe un "surfeur aléatoire" à qui l'on donne une page Web au hasard et qui continue à cliquer sur les liens, sans jamais appuyer sur "retour", mais qui finit par se lasser et passe à une autre page aléatoire. La probabilité que le surfeur aléatoire visite une page est son PageRank. Et le facteur d'amortissement d est la probabilité qu'à chaque page, le "surfeur aléatoire" se lasse et demande une autre page aléatoire.

Cette page compare l'algorithme du PageRank de Google avec un surfeur aléatoire sur quelques exemples afin de vérifier que les résultats sont identiques. Nous ne détaillerons pas ici l'algorithme du PageRank qui est déjà décrit sur cette page.

Matrice d'adjacence

L'algorithme du surfeur aléatoire a été implémenté avec MATLAB. Le réseau est décrit par une matrice d'adjacence qui représente les liens entre les pages :

$$ A = \left[ \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} \right] $$

La matrice d'adjacence ci-dessus décrit le graphe dirigé suivant :

Les valeurs sur chaque nœud représentent le PageRank déjà calculé avec le l'algorithme de Google présenté sur cette page.

L'algorithme du surfeur aléatoire

Pour mettre en œuvre l'algorithme du surfeur aléatoire, commençons par le vecteur ci-dessous qui représente le nombre de visites pour chaque page (nœud du graphe). N est le nombre de nœuds (ici N=3) :

Visits = zeros(N,1);

Définissons la page de départ que l'internaute a choisie au hasard :

Page = randi(N);

Définissons \(d\N) le facteur d'amortissement, c'est-à-dire la probabilité qu'à chaque page le surfeur se lasse et demande une nouvelle page tirée au hasard.

d=0.85;

L'algorithm est relativement simple, ici, nous l'exécutons sur 1000 itérations. À chaque pas :

le nombre de visites est incrémenté
on choisit aléatoirement une nouvelle page parmi les liens sortants de la page courante
on vérifie si le surfeur se lasse et choisit une nouvelle page élaétoirement (damping factor)

%% Itearate 1000 times
for i=2:1000

    %% Increase visits for the current page
    Visits(Page,1) = Visits(Page,1) + 1;

    %% Randomly pick a new page from the links going out of the current page
    % L are pages linked by Page
    L=find (A(Page,:)==1);
    % Idx is the index of the link
    Idx = randi(length(L));
    % Next page
    Page = L(Idx);

    %% Damping factor, the surfer request another random page 15% of the time
    if (rand(1)>d)
        Page = randi(N);
    end
end

Au final, le PageRank est calculé en normalisant les visits :

$$ PageRank(i) = \dfrac{N*Visits(i)}{\sum_{i=1}^{N}{Visits(i)}} $$

Voici le code MATLAB :

PR = N*Visits/sum(Visits);

Résultats

En laissant le surfeur aléatoire voyager sur 1000 pages on obtient le résultat suivant :

$$ Visits = \left[ \begin{matrix} 215 \\ 402 \\ 382 \end{matrix} \right] $$

Le PageRank associé est :

$$ PageRank = \left[ \begin{matrix} 0.6456 \\ 1.2072 \\ 1.1471 \end{matrix} \right] $$

Premier constat : la PageRanks calculé avec le surfeur aléatoire est très proche de l'algorithme du PageRank de Google :

Nœud	PageRank	Random Surfer
1	0.6444	0.6456
2	1.1922	1.2072
3	1.1634	1.1471

Voici l'évolution des PageRanks avec l'algorithme random surfer :

L'algorithme a besoin d'envison 200 itérations pour converger alors que l'agorithme de Google en nécessite moins de 20 comme le montre la figure ci-dessous :

Discussion

Pas de liens sortants

Bien sûr, l'algorithme du "surfeur aléatoire" ne fonctionne pas si une page n'a pas de liens sortants. J'ai essayé de mettre en place une nouvelle version où le surfeur choisit une page aléatoire si la page actuelle n'a pas de lien. Mais les résultats ne sont pas cohérents avec l'algorithme du PageRank.

Pas de liens entrants

Un autre fait intéressant est le cas où une page n'a pas de lien entrants :

Comme précédemment, les valeurs sur chaque nœud représentent le PageRank déjà calculé avec le l'algorithme de Google présenté sur cette page.

Nœud	PageRank	Random Surfer
1	0.1500	0.1411
2	1.4595	1.4595
3	1.3905	1.3994

Les valeurs produites par le surfeur aléatoire sont cohérentes.

Graph non connexe

Le dernier cas est un graphe non connexe :

Comme le surfeur saute vers une nouvelle page 15% du temps, le graphe complet finit par être exploré :

Nœud	PageRank	Random Surfer
1	1	0.9690
2	1	0.9449
3	1	1.0370
4	1	1.0490

Notons que le surfeur aléatoire est moins précis que l'algorithme de Google.

Téléchargement

L'algorithme a été implémenté sous MATLAB. Tous les résultats présentés sur cette page ont été calculés avec le script ci-dessous :

pagerankRandomSurfer.m

Voir aussi

Dernière mise à jour : 03/10/2022