En 1998, deux jeunes doctorants de l'université de Stanford, Larry Page et Sergey Brin (en collaboration avec Motwani et Wynograd) publiaient un article intitulé "The PageRank Citation Ranking: Bringing Order to the Web" présentant les résultats d'un nouvel algorithme permettant de classer les pages web selon leur popularité et montrant la précision de cet algorithme sur un nouveau moteur de recherche appelé ... Google !
L'idée de Page & Brin était d'utiliser les liens hypertextes entre les pages internet afin de simuler le comportement d'un utilisateur surfant aléatoirement sur le Web, en supposant alors que les pages vers lesquelles un "random surfer" se rendra le plus souvent sont les pages les plus importantes du réseau (et donc les plus pertinentes). Vous n'avez rien compris ? Prenons alors un exemple.
Supposons qu'il n'existe que 6 sites sur internet, appelé "A","B","C","D","E" et "F" , composé d'une seule page et traitant d'un même sujet. Pour simplifier, supposons que chaque site contienne au moins un lien vers un (ou plusieurs) autre site du réseau :
- Le site A contient un lien vers les sites "B", "C" et "E" (3 liens sortants)
- Le site B contient un lien vers le site "F" (1 lien sortant)
- Le site C contient un lien vers les sites "A" et "E" (2 liens sortants)
- Le site D contient un lien vers les sites "B" et "C" (2 liens sortants)
- Le site E contient un lien vers les sites "A", "B", "C", "D" et "F" (5 liens sortants)
- Le site F contient un lien vers le site "E" (1 lien sortant)
La grande question est alors : comment classer les sites ci-dessus du plus populaire au moins populaire ? Il est possible de représenter ce réseau en considérant chaque site web comme un noeud (6 noeuds) et chaque lien hypertexte comme un lien dirigé (14 liens). Graphiquement, cela nous donne donc ça (graphique réalisé sous Gephi):
Pour réaliser une approximation du PageRank de chaque site web, il est possible d'utiliser une méthode de Monte Carlo pour simuler le comportement d'un utilisateur sur le web (voir par exemple "Fast Incremental and Personalized PageRank"). Et dans le fond, ce n'est pas super complexe ! La première étape consiste à supposer qu'un utilisateur tombe au hasard sur l'une des 6 pages web de notre galaxie. Ensuite, cet utilisateur suit aléatoirement un lien présent dans la page, puis continue de suivre aléatoirement un lien sur la page suivante... et ainsi de suite.
Par exemple, supposons que notre utilisateur aléatoire tombe en premier sur la page "B". Cette page n'ayant qu'un seul lien sortant, l'utilisateur va ensuite forcément se rendre sur la page "F". Une fois sur cette page, idem, étant donné qu'il n'y a qu'un seul lien sortant, l'utilisateur va ensuite aller sur la page "E". Arrivé sur la page "E", il va cliquer aléatoirement sur un des liens présents : comme il existe 5 liens, chaque lien a une probabilité de 20% d'être cliqué. Supposons qu'il tombe alors sur la page "C", il va ensuite cliquer au hasard soit sur la page "A" soit sur la page "E" (probabilité 50%). Et ainsi de suite, notre utilisateur va se balader de pages en pages, en faisant son petit tour du net. A chaque fois que l'utilisateur tombe sur une page donnée, cette page gagne un point. Et à la fin, la page ayant le plus de point est alors la page la plus populaire du réseau !
En répétant ce processus des centaines de fois et en supposant que le processus s'arrête sous certaines conditions (Page & Brin conseillent que dans 15% des cas, le processus reparte sur un noeud aléatoire), il est alors possible d'approximer le fameux PageRank de Google. Un extrait du papier précédent résume cela de manière plus scientifique :
Histoire de s'amuser un peu, tentons de coder tout cela en Python et de calculer le PageRank de chaque site web. Nous allons donc tout d'abord définir les différents noeuds (variable "Websites") et les liens entre les différents noeuds (variable "Hypertext"). Ensuite, nous allons lancer 1000 "random walks" commençant aléatoirement sur l'un des 6 sites web, puis "jumpant" via un lien vers un site connecté avec une probabilité de 85% ou s'arrêtant avec une probabilité de 15%. En codant (salement) cette chose, cela nous donne donc :
import random
Hypertext = {}
Walk_Number = {}
Total_Walk = 0
Websites = ["A","B","C","D","E","F"]
Hypertext["A"] = ["B","C","E"]
Hypertext["B"] = ["F"]
Hypertext["C"] = ["A","E"]
Hypertext["D"] = ["B","C"]
Hypertext["E"] = ["A","B","C","D","F"]
Hypertext["F"] = ["E"]
Walk_Number["A"] = 0
Walk_Number["B"] = 0
Walk_Number["C"] = 0
Walk_Number["D"] = 0
Walk_Number["E"] = 0
Walk_Number["F"] = 0
i = 0
while i < 1000:
x = random.choice(Websites)
while random.random() < 0.85:
Walk_Number[x] = Walk_Number[x] + 1
Total_Walk = Total_Walk + 1
x = random.choice(Hypertext[x])
i = i + 1
print Walk_Number, Total_Walk
Ce calcul nous permet de voir combien de fois un utilisateur passera sur chacun des sites Web, en supposant qu'il arrive sur un site Web aléatoirement puis clique aléatoirement sur un lien de la page, et ainsi de suite. Dans l'exemple ci-dessus, voici les résultats de la variable Walk_Number
{'A': 748, 'B': 800, 'C': 823, 'D': 454, 'E': 1628, 'F': 1092} - Total_Walk = 5545
Cela signifie donc que l'utilisateur s'est rendu au total sur 5545 pages, et qu'il est allé 748 fois sur la page A, 800 fois sur la page B, 1628 fois sur la page E et ainsi de suite. Pour calculer le PageRank à partir de ces données, il suffit de diviser les valeurs précédentes par le nombre total de page visitées, ce qui nous donne alors :
{'A': 0.1349, 'B': 0.14427, 'C': 0.1484,'D': 0.08188, 'E': 0.2936, 'F': 0.1969}
Bien évidemment, une nouvelle simulation donnera des résultats légèrement différents, mais il peut être prouvé mathématiquement que les valeurs convergent. La page la plus populaire dans notre réseau est alors la page E, suivie de la page F, de la page C ... et la moins populaire est la page D, ce qui est d'ailleurs assez logique car seule la page E a un lien vers D, et de plus E a beaucoup de liens sortants donc la puissance du lien est divisée. En modifiant la taille des noeuds selon le PageRank, notre réseau devient donc:
Conclusion : L'algorithme PageRank peut être utilisé pour calculer la popularité des publications académiques (voir "Finding scientific gems with Google’s PageRank algorithm") ou pour identifier les utilisateurs influents sur un réseau social (voir "What is Twitter, a Social Network or a News Media?"). Le Captain' lui l'utilise dans le second cas, pour pondérer les messages sur les réseaux sociaux en fonction de l'influence de l'émetteur. Quelques lignes de codes, et le tour est joué (enfin pour des réseaux de petites tailles et statiques... lorsque le nombre de noeuds et de liens augmentent fortement ou bien si une mise à jour fréquente est nécessaire, des problématiques de temps de calcul que le Captain' ne maitrise pas trop ont tendance à vite apparaître) !