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.
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.
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 :
%% 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);
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 :
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.
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.
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.
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 :