Soutenance mémoire
Les moteurs de recherche aujourd’hui
DEPUIS quelques années, l’Internet, et le Web en particulier, ont subi de profondes transformations liées à de multiples changements d’ordresde grandeur. Toujours plus de données sur toujours plus de machines sont accessibles à toujours plus d’internautes. L’économie électronique s’est également développée, et ce qui n’était hier pour les entreprises commerciales qu’une simple vitrine expérimentale est devenu, souvent au prix d’essais malheureux, un secteur économique à part entière. Ces mutations ont généré de nouveaux comportements aussi bien au niveau des internautes que des administrateurs de site. Du côté des internautes, le problème qui est apparu consiste à se repérer au milieu des milliards de pages disponibles. L’utilisateur lambda veut avoir les moyens d’accéder à toutes les ressources offertes par le Web, et les méthodes habituelles (navigation par hyperliens à partir d’un portail, connaissance de la bonne adresse par des moyens extra-Web) ne suffisent plus. Du côté des sites se pose le problème symétrique de la visibilité. Un site, si bien conçu soit-il, n’a de valeur que s’il est fréquenté, tel l’arbre qui tombe dans la forêt. Ce problème de la visibilité a de multiples facettes, qui sont les mêmes que pour la visibilité dans le monde réel. La visibilité du site personnel de Monsieur Durand est pour lui l’assurance de pouvoir être connu ou contacté par les personnes qui le désirent. La visibilité d’un site commercial représente de l’argent. Être plus visible que ses concurrents permet d’acquérir une nouvelle clientèle à leurs dépens, ce qui, dans un marché encore limité mais en pleine expansion, est une condition quasi-nécessaire de survie. Si les deux problèmes de l’accessibilité et de la visibilité sont symétriques, ils ne font pas forcément bon ménage. Si un internaute veut manger des pommes, sa principale préoccupation va être de trouver des pages Web qui parlent de pommes, voire qui en vendent. De son côté, le site d’un amateur de poires va vouloir se faire connaître de l’internaute mangeur de pommes, si possible avant qu’il n’ait trouvé un site de pommes, pour essayer de le faire changer d’avis et de le convertir à la poire. Les moteurs de recherche ont pour but premier d’assurer l’accessibilité d’un maximum de pages Web aux internautes. Concrètement, parmi le plus grand choix possible de pages, le moteur doit renvoyer les pages répondant aux besoins de l’internaute, ce besoin étant exprimé au travers d’une requête. Mais ils sont de fait devenus aussi le principal média de visibilité pour les sites. Ce placement stratégique, à la croisée de l’internaute et du site, fait du moteur de recherche la pièce maîtresse du Web actuel, et il n’est pas étonnant de voir que la société Google, qui possède — à ce jour — le quasi monopole du secteur des moteurs de recherche, est maintenant cotée en bourse.
Connaître le Web
Une des premières qualités pour un moteur de recherche est d’avoir une base de données conséquente, autant d’un point de vue quantitatif que d’un point de vue qualitatif. Dans la partie I nous nous proposons de mettre en évidence la problématique que posent ces bases de données constituées par les moteurs de recherche. Nous commençons tout d’abord par tenter de définir le Web, ce qui, comme nous allons le voir lors du chapitre 1, n’est pas aussi facile qu’on pourrait le penser de prime abord. Ceci fait, nous pourrons au cours du chapitre 2 étudier ces sous-ensembles du Web que sont les crawls. Les crawls sont naturellement munis d’une structure de graphe que nous détaillerons lors du chapitre 3. Nous essaierons en particulier de mettre en perspective le modèle du nœud papillon, dont les conclusions sont trop souvent mal interprétées, et nous montrerons l’existence d’une très forte organisation en sites des pages Web liée à l’arbre de décomposition des URLs. Nous verrons en particulier que la structure canonique des sites permet de calculer en temps linéaire une bonne approximation d’une certaine décomposition en sites d’un graphe du Web.
Trouver les bonnes pages
Plus que la taille de sa base de donnée, c’est la façon dont un moteur de recherche va s’en servir qui va déterminer son efficacité. Alors que pour une requête donnée, la base de données va souvent contenir quelques dizaines de milliers de pages susceptibles de fournir une réponse adaptée, l’internaute va rarement aller au delà des 10 ou 20 premières réponses renvoyées par le moteur. Il est donc nécessaire d’opérer un tri parmi les réponses possibles afin d’extraire, de manière automatique, les quelques pages les mieux adaptées à une requête donnée. Les moteurs de recherche de première génération utilisaient des méthodes de pertinence lexicale et sémantique afin de réaliser ce tri : les premières pages renvoyées étaient celles qui, du point de vue de l’analyse sémantique, se rapprochaient le plus de la requête. Mais assez vite, le classement par pertinence a été dénaturé par le besoin de visibilité des sites. Beaucoup de sites se sont mis à étoffer le contenu sémantique de leurs pages à l’aide de techniques plus ou moins rusées et plus ou moins honnêtes, par exemple en surchargeant la page de texte blanc sur fond blanc. Très souvent, au lieu d’être renvoyé sur les pages les plus pertinentes, l’internaute se retrouvait alors sur des pages qui n’ont rien à voir avec sa requête, mais dont la volonté d’être visible est très grande. Pour contrer ces techniques, de nouvelles méthodes de classement ont été introduites, dans le but d’inférer l’importance des pages Web à partir de la structure de graphe formée par les pages connues. C’est l’une de ces familles de méthodes de classement, les PageRanks, qui sera étudiée dans la partie II. Le chapitre 4 rappellera quelques bases théoriques sur les chaînes de Markov, et développera plus particulièrement certains liens entre la théorie des graphes et celles des processus stochastiques nécessaires à une bonne compréhension du PageRank. Le chapitre 5 sera l’occasion de présenter un bestiaire quasi-exhaustif des algorithmes classiques de PageRank. Nous présenterons en particulier une vision du PageRank unifiée en terme d’interprétation stochastique, et mettrons en évidence les point communs, différences, avantages et inconvénients des différentes méthodes. Enfin, au cours des chapitres 6 et 7, nous présenterons quelques algorithmes de PageRank originaux dont nous pensons qu’ils peuvent apporter des améliorations significatives aux algorithmes existants. L’algorithme BackRank, conçu au départ pour modéliser l’utilisation de la touche Back, possède quelques effets secondaires intéressants, comme une convergence plus rapide que les algorithmes classiques et l’absence de problèmes liés à l’existence de pages sans lien. FlowRank est un algorithme qui essaie de prendre en compte de manière fine le rôle des pages internes, des pages externes et du flot de zap dans un calcul exact du PageRank. BlowRank est une adaptation pratique de FlowRank inspirée d’un autre algorithme de calcul décomposé du PageRank. Tous ces algorithmes sont autant d’outils potentiels ayant pour but de faciliter l’arbitrage entre accessibilité et visibilité, mais ils permettent aussi de se faire une meilleure idée des mécanismes qui entrent en jeu lorsque l’on veut modéliser un comportement stochastique sur le Web.
Une définition du Web
À l’origine, comme nous venons de le voir, le Web était caractérisé à la fois par un protocole (le http) et un langage (le html, HyperText Markup Language), le premier servant à diffuser des « pages » (des fichiers) écrites dans le second, et interprétées du côté client par des navigateurs Web (Browsers). De nos jours, on peut se poser des questions sur la validité de cette double caractérisation :
• Le html est un langage facile à apprendre permettant d’écrire des documents structurés et reliés entre eux par des hyperliens. De fait, il n’est plus utilisé aujourd’hui exclusivement à travers http, et on le retrouve sur de nombreux autres supports (CD-ROM, DVDROM. . . ) à des fins aussi nombreuses que variées (documentation, enseignement, encyclopédie, aide. . . ).
• Afin de délivrer du contenu multimedia, le http est prévu pour servir tout type de fichier. Images, sons, vidéos, textes sous divers formats, archives, exécutables. . . sont ainsi accessibles grâce au protocole http, dans un esprit plus ou moins éloigné de la conception originelle de navigation hypertexte. Cette tendance au « tout-http » aboutit à des situations parfois paradoxales. Ainsi, pour transférer des fichiers (même gros), il existe une certaine tendance à délaisser le protocole adéquat (le ftp, File Transfert Protocol) au profit de http. Comme le montre le tableau 1.12 , il semble que les fichiers traditionnellement transférés par ftp le soient maintenant par pair-à-pair, mais aussi par http (par exemple, la plupart des serveurs de téléchargements de sourceforge.net sont sous http).
• Certains documents qui ne sont pas des documents html permettent une navigation par hyperliens : documents propriétaires (Acrobat PDF, Flash. . .) ou nouveaux langages (WML, XML. . . )
Visibilité du Web
Chris Sherman et Gary Price proposent dans leur ouvrage The Invisible Web [SP01] une approche basé sur la visibilité par les grands moteurs de recherche. L’équivalent du Surface Web est chez Sherman et Price l’ensemble des pages indexées par les moteurs de recherche. Selon eux, le reste du Web se décompose alors en 4 catégories : The Opaque Web : les pages qui pourraient être indexées par les moteurs mais qui ne le sont pas (limitation d’indexation du nombre de pages d’un site, fréquence d’indexation, liens absents vers des pages ne permettant donc pas un crawling). The Private Web : les pages webs disponibles mais volontairement exclues par les webmasters (mot de passe, metatags ou fichiers dans la page pour que le robot du moteur ne l’indexe pas). The Proprietary web : pages accessibles seulement pour les personnes autorisées (intranets, système d’identification. . . ). Le robot ne peut donc pas y accéder. The Truly Invisible Web : contenu qui ne peut être indexé pour des raisons techniques. Par exemple, format inconnu par le moteur, pages générées dynamiquement (incluant des caractères comme? et &). . .
Le nœud papillon revisité
La structure en nœud papillon du graphe du Web est aujourd’hui admise par beaucoup de monde, et est très souvent évoquée par des articles scientifiques [CF02, APC03, LM04, RGM03,ANTT01, LM04, KHMG03a] ou de vulgarisation [GL02], de manière parfois totalement hors de propos . Je considère pour ma part que le modèle du nœud papillon s’applique mal aux graphes dynamique en général, et aux graphes du Web en particulier. Cette section, dont les idées viennent de [Mat01], va essayer de justifier cette prise de position en essayant de distinguer mythe et réalité afin de dégager le véritable intérêt de l’article Graph Structure in the Web.
Le modèle du nœud papillon Graph Structure in the Web [BKM+00] est un article qui a été présenté lors de la 9 ième conférence internationale sur le World Wide Web. L’article est basé sur l’analyse de deux crawls fournis par le moteur de recherche AltaVista, un crawl de 203 millions de pages daté de mai 1999 et un de 271 millions de pages d’octobre 1999. L’analyse donne plusieurs résultats sur la structure du graphe du web, le plus novateur étant la découverte d’une structure en nœud papillon :
• Environ un quart des pages considérées appartiennent à une seule et même composante fortement connexe, appelée noyau ou SCC (pour Strongly Connected Component).
• Un autre quart est formé de pages à partir desquelles on peut rejoindre le noyau, l’inverse n’étant pas vrai. C’est la composante IN.
• À l’inverse, près d’un quart des pages sont accessibles à partir du noyau, la réciproque étant fausse. Ces pages forment la composante OUT.
• Les pages qui sont accessibles à partir de IN, ou qui permettent d’accéder à OUT, et qui n’appartiennent ni à IN, ni à OUT, ni à SCC, forment les tentacules (TENDRILS) et représentent aussi près d’un quart des pages.
1. Les ancres (anchors) permettent de pointer vers une partie spécifique d’une page Web.
2. Par exemple, il est affirmé dans [LM04] et [KHMG03a] que Arasu et al. utilisent le modèle du nœud papillon pour accélérer leur calcul de PageRank [ANTT01]. Vérifications faites, Arasu et al. citent bien le modèle du nœud papillon, et proposent une méthode de calcul de PageRank basée sur. . . l’écriture de A sous une forme triangulaire par blocs déduite de la décomposition en composantes fortement connexes (cf théorème 6). En particulier, le seul apport du modèle du nœud papillon est l’existence d’un bloc diagonal plus gros que les autres (la SCC).
• Les quatre quarts que nous venons d’évoquer forment en fait 90% des pages du crawl, soit la plus grande composante connexe. Les 10% restant sont des composantes déconnectées du reste et de taille moindre. Cette structure est couramment représentée par un schéma similaire à celui de la figure 3.1. La forme de nœud papillon obtenue à partir des composantes IN, SCC et OUT donne son nom au modèle (bow tie). De cet article est resté auprès de beaucoup de monde l’idée que ce découpage en quantité à peu près égales en composante IN, SCC, OUT et tentacules est caractéristique du Web : c’est le modèle du nœud papillon.
Faiblesses du modèle du nœud papillon
Existe-t-il encore? Le principal inconvénient du modèle du nœud papillon, c’est que selon toute vraisemblance, il ne représente plus la réalité. Le graphe du Web, c’est-à-dire le graphe du Web accessible, ne peut pas avoir une structure de nœud papillon équilibrée, puisqu’il contient entre autres la page qui pointe vers toutes les pages (cf section 1.4 page 21). Il faut donc considérer que ce modèle s’applique aux graphes issus de gros crawls du Web (c’est d’ailleurs l’opinion des auteurs ). Seulement, on constate que :
• Aujourd’hui, la plupart des grands crawls sont l’œuvre de moteurs de recherche.
• Ces moteurs recensent les sites qu’il découvrent (par crawl ou par référencement) dans des annuaires (directories).
• Les annuaires font de toutes évidence partie du noyau du Web. Que peut-il donc se passer pour une page qui, pour un crawl donné, fait partie de la composante IN, ou des tentacules, ou même des composantes déconnectées :
• Si la page ou un de ses ancêtres est indexé par les annuaires, elle se retrouve de facto soit dans le noyau, soit dans OUT.
• Une page fait partie du crawl parce que un de ses ancêtres faisait partie de l’ensemble initial de crawl. Si aucun ancêtre de la page n’a été mis à l’annuaire, on peut douter qu’un ancêtre soit conservé dans l’ensemble initial de crawl. Conséquence, au prochain crawl, la page disparaîtra. En conclusion, oui, il peut y avoir une composante IN, ou des composantes déconnectées, mais ces composantes sont forcément transitoires, à cause même des relations entre crawlers et annuaires. Il faut également tenir compte du fait que les gros crawls actuels possèdent une part non négligeable de pages non-indexées (au moins 25 % d’après une étude de 2002 [Sea], 75% d’après un article de 2004 [EMT04]), qui viennent automatiquement grossir la composante OUT. Pour toutes ces raisons, j’ai tendance à douter très fortement que plus de 2 (3?) milliards de pages indexées par Google ne fassent partie ni du noyau, ni de OUT.
|
Table des matières
Remerciements
Introduction
I Structures du Web
1 Qu’est-ce que le Web?
1.1 Genèse du Web
1.2 Une définition du Web
1.3 Accessibilité du Web
1.3.1 Profondeurs du Web
1.3.2 Visibilité du Web
1.3.3 Web accessible
1.4 Intermezzo : la page qui pointait vers toutes les pages
2 Chalutiers et tailles du Web
2.1 Les chalutiers du Web
2.1.1 Création de l’ensemble des pages initial
2.1.2 Stratégies d’exploration
2.2 Tailles et évolutions des crawls
2.2.1 Selon les organisateurs
2.2.2 Selon la police
2.2.3 remarques personnelles
2.3 Mesures sur des crawls
2.3.1 Techniques de chevauchement (overlap)
2.3.2 Échantillonnage par marche aléatoire
3 Graphes et structures du web
3.1 Graphes du Web : définition
3.2 Le nœud papillon revisité
3.2.1 Le modèle du nœud papillon
3.2.2 Faiblesses du modèle du nœud papillon
3.2.3 Le modèle du nœud papillon dans un contexte sociologique
3.2.4 Conclusion
3.3 Rôle des serveurs et des sites dans la structure du graphe du Web
3.3.1 Serveurs Web, sites et communautés
3.3.2 Évolution du nombre des serveurs
3.3.3 Approche intuitive et visuelle de la notion de site structurel
3.3.4 Proposition d’algorithme de partitionnement en sites
II Algorithmes de classement de pages web : les « PageRank »
4 Les chaînes de Markov
4.1 Définitions
4.2 Côté graphe, côté matrice
4.3 Évolution d’une chaîne de Markov homogène
4.4 Intermezzo : Le MonopolyTM selon Markov
4.4.1 Bref rappel des règles et notations
4.4.2 Matrice des transitions
4.4.3 Probabilités asymptotiques et conclusion
4.5 Matrices (sous-)stochastiques : cas général
4.5.1 Matrices non irréductibles
4.5.2 Matrices périodiques
4.5.3 Matrices sous-stochastiques
4.5.4 Cas général : conclusion
5 PageRank, une manière d’estimer l’importance des pages web
5.1 Une aiguille dans un océan de foin
5.2 Les deux axiomes du PageRank
5.2.1 Une page importante est pointée par des pages importantes
5.2.2 Le surfeur aléatoire : le hasard fait bien les choses
5.2.3 Cohérence des deux interprétations
5.3 Les modèles classiques
5.3.1 Cas idéal
5.3.2 Renormalisation simple
5.3.3 Complétion stochastique
5.3.4 Source de rang : facteur zap
5.3.5 Choix de d
5.4 Source de rang et matrices sous-stochastiques
5.4.1 Modèle hybride : facteur zap et renormalisation
5.4.2 Complétion et source de rang : µ-compensation
5.4.3 PageRank non-compensé
5.4.4 Comparaison : algorithmes µ-compensé ou non-compensé?
5.5 Convergence en norme 1 et convergence du classement
5.5.1 Distance de Kendall normalisée
5.5.2 Densité de PageRank
5.5.3 Seuil de différenciation
5.6 Modèles avec page virtuelle
5.6.1 Page virtuelle de zap
5.6.2 De l’utilité de la page virtuelle
5.6.3 Page virtuelle de complétion
5.6.4 Erratum
5.7 Gestion des ressources physiques
6 BackRank
6.1 De l’importance de la touche Back
6.2 Travaux antérieurs et contemporains
6.3 Modélisation de la touche Back
6.3.1 Modèle réversible
6.3.2 Modèle irréversible
6.3.3 Incorporation du facteur zap
6.4 Algorithme pratique : BackRank
6.4.1 Optimisation
6.4.2 Résultats
7 Décomposition fine du PageRank
7.1 Travaux antérieurs et contemporains
7.2 Hypothèses
7.3 PageRank interne, PageRank externe
7.3.1 Notations
7.3.2 Lois de conservation
7.4 Décomposition du calcul du PageRank
7.4.1 Relation entre PageRank externe et PageRank
7.4.2 Matrice de transition du PageRank externe
7.4.3 Calcul décomposé théorique du PageRank
7.5 Intermezzo : modifier son propre PageRank
7.5.1 Coefficient d’amplification
7.5.2 Introduction du facteur zap
7.5.3 Zap et coefficient d’amplification
7.5.4 Amplification d’une page donnée
7.6 Cas réel : FlowRank et BlowRank
7.6.1 Relations à l’équilibre avec le facteur zap
7.6.2 Une première approche : FlowRank
7.6.3 Algorithme distribué de Kamvar et al. : BlockRank
7.6.4 Algorithme hybride : BlowRank
Conclusion
Annexe A : Théorème de Perron-Frobenius
Annexe B : Petite étude du PageRank sur le site de l’INRIA
Annexe C : Persistence et diffusion des fichiers dans les réseaux pair-à-pair
C.1 Introduction
C.2 Model
C.3 First simulations
C.3.1 Strategies
C.3.2 Results
C.4 “torpor” characteristics
C.4.1 Torpor apparition
C.4.2 Torpor robustness
C.4.3 The missing block in real networks
C.5 Efficiency of upload strategies
C.5.1 Average download speed
C.5.2 Speed of Deployment
C.5.3 Density
C.5.4 Robustness to very greedy peers
C.6 Future work
C.7 Conclusion
Bibliographie
Télécharger le rapport complet
