Chapitre 3 — Graphes et structures du web

La vie est un papillon éphémère arborant les ailes du paradoxe.

Les sites ne changent pas d’aspect comme les hommes changent de visage.

Un bon site Web est toujours en construction.

Maintenant que les concepts de Web et de crawl ont été précisé, nous allons pouvoir étudier ce qu’il est possible d’en dire. Ce chapitre étant consacré aux structures, il convient de placer une structure canonique sur les crawls que l’on veut étudier. Une des structures les plus simples et les plus naturelles dans le cas des crawls du Web est la structure de graphe. Les graphes du Web, dont une définition est donnée Section 3.1, sont un sujet d’étude fréquent. Après avoir analysé de manière critique l’un des modèles les plus connus, le modèle du nœud papillon (Section 3.2), nous mettrons en évidence dans le reste du chapitre l’importance de la structure en sites dans les graphes du Web.

3.1 Graphes du Web : définition

Considérons un crawl . Ce crawl est constitué d’un ensemble d’URLs, dont certaines ont été visitées, et d’autres simplement détectées à travers les hyperliens des pages visitées. Il contient aussi l’ensemble des hyperliens des pages visitées. On appellera graphe du crawl le graphe orienté , où est l’ensemble des pages du crawl, visitées ou non, et tel qu’un arc relie une page à une page si, et seulement si, contient un hyperlien pointant vers . Par convention, les ancres¹ sont ignorées, et les liens multiples ne rajoutent rien au graphe (si une page possède deux hyperliens pointant vers , le graphe aura toujours un seul arc de vers ). De même, les liens d’une page vers elle-même ne seront pas pris en compte.

Par abus de langage, nous utiliserons souvent le terme graphe du Web pour désigner un tel graphe . Il conviendra de toujours se rappeler qu’il s’agit toujours en fait de graphes de crawls.

3.2 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 [APC03, Ara+01, CF02, Kam+03b, LM04, RG03] 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.

3.2.1 Le modèle du nœud papillon

Graph Structure in the Web [Bro+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.
• 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.
• 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.

3.2.2 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). 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.

Un modèle peu robuste

Une question que l’on peut se poser est de savoir si les paramètres considérés sont pertinents pour l’étude des graphes du Web. D’un côté, nous avons les crawls, qui essaient de parcourir tant bien que mal un Web dynamique aussi bien spatialement que temporellement, et qui ont souvent un overlap très faible entre eux [BB98]. De l’autre, des définitions comme IN : ensemble des pages qui accèdent au noyau, mais ne sont pas accessibles de celui-ci. Est-il raisonnable de faire cohabiter des crawls très variables et des définitions peu robustes ? Un exemple concret : imaginons qu’un individu peu scrupuleux s’empare de l’ensemble des pages initiales des crawls d’AltaVista et mette les liens vers ces pages sur sa page Web. Si cette page est dans le noyau, cela signifie l’écroulement de toutes les composantes sur SCC et OUT⁴.

Contrairement à ce qu’affirme les auteurs⁵, il suffit donc d’une page, pas si grosse que ça⁶, pour mettre à mal le modèle du nœud papillon. On est en fait en présence d’une lacune méthodologique : en face de données sur lesquelles l’incertitude et la dynamique est très grande (les graphes du Web), cela n’a pas de sens de considérer des variables extrêmement dépendantes des conditions initiales comme des constantes universelles. Pour les même raisons, considérer le diamètre de la composante connexe n’est guère pertinent ; effectivement, sur les 2 crawls d’AltaVista étudiés, il reste à peu près constant (aux alentours de 500), mais en y regardant de plus près, des indices semblent montrer que le diamètre de 500 est dû à une unique guirlande, peut-être une page mal configurée ou un piège à robots qui aurait échappé aux filtres⁷.

Une expérience non reproduite

À ma connaissance, l’expérience de [Bro+00] n’a pas été reproduite sur des grands crawls depuis. Les seules expériences réelles menées sur le modèle du nœud papillon portent donc sur deux crawls propriétaires d’AltaVista, peu espacés et donc vraisemblablement basés sur la même technologie (ce qui peut expliquer certains artefacts comme la constance du diamètre). De plus, si on compare la taille et les dates de ces deux crawls (mai 1999, 203 millions de pages, octobre 1999, 271 millions de pages) avec les Figure 2.2b et Figure 2.2c (Figure 2.2b), on arrive à la conclusion que les crawls utilisés étaient certainement expérimentaux.

