Exploration du Web et Structure des Liens

L'exploration du Web (web crawling) est le processus automatisé de découverte et de téléchargement de pages web en suivant les hyperliens, et la structure de liens qui en résulte forme un graphe que les systèmes de recherche parcourent et analysent.

Definition

L'exploration du Web est le parcours algorithmique du Web qui débute à partir d'URL de départ (seed URLs) et récupère de manière répétée des pages et en extrait leurs liens sortants pour découvrir davantage de pages, tandis que la structure des liens fait référence au graphe dirigé formé par les pages et les hyperliens entre elles.

Scope

Ce sujet aborde la manière dont les robots d'exploration (crawlers) récupèrent systématiquement les pages web et comment le graphe d'hyperliens du Web est structuré. Il traite de l'architecture des robots d'exploration, de la frontière d'URL et des contraintes de politesse, de la détection des doublons et quasi-doublons, de la fraîcheur et de la planification de la réexploration, ainsi que du respect de l'exclusion par les robots. Il couvre également les propriétés empiriques du graphe web, telles que sa structure en nœud papillon (bowtie) et sa distribution de degrés à queue lourde, qui éclairent à la fois l'exploration et l'analyse des liens. Il exclut l'utilisation des liens pour le classement, traitée sous PageRank et HITS.

Core questions

• Comment un robot d'exploration découvre-t-il, priorise-t-il et planifie-t-il les pages qu'il récupère ?
• Comment la politesse, l'exclusion par les robots et la charge du serveur sont-elles respectées lors de l'exploration ?
• Comment les pages dupliquées et quasi-dupliquées sont-elles détectées et gérées ?
• Comment la fraîcheur de l'exploration est-elle maintenue à mesure que les pages changent ?
• Quelle structure à grande échelle le graphe web présente-t-il ?

Key concepts

• robot d'exploration web / araignée (spider)
• frontière d'URL et ensemble de départ (seed set)
• politesse d'exploration et robots.txt
• détection des doublons et quasi-doublons
• fraîcheur et planification de la réexploration
• le graphe web
• structure en nœud papillon (bowtie)
• distributions des degrés entrants et sortants

Key theories

Architecture des robots d'exploration et la frontière d'URL

Un robot d'exploration maintient une frontière d'URL à récupérer, applique des politiques de priorisation et de politesse, analyse les pages récupérées pour en extraire de nouveaux liens, et suit les pages visitées, équilibrant la couverture, la fraîcheur et les limites de ressources.

Structure macroscopique du graphe web

Des études empiriques montrent que le graphe de liens du Web possède une forme caractéristique en nœud papillon (bowtie) avec un grand cœur fortement connecté, ainsi que des composants entrants et sortants, et un degré entrant à queue lourde, ce qui contraint l'accessibilité et éclaire la stratégie d'exploration.

Clinical relevance

L'exploration est l'étape d'acquisition de données de tout moteur de recherche web et des analyses web à grande échelle, de l'archivage et de la construction d'ensembles de données. La compréhension de la structure des liens guide une exploration efficace, aide à estimer la couverture et sous-tend les mesures d'autorité basées sur les liens utilisées dans le classement.

History

Les robots d'exploration web sont apparus avec les débuts du Web au milieu des années 1990 pour alimenter les index de recherche. Cho et ses collègues ont étudié l'exploration efficace et l'ordonnancement des URL en 1998, et l'étude de 2000 intitulée « graph structure in the web » a révélé la macrostructure en nœud papillon (bowtie) du Web. À mesure que le Web se développait, l'exploration est devenue une discipline de systèmes distribués à grande échelle, mettant l'accent sur la fraîcheur, la couverture et la politesse.

Key figures

• Andrei Broder
• Prabhakar Raghavan
• Junghoo Cho
• Hector García-Molina

Seminal works

• broder2000
• cho1998
• manning2008

Frequently asked questions

Qu'est-ce que la frontière d'URL dans un robot d'exploration ?

La frontière d'URL est la file d'attente des URL découvertes mais pas encore récupérées. Un robot d'exploration sélectionne de manière répétée des URL de la frontière selon des politiques de priorité et de politesse, récupère les pages, en extrait de nouveaux liens et ajoute les URL précédemment non vues à nouveau dans la frontière.

Que signifie la structure en « nœud papillon » (bowtie) du Web ?

Des études à grande échelle ont montré que le graphe web possède un grand cœur fortement connecté, un composant « entrant » de pages pouvant atteindre le cœur, un composant « sortant » accessible depuis celui-ci, ainsi que des ramifications (tendrils) et des parties déconnectées, le tout ressemblant à un nœud papillon (bowtie). Cette forme influence les pages qu'un robot d'exploration peut atteindre à partir de points de départ (seeds) donnés.