Estimating Absolute Web Crawl Coverage From Longitudinal Set Intersections

1. Problématique

L'archivage du web vise à préserver des portions du web, mais quantifier l'exhaustivité (la couverture) d'un crawl spécifique reste un défi majeur.

• La limite fondamentale : Un crawl isolé ne permet pas de déterminer sa propre couverture $c = M/N$, où $M$ est le nombre d'URLs collectées et $N$ la taille totale de l'espace web crawlable (inconnue).
• Limites des approches existantes :
  • Les méthodes comparatives (ex: Bharat & Broder, 1998) ne fournissent que des tailles relatives entre plusieurs moteurs de recherche, sans donner de fraction absolue du web total.
  • Les approches basées sur des entités nécessitent des jeux de données de vérité terrain externes (ground truth) spécifiques au domaine.
  • Les cadres de qualité (ex: SHARC) évaluent la cohérence temporelle mais pas la couverture globale du domaine.
• Objectif : Développer une méthode pour estimer la couverture absolue d'un crawl en utilisant uniquement les données longitudinales de l'archive elle-même (c'est-à-dire les données de plusieurs crawls successifs), sans aucune référence externe.

2. Méthodologie

Les auteurs proposent une approche basée sur l'analyse des intersections d'ensembles d'URLs entre des crawls successifs, modélisée par un processus d'urne.

A. Le Modèle d'Urnne

Le modèle suppose une population de $N$ URLs uniques. Le temps avance par étapes discrètes (crawls successifs). À chaque étape, deux processus se produisent :

1. Turnover (Renouvellement) : Une fraction $(1-\alpha)$ des URLs existantes est retirée et remplacée par de nouvelles URLs, maintenant la taille totale $N$ constante. Le paramètre $\alpha$ représente la persistance temporelle des URLs.
2. Échantillonnage : Le crawl collecte $M$ URLs tirées au hasard (sans remise) de la population actuelle.

B. Déduction Théorique

En considérant la probabilité qu'une URL capturée au temps $t=1$ survive jusqu'au temps $T$ et soit à nouveau capturée, les auteurs dérivent l'expression de l'intersection attendue entre deux crawls séparés par un temps $T$ :
$$E[|u_1 \cap u_T|] = M \cdot \alpha^{T-1} \cdot \frac{M}{N}$$

En normalisant par la taille du crawl $M$, on obtient la fraction d'intersection attendue $f(T)$ :
$$f(T) = c \cdot \alpha^{T-1}$$
Où :

• $c = M/N$ est la couverture absolue (fraction de l'espace web crawlable capturée).
• $\alpha$ est le taux de persistance annuelle des URLs.

C. Estimation par Régression

La méthode consiste à :

1. Calculer les intersections empiriques (mesure de contenance asymétrique $g(u_i, u_j) = |u_i \cap u_j| / |u_i|$) entre toutes les paires de crawls longitudinaux.
2. Appliquer une régression linéaire sur les valeurs logarithmiques de ces intersections en fonction de la différence de temps ($\Delta t$).
3. Extrapolation :
   • L'ordonnée à l'origine (intercept) de la régression (pour $\Delta t = 0$) donne l'estimation de la couverture $c$.
   • La pente de la régression donne le taux de décroissance $\alpha$ (taux de turnover).

3. Contributions Clés

1. Estimation Absolue sans Vérité Terrain : C'est la première méthode capable d'estimer la couverture absolue ($c$) d'un crawl en utilisant uniquement ses propres données longitudinales, éliminant le besoin de jeux de données externes ou de comparaison avec d'autres crawlers.
2. Modélisation Théorique : Introduction d'un modèle d'urne simple pour décrire la dynamique des crawls web, reliant les intersections temporelles à la taille de la population sous-jacente.
3. Interprétation de l'Auto-Intersection : Démonstration que l'intersection d'un crawl avec lui-même (extrapolée à $\Delta t = 0$) correspond à la fraction d'échantillonnage $c$, même si le processus de crawl n'est pas parfaitement uniforme (sous certaines conditions de biais).
4. Diagnostic de Biais : Le modèle permet d'isoler un coefficient de biais ($R_{ij}$) pour détecter si le crawl revisite systématiquement les mêmes sous-graphes (corrélation positive) par rapport à un échantillonnage uniforme théorique.

4. Résultats (Étude de Cas : Web Académique Allemand)

Les auteurs ont appliqué leur méthode à l'archive du German Academic Web (GAW), composée de 15 crawls semi-annuels réalisés entre 2013 et 2021 (environ 100 millions d'enregistrements au total).

• Couverture Estimée : Le modèle estime que chaque crawl capture environ 46 % de l'espace web académique allemand crawlable ($c \approx 0.46$).
• Persistance Temporelle : Le taux de persistance annuel des URLs est estimé à $\alpha \approx 0.73$, ce qui correspond à un taux de renouvellement (turnover) d'environ 27 % par an. Cela implique une demi-vie des URLs d'environ 2,2 ans, cohérent avec les études antérieures (Koehler, 2002).
• Évolution Temporelle : L'analyse des régressions par crawl montre une tendance à la hausse de la couverture au fil du temps (de 2013 à 2021), suggérant une amélioration de l'efficacité du crawl ou une réduction de la taille de la population cible.
• Validation : La régression sur les données réelles ($R^2 = 0.95$) correspond parfaitement aux simulations stochastiques du modèle d'urne, validant la robustesse de l'approche.

5. Signification et Implications

• Outil Autonome pour les Archivistes : Cette méthode offre aux opérateurs d'archives un moyen interne et indépendant d'évaluer la complétude de leurs données sans dépendre de ressources externes coûteuses ou de comparaisons inter-archives.
• Fiabilité pour les Tâches en Aval : Connaître la fraction de couverture (ex: 46 %) permet aux chercheurs d'évaluer la confiance qu'ils peuvent accorder aux données pour des tâches comme l'entraînement de modèles de langage (LLM) ou l'analyse sociologique.
• Gestion de la Fréquence de Crawl : L'analyse de la stabilité temporelle aide à décider de la fréquence optimale des crawls (régime de remplacement vs régime de croissance).
• Limites et Avenir : La méthode suppose une taille de population relativement stable et un échantillonnage quasi-uniforme. Elle mesure la couverture au niveau des URLs, pas du contenu. Des extensions futures pourraient intégrer des pondérations pour les biais de crawl (approche basée sur le réseau) ou combiner l'intersection d'URLs avec des mesures de similarité sémantique (MinHash).

En conclusion, cet article fournit un cadre mathématique simple mais puissant pour transformer les données temporelles d'une archive web en une estimation quantitative de sa propre exhaustivité.