Dans [Dil+01], on trouve pourtant que la structure en nœud papillon est une figure fractale de la structure du Web, c’est-à-dire que l’on retrouve à l’intérieur des sites et des communautés le même modèle de nœud papillon que sur le graphe tout entier. En y regardant de plus près, on s’aperçoit que la structure globale de nœud papillon est admise, et que les proportions de IN, OUT, et SCC observés dans les sous-graphes sont extrêmement variables, ce qui va dans le sens des remarques précédentes.

3.2.3 Le modèle du nœud papillon dans un contexte sociologique

Pour bien comprendre le succès du modèle du nœud papillon, il est important de se replacer dans le contexte. Nous sommes au début de l’année 2000. La Bulle Internet est encore en pleine croissance, et des articles apparaissent indiquant que les moteurs de recherche ne font plus face à la croissance du Web [Ber00, Bra97, LG99]. La société AltaVista a remporté la première Guerre du Crawl (voir Figure 2.2b ainsi que les conclusions de [BB98]) en dépassant les 150 millions de pages indexées, mais il lui manque l’assurance que cette augmentation de taille va lui permettre de rattraper l’évolution du Web. Dans cette optique, Graph Structure in the Web tombe à point nommé. En effet, quelle est la morale de l’article ?

• Il existe une structure globale du Web (avec un grand W).
• Cette structure est invisible si on considère une portion trop petite du Web, mais il existe un seuil au-delà duquel la structure d’un crawl est la structure du Web.
• Les crawls d’AltaVista sont assez grands pour posséder la structure du Web.

En somme, Graph Structure in the Web répond à une attente à la fois existentielle (Peut-on comprendre le Web ?) et commerciale (Notre crawl est le Web.). On pourrait presque le voir comme un mécanisme issu des lois de l’offre et de la demande. À la limite, la question de savoir si ses bases scientifiques sont solides ou non devient secondaire, ce qui est peut-être un début d’explication au succès de cet article.

3.2.4 Conclusion

Le modèle du nœud papillon a très certainement eu un sens au moment de sa découverte, mais ce sens n’est pas le Web a une structure de nœud papillon. Il exprime plutôt une situation particulière où à cause de la Bulle Internet, les nouvelles pages arrivaient trop vite pour que le Web puisse les assimiler. Mais aujourd’hui, deux phénomènes font que l’on est plus dans ce cas : d’une part, la Bulle a éclaté. La création de nouveaux sites se fait rare, et on assiste plus à un développement de sites existants qu’à l’apparition d’une nuée de sites non répertoriés (cf Section 3.3.2), ce qui est un début d’explication au fait que la structure en nœud papillon se retrouve dans les graphes des sites [Dil+01]. D’autre part, les moteurs de recherche ne font plus seulement qu’indexer le Web, ils en modifient continuellement la structure par l’intermédiaire des annuaires. Ces deux effets conjugués au manque de robustesse du modèle font qu’il est peu probable que les grands crawls commerciaux aient encore la même proportion de IN, tentacules et autres composantes déconnectées que celles trouvées dans Graph Structure in the Web.

On retiendra quand même que Broder et al. ont mis en évidence l’existence d’un important noyau de pages toutes connectées les unes aux autres, ainsi que le comportement protectionniste de certains sites commerciaux qui s’incluent totalement dans la composante OUT. On retiendra également que la proportion de composante IN dans le graphe d’un crawl est une certaine indication de la difficulté d’un grand graphe structuré à s’adapter à une expansion rapide.

3.3 Rôle des serveurs et des sites dans la structure du graphe du Web

La notion de site est fondamentale dans l’organisation du Web. Par exemple, beaucoup de moteurs de recherche ont pour politique de ne renvoyer qu’un nombre limité de pages par site (avec une option plus de pages venant du même site disponible). Une bonne décomposition en sites a de nombreuses applications, qui vont des méthodes de calcul du PageRank [Kam+03b, MV04] à des méthodes de compression efficaces des crawls [GLV02, Ran+01].

