Lorsque les moteurs de recherche comme Google affichent des résultats de recherche, ils positionnent les pages plus « importantes » et de meilleure qualité plus haut dans les résultats que les pages moins importantes. Une heuristique pourrait être qu'une page « importante » est une page vers laquelle de nombreuses autres pages mènent, car il est raisonnable d'imaginer que davantage de sites créeront des liens vers une page web de meilleure qualité que vers une page de moindre qualité. C'est pour cette raison que l'algorithme PageRank a été créé par les cofondateurs de Google, dont Larry Page, qui a donné son nom à l'algorithme. Le PageRank est un algorithme de Google qui évalue l’importance des pages web. Il a été développé par Larry Page et Sergey Brin à l'Université de Stanford en 1996, dans le cadre d'un projet de recherche visant à créer un nouveau type de moteur de recherche, différent des acteurs alors dominants comme AltaVista de DEC. Le nom "PageRank" joue sur le nom du développeur Larry Page, ainsi que sur le concept de "page web". Le PageRank est un algorithme d'analyse de liens qui attribue une pondération numérique à chaque élément d'un ensemble de documents hyperliés, tel que le World Wide Web, dans le but de « mesurer » son importance relative au sein de l'ensemble. L'algorithme peut être appliqué à toute collection d'entités avec des citations et des références réciproques. Le PageRank est également célèbre pour avoir été la pierre angulaire de la réussite de Google en tant que moteur de recherche révolutionnaire.
Comprendre le PageRank : Le Modèle du Surfeur Aléatoire
Une façon de comprendre le PageRank est à travers le modèle du surfeur aléatoire, qui considère le comportement d'un surfeur hypothétique sur Internet qui clique sur des liens au hasard. Le modèle du surfeur aléatoire imagine un surfeur qui commence sur une page web au hasard, puis choisit aléatoirement les liens à suivre. Une page web est un ensemble fixe de pages, avec chaque page contenant un ensemble fixe d'hyperliens, et chaque lien une référence à une autre page. Une page’s PageRank, alors, peut être décrit comme la probabilité qu'un surfeur aléatoire soit sur cette page à un moment donné. Après tout, s'il y a plus de liens vers une page particulière, il est plus probable qu'un surfeur aléatoire finisse sur cette page.
Pour formuler plus précisément ce que signifie se déplacer aléatoirement de page en page, le modèle propose une simulation du comportement d'un utilisateur naviguant sur le web en cliquant sur des liens au hasard. Par exemple, si le surfeur est sur la Page 2, il choisirait aléatoirement entre la Page 1 et la Page 3 pour la prochaine visite (les liens dupliqués sur la même page sont traités comme un seul lien, et les liens d'une page vers elle-même sont également ignorés). Si une page n'a pas de liens sortants, elle devient un "puits" et met fin au processus de navigation aléatoire.
Le Facteur d'Amortissement (Damping Factor)
Pour s'assurer que le surfeur peut toujours se rendre ailleurs dans le corpus de pages web, un facteur d'amortissement d est introduit dans le modèle. Avec une probabilité d (où d est généralement fixé autour de 0,85), le surfeur aléatoire choisira l'un des liens de la page actuelle au hasard. Avec une probabilité 1 - d, le surfeur "s'ennuie" et passe à une page aléatoire, c'est-à-dire qu'il choisit n'importe quelle page du corpus au hasard. Cette probabilité 1 - d est également répartie entre toutes les pages possibles. Cette approche permet d'éviter que le surfeur ne reste piégé dans un cycle fermé de pages qui ne se lient qu'entre elles, ce qui l'empêcherait de visiter d'autres pages. En introduisant ce facteur, le processus est capable d'atteindre toutes les pages du web, même celles qui n'ont pas de liens entrants directs. Le facteur d'amortissement ajuste la valeur dérivée à la baisse. La probabilité résiduelle, d, est généralement fixée à 0,85, estimée à partir de la fréquence à laquelle un internaute moyen utilise la fonction de signet de son navigateur.
PageRank comme Chaîne de Markov
Une façon d'interpréter ce modèle est comme une chaîne de Markov, où chaque page représente un état, et chaque page a un modèle de transition qui choisit parmi ses liens au hasard. Le processus aléatoire qui décrit le comportement du surfeur est connu sous le nom de chaîne de Markov. Les chaînes de Markov sont largement applicables, bien étudiées et possèdent de nombreuses propriétés remarquables et utiles. Par exemple, un théorème de limite fondamental pour les chaînes de Markov stipule que notre surfeur pourrait commencer n'importe où, car la probabilité qu'un surfeur aléatoire se retrouve finalement sur une page particulière est la même pour toutes les pages de départ ! Peu importe où le surfeur commence, le processus finit par se stabiliser jusqu'à un point où une navigation supplémentaire ne fournit plus d'informations.
Lire aussi: S'initier à l'Aviron : Le Guide
En échantillonnant aléatoirement des états de la chaîne de Markov, nous pouvons obtenir une estimation du PageRank de chaque page. Nous pouvons commencer par choisir une page au hasard, puis continuer à suivre les liens au hasard, en gardant une trace du nombre de fois où nous avons visité chaque page. On pourrait imaginer qu'un surfeur aléatoire ne fait que cliquer sur des liens, et le PageRank d'une page est la probabilité que ce surfeur se trouve sur cette page à un instant donné.
Le Surfeur Raisonnable
Le concept de surfeur raisonnable est une évolution du surfeur aléatoire. Il représente un utilisateur qui navigue de manière plus réaliste, en suivant des liens pertinents et en revenant parfois à la page précédente. Ce modèle reflète mieux le comportement réel des internautes et influence la façon dont Google calcule l’importance des pages. Un surfeur plus intelligent qui saute de manière probabiliste d'une page à l'autre en fonction du contenu des pages et des termes de requête recherchés par le surfeur. Ce modèle est basé sur un score PageRank d'une page dépendant de la requête, qui, comme son nom l'indique, est également fonction de la requête.
Calcul du PageRank : Formule Itérative et Implémentation
Le PageRank d'une page, PR(p), peut également être défini à l'aide d'une expression mathématique récursive. Il s'agit de la probabilité qu'un surfeur aléatoire finisse sur cette page. Comment définir PR(p) ? Eh bien, nous savons qu'il y a deux façons pour un surfeur aléatoire de se retrouver sur la page :
- Avec une probabilité
1 - d, le surfeur a choisi une page au hasard et a abouti sur la pagep. - Avec une probabilité
d, le surfeur a suivi un lien d'une pageivers la pagep.
La première condition est assez simple à exprimer mathématiquement : c'est 1 - d divisé par N, où N est le nombre total de pages dans l'ensemble du corpus. Cela s'explique par le fait que la probabilité 1 - d de choisir une page au hasard est répartie uniformément entre les N pages possibles.
Pour la deuxième condition, nous devons considérer chaque page possible i qui contient un lien vers la page p. Pour chacune de ces pages entrantes, soit NumLinks(i) le nombre de liens sur la page i. Chaque page i qui pointe vers p a son propre PageRank, PR(i), représentant la probabilité que nous soyons sur la page i à un moment donné. Et puisque de la page i, nous nous déplaçons vers n'importe lequel des liens de cette page avec une probabilité égale, nous divisons PR(i) par le nombre de liens NumLinks(i) pour obtenir la probabilité que nous étions sur la page i et avons choisi le lien vers la page p.
Lire aussi: Conseils de sécurité pour la navigation de nuit
Ceci nous donne la définition suivante pour le PageRank d'une page p :
PR(p) = (1 - d) / N + d * Σ (PR(i) / NumLinks(i))
Dans cette formule, d est le facteur d'amortissement, N est le nombre total de pages dans le corpus, i représente toutes les pages qui renvoient à la page p, et NumLinks(i) est le nombre de liens présents sur la page i.
Comment calculer les valeurs PageRank pour chaque page ? Nous pouvons le faire par itération : commencer par supposer que le PageRank de chaque page est 1 / N (c'est-à-dire, également susceptible d'être sur n'importe quelle page). Ensuite, utiliser la formule ci-dessus pour calculer de nouvelles valeurs PageRank pour chaque page, basées sur les valeurs PageRank précédentes. Si nous continuons à répéter ce processus, en calculant un nouvel ensemble de valeurs PageRank pour chaque page basé sur l'ensemble précédent de valeurs PageRank, les valeurs PageRank finiront par converger. Les fondateurs de Google, dans leur article original, ont rapporté que l'algorithme PageRank pour un réseau composé de 322 millions de liens (liens entrants et sortants) convergeait dans une limite tolérable en 52 itérations. La convergence dans un réseau de la moitié de cette taille prenait environ 45 itérations. En pratique, on peut s'attendre à ce qu'environ 50 à 100 itérations soient nécessaires pour que les valeurs convergent.
Implémentation Python : Le Fichier pagerank.py
Le fichier pagerank.py contient l'implémentation de cet algorithme. Il est conçu pour estimer le PageRank de chaque page en utilisant deux méthodes : l'échantillonnage (modèle du surfeur aléatoire) et la formule itérative.
Lire aussi: La Roche-de-Glun : festivités nautiques
Initialement, le fichier définit deux constantes : DAMPING qui représente le facteur d'amortissement et est initialement réglé à 0.85, et SAMPLES qui représente le nombre d'échantillons à utiliser pour la méthode d'échantillonnage.
La fonction main attend un argument de ligne de commande, qui sera le nom d'un répertoire contenant un corpus de pages web pour lesquelles nous souhaitons calculer les PageRanks. La fonction crawl prend ce répertoire, analyse tous les fichiers HTML qu'il contient et renvoie un dictionnaire représentant le corpus. Les clés de ce dictionnaire représentent les pages (par exemple, "2.html"), et les valeurs du dictionnaire sont un ensemble de toutes les pages liées par la clé (par exemple, {"3.html"}). La fonction main appelle ensuite la fonction sample_pagerank, dont le but est d'estimer le PageRank de chaque page par échantillonnage. La fonction prend comme arguments le corpus de pages généré par crawl, ainsi que le facteur d'amortissement et le nombre d'échantillons à utiliser. La fonction main appelle également la fonction iterate_pagerank, qui calcule également le PageRank pour chaque page, mais en utilisant la méthode de la formule itérative plutôt que par échantillonnage.
Fonction transition_model
Cette fonction génère un modèle de transition pour une page donnée. Sa signature est transitionModel(corpus, page, dampingFactor). Elle doit retourner un dictionnaire Python avec une clé pour chaque page du corpus. Chaque clé doit être mappée à une valeur représentant la probabilité qu'un surfeur aléatoire choisisse cette page ensuite.
Par exemple, si le corpus était {"1.html": {"2.html", "3.html"}, "2.html": {"3.html"}, "3.html": {"2.html"}}, la page était "1.html", et le damping_factor était 0.85, alors la sortie de transition_model devrait être {"1.html": 0.05, "2.html": 0.475, "3.html": 0.475}.
Si la page n'a pas de liens sortants, transition_model doit retourner une distribution de probabilité qui choisit aléatoirement parmi toutes les pages avec une probabilité égale. En d'autres termes, pour être juste avec les pages qui ne sont pas des puits, ces transitions aléatoires sont ajoutées à tous les nœuds du Web.
L'implémentation inclut cette logique : si la page a des liens, les probabilités sont réparties proportionnellement aux liens sortants et à la probabilité de saut aléatoire. Si la page n'a pas de liens, toute la probabilité est répartie également entre toutes les pages du corpus, simulant un saut aléatoire.
Fonction sample_pagerank
Cette fonction estime les valeurs PageRank en utilisant l'échantillonnage, c'est-à-dire la méthode du surfeur aléatoire. Sa signature est samplePageRank(corpus, dampingFactor, n). Elle prend le corpus, le facteur d'amortissement et le nombre d'échantillons n à générer.
Le retour de cette fonction est un dictionnaire Python avec une clé pour chaque page du corpus. Chaque clé est mappée à une valeur représentant le PageRank estimé de cette page (c'est-à-dire la proportion de tous les échantillons qui correspondaient à cette page).
Le processus commence par choisir une page aléatoire. Ensuite, pour chaque échantillon supplémentaire à générer, le surfeur choisit un lien de la page actuelle au hasard avec une probabilité d, et choisit une page quelconque au hasard avec une probabilité 1 - d. Le nombre de visites pour chaque page est compté et finalement normalisé pour obtenir les probabilités PageRank.
Fonction iterate_pagerank
Cette fonction estime le PageRank en utilisant la méthode itérative. Sa signature est iterate_pagerank(corpus, damping_factor). Elle doit retourner un dictionnaire Python avec une clé pour chaque page du corpus. Chaque clé doit être mappée à une valeur représentant le PageRank de cette page.
La fonction commence par initialiser le PageRank de chaque page à 1 / N, où N est le nombre total de pages. Elle calcule ensuite de nouvelles valeurs de PageRank de manière répétée, basées sur toutes les valeurs de PageRank actuelles, en suivant la formule de PageRank décrite précédemment. Le calcul s'arrête lorsque la différence totale entre les nouvelles valeurs de PageRank et les anciennes valeurs de PageRank est inférieure à une tolérance prédéfinie (par exemple, 0.00001), indiquant la convergence. Les valeurs sont ensuite normalisées pour que leur somme soit égale à 1.
Le calcul est fait de manière itérative ou algébrique. La méthode itérative peut être considérée comme la méthode d'itération de puissance. Le calcul de probabilité est effectué pour chaque page à un moment donné, puis répété pour le moment suivant.
Construction d'un Corpus pour l'Analyse PageRank : L'Exemple de Wikipédia
Un projet d'application du PageRank consiste à l'utiliser pour mesurer la popularité et la pertinence des pages Wikipédia via leurs liens internes. La première étape consiste à définir la page principale à partir de laquelle commencer l'exploration. Dans ce cas, la page "Python_(programming_language)" a été choisie. À partir de cette page, un corpus de 15 pages a été construit, limitant à un maximum de 5 liens pertinents par page, à l'aide d'un web scraper personnalisé.
Les Fonctions Clés de l'Extraction
Pour gérer la complexité et la taille du Web, plusieurs fonctions Python sont nécessaires pour construire et traiter le corpus :
normalize(text): Cette fonction prend un texte en entrée et retourne une version normalisée, en convertissant le texte en minuscules et en supprimant tous les caractères non alphanumériques.linked(startPage, maxLinkers=10): Cette fonction est conçue pour extraire les pages liées pertinentes d'une page Wikipédia donnée. Elle commence par obtenir le contenu de la page Wikipédia (par exemple,wiki.page(startPage)). Le résumé de la page est normalisé (normalizedSummary). Tous les titres de liens présents sur la page sont également normalisés. Un modèle d'expression régulière est préparé pour faire correspondre les titres normalisés dans le résumé. Seuls les liens dont le titre normalisé correspond à une partie du résumé sont conservés. De plus, les catégories de la page sont extraites et normalisées. Enfin, les liens pertinents sont filtrés en ne retenant que ceux qui contiennent ou sont contenus dans un mot-clé extrait des catégories. Les liens sont ensuite mélangés aléatoirement et un maximum demaxLinkerssont retournés.corpusBuilder(startPage): Cette fonction construit le corpus complet en explorant les pages à partir de lastartPage. Elle initialise un dictionnairecorpusvide et une listetoProcessavec lastartPage. Tant que la taille ducorpusest inférieure àmaxCorpuset qu'il y a des pages à traiter, la fonction extrait la page courante detoProcess. Si cette page n'est pas déjà dans lecorpus, elle appellelinked()pour obtenir les liens filtrés de la page courante, s'assurant d'exclure les auto-liens. Les liens de la page courante sont ensuite ajoutés aucorpuset aux pages à traiter.
L'un des défis lors de la construction du corpus était que de nombreuses pages contiennent des liens vers des articles non directement liés au sujet principal. Pour réduire ce bruit, un filtre en deux étapes a été appliqué : les liens n'étaient considérés comme valides que s'ils apparaissaient dans le résumé de l'article et s'ils étaient liés à l'une de ses catégories.
Analyse et Visualisation des Résultats du PageRank
Après avoir construit le corpus et appliqué les deux méthodes de calcul (échantillonnage et méthode itérative), on obtient deux distributions PageRank qui reflètent l'importance relative de chaque page au sein du corpus.
Il est important de noter qu'il existe des différences entre la popularité calculée par échantillonnage et celle obtenue par la méthode itérative. La méthode d'échantillonnage dépend du nombre de visites simulées : si l'on utilise trop peu d'échantillons, le résultat peut être bruité ou imprécis. En revanche, l'approche itérative applique directement la formule mathématique du PageRank, mettant à jour les valeurs jusqu'à ce que la différence entre les itérations soit négligeable, ce qui la rend généralement plus stable et fiable. En augmentant le nombre d'itérations, on obtient des estimations de plus en plus précises de la probabilité que le surfeur atterrisse sur chaque page (les PageRanks).
Représentation Graphique du Corpus
Une fois le corpus et les PageRanks calculés, il est souvent utile de visualiser comment les pages sont connectées entre elles. Pour ce faire, un graphique peut être conçu où chaque nœud représente une page Wikipédia, et les arêtes (flèches) indiquent les liens entre elles.
Une façon de comprendre l'importance d'une page est d'analyser sa relation avec les autres au sein du graphique. Pour ce faire, on peut tracer les liens entrants, les liens sortants et les connexions bidirectionnelles pour chaque nœud. Cela permet de visualiser quelles pages sont les plus influentes (recevant le plus de liens), lesquelles agissent comme des distributeurs de trafic (liant à beaucoup d'autres), et où des relations mutuelles entre les pages existent. Cette analyse complète les valeurs PageRank et offre une perspective structurelle du corpus.
Stratégies d'Optimisation (SEO) Basées sur les Principes du PageRank
Bien que le PageRank ait évolué et ne soit plus le seul facteur de classement, ses principes fondamentaux restent cruciaux pour le référencement naturel (SEO). L'algorithme de Google ne cesse d'évoluer pour mieux répondre aux besoins des utilisateurs, et le PageRank est toujours utilisé, mais comme l’un des nombreux signaux de classement.
Le Contenu de Qualité comme Fondement
Le contenu de qualité est le fondement d’une bonne stratégie PageRank. Si un blog culinaire souhaite améliorer son PageRank, il pourrait créer un guide complet sur « Les techniques de cuisson des pâtes » ou un article détaillé sur « Les 50 épices essentielles de la cuisine du monde ». Le meilleur netlinking ne compensera jamais un contenu médiocre.
Acquisition de Backlinks de Qualité
Le PageRank évalue non seulement le nombre de backlinks pointant vers une page, mais aussi la qualité de ces liens. Une page avec un PageRank élevé transmet plus de confiance via ses liens sortants qu’une page avec un PageRank faible. Les backlinks provenant de sites en rapport avec la thématique du site ont plus de poids dans la formule du PageRank. Il est crucial de se concentrer sur l’obtention de backlinks de sites de qualité dans votre thématique. Par exemple, contacter des podcasts culinaires populaires pour se proposer comme invité expert, ou créer une infographie originale sur un sujet d'actualité dans le secteur culinaire. Identifier les sites influents dans la thématique qui ont des sections de contenu invité et leur proposer des articles de haute qualité est une autre stratégie. Un petit nombre de backlinks de haute qualité vaut mieux qu’une multitude de liens de faible valeur.
Structure de Liens Interne Efficace
Une bonne structure de liens interne aide à distribuer la confiance efficacement sur un site. Il est recommandé de créer une hiérarchie claire pour le site et d'utiliser la page d’accueil et le menu principal pour lier vers les pages les plus importantes. Dans chaque article de blog, il est bénéfique de lier vers 2-3 articles connexes. Cela augmente le PageRank des pages cibles.
Le "Link Sculpting"
Le « link sculpting » consiste à contrôler la transmission de la confiance à travers les liens internes. Il s'agit d'identifier les pages les plus importantes en termes de conversion ou de trafic. L'attribut « nofollow » peut être utilisé sur les liens moins importants, comme ceux vers la politique de confidentialité ou les conditions d’utilisation, pour éviter de diluer le PageRank. Cependant, il ne faut pas abuser de cette technique. Google a également introduit les attributs rel="ugc" pour le contenu généré par les utilisateurs (comme les commentaires) et rel="sponsored" pour les publicités ou le contenu sponsorisé, pour fournir des indices supplémentaires sur la nature des liens.
Diversité et Naturel du Profil de Liens
Un profil de backlinks varié est plus naturel aux yeux de Google et augmente la probabilité d’un bon classement. Il faut éviter les pics soudains de backlinks, qui peuvent sembler suspects à Google, et varier le texte d’ancrage des backlinks pour un profil plus naturel. Participer à des événements culinaires conjoints, proposer des témoignages clients en échange de backlinks, ou s'engager dans des groupes et communautés liées à la cuisine sont des moyens d'obtenir des liens diversifiés.
Évolution et Applications Élargies du PageRank
Le PageRank a été influencé par l'analyse des citations, développée dès les années 1950 par Eugene Garfield à l'Université de Pennsylvanie, et par Hyper Search, développé par Massimo Marchiori à l'Université de Padoue. Il est à noter que la théorie PageRank soutient qu'un surfeur imaginaire qui clique aléatoirement sur des liens finira par arrêter de cliquer.
Les mathématiques du PageRank sont entièrement générales et s'appliquent à n'importe quel graphique ou réseau dans n'importe quel domaine. Ainsi, le PageRank est maintenant régulièrement utilisé en bibliométrie, en analyse de réseaux sociaux et d'information, et pour la prédiction de liens et la recommandation.
Au-delà du Web : Diverses Applications
Le PageRank a été utilisé pour quantifier l'impact scientifique des chercheurs. Les réseaux de citation et de collaboration sous-jacents sont utilisés conjointement avec l'algorithme PageRank afin de créer un système de classement pour les publications individuelles qui se propage aux auteurs individuels. Une utilisation similaire plus récente du PageRank est de classer les programmes doctoraux académiques en fonction de leurs dossiers de placement de leurs diplômés dans des postes universitaires. Une version du PageRank a récemment été proposée comme remplacement du facteur d'impact traditionnel de l'Institute for Scientific Information (ISI), et implémentée chez Eigenfactor ainsi qu'à SCImago.
Un robot d'exploration web (web crawler) peut utiliser le PageRank comme l'une des nombreuses métriques d'importance pour déterminer quelle URL visiter lors d'une exploration du web. Un des premiers articles de travail utilisés dans la création de Google est "Efficient crawling through URL ordering", qui discute de l'utilisation de plusieurs métriques d'importance différentes pour déterminer la profondeur et l'étendue de l'exploration d'un site par Google. Le PageRank peut également être utilisé comme méthodologie pour mesurer l'impact apparent d'une communauté comme la blogosphère sur l'ensemble du Web. En 2005, dans une étude pilote au Pakistan, le Structural Deep Democracy, SD2, a été utilisé pour la sélection des leaders dans un groupe d'agriculture durable appelé Contact Youth. Le SD2 utilise le PageRank pour le traitement des votes par procuration transitifs, avec des contraintes supplémentaires obligeant au moins deux procurations initiales par votant, et tous les votants sont des candidats par procuration.
#