3.3.1 Serveurs Web, sites et communautés

Les concepts de serveur Web, site et communauté sont souvent rencontrés dans la littérature, avec des définitions parfois contradictoires. Nous allons expliciter ici ce que nous entendrons par serveur, site et communauté.

Serveur réel

Un serveur Web réel se définit comme une machine physique précise connectée à Internet et identifiée par une adresse IP, qui renvoie un code de réponse 200 et une page Web en retour d’une requête HTTP demandant la racine (/) sur le port 80⁸. Le site Web physique associé au serveur consiste en toutes les pages hébergés à l’adresse IP considérée.

Serveur virtuel

Les adresses IP n’étant pas illimitées, des solutions ont dû être envisagées pour économiser les adresses. Une de ces solutions est l’emploi de serveurs virtuels. Les serveurs virtuels, introduits avec la norme HTTP 1.1, permettent à une même adresse IP de se comporter comme plusieurs serveurs différenciés par leur adresse Domain Name System (DNS) (Hostname). Ce procédé est par exemple utilisé par free pour l’hébergement des pages personnelles de ses clients, ou au Japon, où les ressources en adresses IP sont très limitées. Du point de vue de l’utilisateur, un serveur virtuel est indicernable d’un serveur réel, si ce n’est qu’on ne peut pas remplacer l’adresse DNS par l’adresse IP.

Site logique

Un site Web logique est constitué d’un ensemble de pages fortement reliées par hyperliens. Intuitivement, un site se caractérise par une certaine homogénéité de style (imposée par le Webmaster) et une navigation aisée au sein des pages du site. L’étude des sites sera l’objet des sections Section 3.3.3 et Section 3.3.4.

Communauté

La notion de communauté est en quelque sorte orthogonale à la notion de site. Une communauté est un ensemble de pages reliées par un intérêt commun. La recherche de communautés est au cœur de l’algorithme Hyperlink-Induced Topic Search (HITS) de Kleinberg [Kle98] ainsi que du projet CosmoWeb [BBM03].

3.3.2 Évolution du nombre des serveurs

Il est plus facile d’estimer le nombre de serveurs Web (réels et virtuels) que le nombre de pages Web.

Pour dénombrer les serveurs réels, il «suffit» de faire une requête HTTP sur toutes les adresses IP possibles. Or, si on oublie les adresses IPv6, qui restent encore relativement négligeables, il n’y a que adresses possibles, soit environ quatre milliards⁹. Ce travail a été effectué par le Web Characterization Project [O'N+02], sur la période 1998-2002, et les résultats concernant le nombre de serveurs sont représentés Figure 3.2. Le nombre de serveurs physiques uniques est le nombre de serveurs physiques diminué des doublons, c’est-à-dire des serveurs renvoyant exactement le même contenu qu’un serveur précédemment testé.

La principale remarque que l’on peut faire quant à ces chiffres est l’observation d’une stagnation du nombre de serveurs physiques depuis 2001. Cette stagnation peut s’expliquer par la fin de la bulle Internet. En effet, le Web a cessé d’être une nouvelle technologie, et la plupart des acteurs universitaires, commerciaux et sociaux susceptibles de s’intégrer au Web l’ont déjà fait. D’après le Web Characterization Project, il ne se crée presque pas, voire plus de serveurs Web, la croissance se fait individuellement au niveau des serveurs.

L’étude des serveurs virtuels a été réalisée par le site Netcraft [Net04]. Elle consiste à répertorier l’ensemble des adresses DNS déclarées (comme le site WhoIs [Who04]), et à tester par une requête HTTP l’existence d’un serveur sur chacune des adresses obtenues.

L’évolution des serveurs Web virtuels, d’après Netcraft [Net04], montre une progression constante à peu près linéaire du nombre de serveurs Web virtuels actifs au cours des 4 dernières années (cf Figure 3.3). Ce n’est en tout cas à priori pas une progression géométrique.

3.3.3 Approche intuitive et visuelle de la notion de site

Le concept de site est selon nous fondamental dans la structure du Web. Ses applications sont nombreuses :

• Évaluation plus précise du degré d’aboutissement d’un crawl (pour chaque site, quelle est la quantité de pages visitées ?)
• Distinguer des liens purement navigationnels de liens plus pertinents (liens de confiance en d’autres sites).
• Permettre à certains moteurs de recherche de ne renvoyer qu’une ou deux pages par site, afin d’éviter une monopolisation des réponses à une requête.
• Affinement du facteur zap dans les calculs de PageRank (voir Partie II, Section 5.3, ainsi que [Bri+98, Hen+99])
• Algorithmes de PageRank basés sur la structure de site (l’algorithme FlowRank, présenté Partie II, Chapitre 7, ainsi que son «concurrent» BlockRank [Kam+03b])

La plupart du temps, les sites sont approximés par les serveurs ([Ada99]). Mais la réalité peut parfois être plus complexe. Des gros sites peuvent reposer sur plusieurs serveurs, alors qu’inversement un serveur peut héberger plusieurs sites. Par exemple, on aurait envie de regrouper www.microsoft.com et download.microsoft.com et de les considérer comme faisant partie d’un même site. À l’inverse, tous les hébergeurs de sites personnels n’utilisent pas les domaines virtuels, une grande partie met les sites dans les répertoires d’un serveur unique.

Toutes ces considérations nous amènent à nous poser la question de la définition d’un site logique. Les internautes (humains) n’ont en général aucun problème pour savoir ce qu’est un site, ce qui constitue en quelque sorte une définition empirique, mais n’est guère rigoureux et ne se prête guère à l’automatisation. Notons que les sites référencés à la main par les annuaires rentrent dans cette définition.

Le Web Characterization Project [O'N+02] propose quant à lui la définition sémantique suivante :

[A Web Site (Information Definition) is] a set of related Web pages that, in the aggregate, form a composite object of informational relevance. Informational relevance implies that the object in question addresses a non-trivial information need.

[Un site Web logique est] un ensemble de pages similaires qui, par leur réunion, forment un objet composite délivrant une information pertinente. Cette information pertinente implique que l’objet en question réponde à un besoin d’information non-trivial.

À cette caractérisation sémantique, Li, Kolak, Vu et Takano superposent dans [Li+00] une approche structurelle pour définir proposent la notion de domaine logique :

A logical domain is a group of pages that has a specific semantic relation and a syntactic structure that relates them.

Un domaine logique est un groupe de pages qui possèdent une relation sémantique spécifique et une structure syntaxique qui les relie.

Se basant sur cette définition, ils définissent un ensemble de règles (sémantiques et structurelles) pour identifier des sites.

Plus modestement, notre approche est de voir ce qu’il est possible de réaliser en ne considérant que le côté structurel des pages. Nous nous limitons donc à d’une part la structure de graphe induite par les hyperliens, d’autre part la structure en arbre des URLs qui fait apparaître des clusters naturels sur les graphes des crawls. En effet, très souvent, un site logique obéit à des règles hiérarchiques au niveau des URLs (Uniform Resource Locators [BMM94]), la plus commune étant l’existence d’un préfixe commun caractéristique.

Cette structure d’arbre de décomposition¹⁰ sur les graphes (clustered graphs) a été introduite par Feng et al. dans [FCE95] comme un outil de représentation des grands graphes. Sa principale utilisation est donc de permettre de dessiner des graphes de manière à laisser apparaître l’éventuelle hiérarchie existante, et on emploie surtout les arbres de décomposition dans les domaines où des structures de diagrammes implicites ou explicites existent¹¹.

Tout le problème est alors de trouver pour un graphe donné l’arbre de décomposition qui offre la meilleure représentation structurelle [Bri03]. Dans le cas des graphes du Web, l’arbre des URLs offre un arbre de décomposition intrinsèque.

Définition

Soit un graphe. Un arbre de décomposition de est la donnée d’un arbre dont les feuilles correspondent aux sommets . Chaque nœud interne de définit un cluster (ensemble de sommets) . Ce cluster est constitué de l’ensemble des sommets de correspondant aux feuilles du sous-arbre de de racine . Par exemple, le cluster associé à la racine de est l’ensemble tout entier.

Un bon exemple de l’utilisation des arbres de décomposition est la modélisation des relations humaines. Il existe en effet un graphe assez naturel des relations humaines, où les sommets sont des personnes et où une personne pointe vers une personne si connaît ). Un arbre de décomposition qui peut compléter de manière pertinente ce graphe est celui de la localisation géographique : monde, pays, (état), ville, quartier, rue, …

Graphes du Web et arbre de décomposition des URLs

Les URLs offrent une structure naturelle d’arbre de décomposition sur les graphes du Web. L’ensemble des serveurs¹² peut être représenté par un arbre dont la racine est http, les nœuds de profondeur 1 les TLDs¹³, suivis des noms de domaines proprement dits et éventuellement des sous-domaines. Chaque serveur, qui est une feuille de l’arbre des noms de domaine, héberge une hiérarchie de pages identique à la structure du système de fichiers physique correspondant. La réunion des arbres des fichiers dans l’arbre des serveurs donne l’arbre de décomposition des URLs.

Par exemple, l’URL http://smith.mysite.org/linux/index.html se décompose en HTTP, org, mysite, smith, linux et enfin index.html, formant ainsi un chemin qui part de la racine jusqu’à la feuille correspondante dans l’arbre de décomposition (voir Figure 3.4).

On peut éventuellement s’interroger sur la pertinence de commencer la décomposition par le domaine de premier niveau (TLD). En effet, il existe des macro-sites qui, pour avoir une meilleure visibilité, se déploient sur plusieurs TLDs (.com et les ccTLDs des pays d’implantation, de manière assez classique). Nous préférons quand même conserver le tri par TLD, d’une part parce que cela correspond à la philosophie initiale des noms de domaines, d’autre part parce qu’il existe aussi des noms de domaine pour lesquels le TLD change beaucoup de choses. Le lecteur majeur et averti pourra par exemple constater une différence sémantique certaine entre le contenu du site http://www.france2.fr et celui de http://www.france2.com…

Voir la structure des sites

Étant donné que d’une manière générale, les webmasters essaient d’organiser leurs sites, on peut s’attendre à ce que le concept de site Web soit intimement relié à celui l’arbre de décomposition des URLs. Nous en avons eu confirmation en observant la représentation graphique de la matrice d’adjacence du graphe d’un crawl d’environ 8 millions d’URLs triées dans l’ordre lexicographique de .fr fait en juin 2001 dans le cadre de l’action de recherche coopérative Soleil Levant [Sol01].

Nous avons représenté une petite partie de ce crawl (60 000 pages) Figure 3.5, et quelques zooms sur des sous-parties intéressantes Figure 3.6. La première constatation est que la matrice d’adjacence peut de toute évidence se décomposer en deux termes, , où est une matrice diagonale par blocs, et où est une matrice (très) creuse.

Les sites (et les sous-sites) apparaissent en effet comme des carrés qui coincident avec les nœuds de l’arbre des URLs. Avec un peu d’habitude, on arrive même à deviner la structure profonde des sites d’après l’aspect du carré correspondant. Par exemple, les pages à fort degré sortant (typiquement, la carte du site) se traduisent par des lignes horizontales, alors que celle à fort degré entrant (les pages d’acceuil) sont caractérisées par des lignes verticales. Des carrés «bruités», c’est-à-dire avec des points présentant une structure pseudo-aléatoire (cf Figure 3.6c), sont souvent le signe de pages de documentation interactives (des dictionnaires par exemple). Remarquons enfin que la structure peut présenter un caractère récursif, comme le montre le bloc de la Figure 3.6d.

3.3.4 Proposition d’algorithme de partitionnement en sites

Nous allons essayer, avec seulement la connaissance du graphe et des URLs d’un crawl, de générer le plus simplement possible une partition du graphe qui reflète la notion de site. Notre approche diffère donc de celle employée par [Li+00], qui emploie également un ensemble de règles sémantiques pour définir les sites.

Modèle formel

Structurellement, nous pensons qu’un site se définit comme un ensemble de pages étroitement reliées entre elles par des liens navigationnels, comme semble le confirmer les représentations de la matrice d’adjacence (cf Figure 3.5).

Cela nous amène à essayer de définir une fonction qui mesure la qualité d’une partition en site par rapport au taux de liens navigationnels. Cette fonction, doit atteindre un extremum lorsque approche (dans un sens à préciser) ce que nous aimerions appeler partition en sites. Une fois une telle fonction trouvée, la méthode standard pour partitionner consiste à construire une partition initiale des URLs (adaptée à la situation considérée), puis à effectuer des ajustements locaux pour essayer d’optimiser .

Choix de la fonction

Comme le facteur le plus important selon nous pour estimer une partition en sites est le nombre de liens navigationnels, il apparaît logique de chercher une fonction qui dépende explicitement de , nombre de liens internes. Il faut également tenir compte du nombre de sites : en effet, celui-ci n’est pas fixé à l’avance (sinon, on serait dans le cadre classique d’algorithmes de type mincut ou maxcut). Pour éviter d’avoir comme extremum la partition triviale , et pour essayer d’avoir une décomposition fine, il nous semble également important d’essayer de maximiser le nombre de sites . Nous avons donc deux paramètres globaux, le nombre de sites et le nombre de liens internes , et la fonction que nous recherchons doit vérifier à la fois et . Plusieurs formules simples sont a priori possibles :

• , .

  Cette solution ne sera pas retenue ici, principalement parce que le choix de nécessite pour être judicieux d’être égal au nombre moyen de liens par page, ce qui laisse peu de jeu. En effet, si est plus grand que ce nombre, on risque de se ramener à maximiser (on a intérêt à isoler des pages), alors que s’il est plus petit, pour les mêmes raisons, seul va compter.

• , .

  Cette solution présente l’avantage d’être plus souple pour ce qui est du rapport entre et .

• , où est le nombre total de liens.

  Cette dernière solution est délibérément dépourvue de paramètre car on a ainsi une quantité qui a une interprétation intuitive : pour une partition dépourvue de liens externes, on aurait . D’une manière générale, reste du même ordre de grandeur que en s’en approchant d’autant plus que la cohésion interne est grande. Nous appellerons donc la quantité l’indice de site, qui peut s’interpréter comme le nombre de sites isolés équivalent.

Problème des pages isolées

Le cas des pages de degré entrant 1 et de degré sortant nul pose un problème. Si elles peuvent parfois représenter un site isolé réduit à une page unique (Figure 3.7), on constate expérimentalement que dans la plupart des cas ce sont des pages crawlées, mais non visitées (voir Section 2.1) ou des pages terminales de sites structurés (Figure 3.8). D’un point de vue structurel, et en l’absence de toute autre considération, il nous semble légitime de s’assurer que les pages de degré entrant 1 et de degré sortant nul soient rattachées au site de la page parente. Cela se traduit, au niveau de la fonction introduite précédemment, par l’inégalité suivante :

Cette inégalité, si on essaie de l’imposer à notre fonction (ce qui est nécessaire si l’on veut que suffise à réaliser la partition), pose le problème suivant : toute partition de paramètre telle que

est moins performante que la partition triviale :

Hélas, l’Équation (3.2) est vérifiée dès que le graphe est connexe. D’une manière générale, pour un graphe composé de composantes connexes et de arêtes, on aura forcément pour toute partition de paramètre l’inégalité

Bilan : Il n’existe aucune fonction universelle maximale pour une partition en site non triviale respectant les pages terminales.

Deux approches sont alors envisageables pour contourner ce problème, ainsi que les autres du même genre que l’on pourrait rencontrer en essayant d’affiner notre modèle :

• Continuer à chercher à maximiser en imposant des règles externes, ce qui reviendrait par exemple à travailler sur un sous-ensemble de l’ensemble des partitions du graphe. C’est l’approche employée pour la partie structurelle de la définition de domaines logiques utilisée par [Li+00].

• Remplacer ou par de nouvelles variables qui prennent en charge le problème implicitement. C’est cette approche que nous allons étudier.

Altération des variables et

Une première idée consisterait à pondérer le poids des arêtes de telle sorte que les liens vers des pages isolées soient plus difficiles à rompre. Ainsi, une idée assez classique et naturelle est de prendre un poids inversement proportionnel au degré entrant (cf [Kle98]). Hélas, la nouvelle variable introduite présente de nombreux inconvénients, surtout si elle est l’unique altération introduite :

En premier lieu, on peut considérer le cas de deux sites (au sens intuitif) reliés entre eux par une arête unique (Figure 3.9). Si l’algorithme est conçu pour ne pas séparer les pages terminales, c’est-à-dire s’il respecte la relation Équation (3.1), il sera obligé de fusionner les deux sites, ce qui n’est pas forcément l’effet désiré.

En outre, si l’on regarde les deux exemples de sites 3-reliés de la Figure 3.10, on aimerait que la décision de fusion des sites, toutes choses étant égales par ailleurs, soit la même dans les deux cas. Avec des poids sur les arêtes dépendant du degré entrant, cela sera difficile, puisque la force de liaison varie du simple au triple entre les deux cas.

Une altération par pondération des partitions suivant leur taille est une autre solution. D’une manière générale, si l’on considère une partition et une fonction de pondération , on peut définir la nouvelle variable . La solution la plus simple, que nous retiendrons ici, consiste à affecter un poids nul aux partitions monoatomiques (ce qui revient en fait à travailler sur en imposant comme règle l’interdiction des partitions monoatomiques). Le choix d’autres fonctions ne sera pas traité ici, mais on peut espérer en choisissant la bonne fonction un certain contrôle sur la distribution des partitions, par exemple éviter la formation de trop gros sites en affaiblissant sur les grandes valeurs.

Fonction choisie

Compte tenue de toutes les remarques que nous venons de faire, nous choisissons de prendre comme fonction d’évaluation la fonction qui à une partition de associe , où est le nombre de liens internes et , avec .

Estimation d’une partition par site à l’aide de l’arbre de décomposition des URLs

Maintenant que nous possédons une fonction d’évaluation d’une partition se pose la question de réaliser une partition efficace. Une méthode intuitive se base sur l’hypothèse suivante, confortée par l’observation des Figure 3.5 et Figure 3.6 : L’architecture URL des pages reflète l’architecture des sites, et donc les blocs sont a priori des sous-arbres ou union de sous-arbres de l’arbre du Tree-Graph. Au lieu d’avoir à choisir une partition parmi toutes celles possibles, on pourra se limiter pour le choix des candidats aux candidats coïncidant avec la structure d’arbre.

Cette solution n’est pas parfaite, et il y aura toujours des cas litigieux. Ainsi, dans des configurations en poupée russe, le choix du niveau de partition va être très lié au choix des fonctions et . Par contre, des configurations en cinq de dé (un site encastré dans un autre au niveau de la matrice d’adjacence, voir Figure 3.11), difficiles à démêler automatiquement avec seulement la matrice d’adjacence (qui porte pourtant plus d’information que le graphe seul), ne poseront pas de problèmes avec l’arbre de décomposition pour peu que les sites coïncident avec l’arbre (ce qui est le cas sur tous les exemples testés).

Nous allons donner un exemple d’algorithme simple pour effectuer une partition intelligente et rapide des URLs à l’aide de l’arbre-graphe : le parcours en largeur filtré (Algorithme 3.1).

Les avantages de ce découpage initial sont les suivants :

• On évite d’amalgamer comme un seul site deux ensembles très proches dans l’arbre mais n’ayant aucun lien direct dans le graphe. Ainsi, les sites dits «persos» ne sont pas fusionnés sous le seul label du fournisseur d’espace (free, voila, multimania…) ; de même, la page d’un chercheur dans un laboratoire ne fera partie du site du laboratoire que si elle est référencée par ce dernier, ce qui nous semble satisfaisant.

• À l’inverse, des sites hébergés sur plusieurs serveurs voisins (www.inria.fr et www-rocq.inria.fr par exemple) sont traités comme une seule et même entité.

Il reste hélas des cas que l’algorithme que nous proposons ne prend pas en charge. Ainsi, certains sites sont à cheval sur plusieurs serveurs n’ayant aucun lien de parenté dans l’arbre lexicographique tel que nous l’avons défini (site perso partagé entre plusieurs hébergeurs, site commercial se déclinant en .com, .fr, .de…).

Résultats

Nous allons comparer ici la partition obtenu par parcours en largeur filtré aux partitions quotientées par serveur, par répertoire à profondeur 1 et par répertoire à profondeur 2 (ce qui correspond typiquement à des coupures à hauteur 3, 4 et 5 dans l’arbre-graphe). L’étude a été faite sur le crawl de 8212791 URLs de .fr daté du 15 juin 2001. Par abréviation, nous appellerons ces partitions plf, serveur, 1-rép et 2-rép.

Observons d’abord comment se répartissent les différentes partitions. La Figure 3.12 montre les distributions des tailles des différentes partitions. On observe que quelque soit la méthode utilisée (plf, serveur, 1-rép ou 2-rép), les partitions obtenues se répartissent suivant une loi de puissance¹⁵, c’est-à-dire que le nombre de blocs de taille est de l’ordre de . Les valeurs des exposants (estimés par régression linéaire) sont indiquées dans le tableau Tableau 3.1.

La loi de puissance est une loi considérée comme caractéristique des réseaux sociaux et des activités humaines. Le fait de rencontrer une telle loi dans tous les cas étudiés, à défaut de prouver quoi que ce soit, montre que du seul point de vue de la répartition des pages (sans tenir compte des hyperliens), les quatre répartitions étudiées semblent être compatibles avec la structure humaine du Web.

Remarquons également l’importance des « sites » de taille 1 (les données de la Figure 3.12 viennent des partitions avant toute optimisation), et cela plus particulièrement pour la partition plf. L’explication est assez logique : les partitions de taille 1 contiennent entre autres toutes les erreurs qui n’ont pas été supprimées du crawl : erreur 4xx, erreur dans l’écriture de l’URL… La partition plf isole plus d’erreurs que les autres par construction, puisqu’une URL isolée dans le cône lexicographique d’un site sera isolée par plf, à l’opposé des autres partitions.

Enfin, comparons la qualité du découpage en site des différentes partitions, à l’aide de l’indice de site défini par la fonction . L’optimisation est dans un premier temps minimale : les sites de taille 1 sont fusionnés avec le site avec lequel ils sont le plus liés (le plus souvent, la liaison est unique).

Les résultats sont reportés dans le tableau Tableau 3.2. On remarquera que plf, dont les résultats pour comme pour sont à mi-chemin entre serveur et 1-rép, obtient de loin le meilleur indice de site.

Optimisation des partitions

Les résultats précédents proviennent de partition qui ne cherchent pas a priori à maximiser l’indice de site. On peut se contenter de ces résultats, si l’on voit simplement l’indice de site comme une indication de qualité, mais on peut aussi chercher à le maximiser. Nous allons donc voir ce que donnent une optimisation locale par mélange, sans plf et avec plf. Le principe de cette optimisation est simple : pour chacun des sites définis par la partition que l’on veut optimiser, on tente d’améliorer l’indice de site en le remplaçant par la décomposition locale (serveur, 1-rép,…) qui donne le meilleur indice de site. Il s’agit donc d’un algorithme glouton, et le résultat obtenu, qui est un maximum local, peut dépendre de l’ordre dans lequel les sites sont traités.

Les résultats sont présentés dans le tableau Tableau 3.3. Deux parcours différents des partitions ont été effectués, pour se rendre compte des fluctuations que le choix du parcours peut générer, ainsi que de leur importance. Les principaux résultats que l’on peut tirer de ce tableau sont :

• Un net regain général de l’indice de site, les données et étant proches des valeurs maximales techniquement possibles par cette méthode.
• L’optimisation avec plf reste meilleure dans tous les cas que l’optimisation sans plf, même si la valeur ajoutée est plus faible que pour les partitions brutes.
• Les fluctuations de et de dans les quatre cas semble montrer qu’il risque d’être difficile de déterminer à l’avance le meilleur parcours d’optimisation (problème dû à l’utilisation d’un algorithme glouton).