La structure du web est en forme de « noeud papillon »

Au sein du Laboratoire Almaden d’IBM il est rare de voir des chercheurs se lancer tête baissée dans de la recherche appliquée avant d’avoir passé beaucoup de temps (en général des années) à étudier tous les aspects du domaine de recherche. Ce respect pour la recherche fondamentale constitue l’une des caractéristiques de la recherche chez Big Blue (on le retrouve aussi au sein du laboratoire PARC de Xerox, ces deux labos privés constituant des exceptions dans le secteur informatique, qui préfère en général la recherche appliquée).

Ceci explique pourquoi l’équipe d’Andrew Tomkins et de Ravi Kumar ont entrepris en priorité , dès le début de leurs travaux, d’étudier la structure du web. Comment en effet créer des moteurs de recherche efficace, si on ne sait pas répondre à cette question simple : à quoi ressemble la Toile ? Comment sont reliées les pages entre elles ? Que se passe-t’il si on « crawle » la Toile : peut on aspirer tous les sites, où certains resteront-ils inaccessibles ?

Les approches de l’équipe du Laboratoire Almaden

L’équipe d’Andrew Tomkins travaillait à l’époque sur trois problèmes différents :
- la recherche thématique
- le dénombrement des thématiques différentes
- la classification dans une thématique donnée

Le problème de la recherche thématique consistait simplement à trouver une solution au problème suivant : soit une requête sur un thème donné, comment renvoyer une liste de pages pertinentes contenant de l’information en rapport avec cette requête ? En 1999, l’algorithme utilisé était HITS de Jon M. Kleinberg, co-signataire de la première version de l’article. [1]

Le second problème consistait en fait à détecter, au sein du web, des zones fortement liées entre elles par des liens réciproques(« bipartite cores »). Ces zones révèlent, à la fois l’existence de « communautés », mais aussi de « sujets » auxquels ces commmunautés s’intéressent ;

Et la dernière approche consistait, pour une page donnée à reconnaître
à quelle thématique la rattacher…

Ces trois approches avaient un point commun : la résolution des problèmes posés passait par l’utilisation poussée de la théorie des graphes orientés. Mais avant de savoir quels outils mathématiques étaient applicables à la Toile, il était intéressant de s’intéresser aux propriétés caractéristiques du « Web en tant que graphe » [2]. Dans les propriétés intéressantes, il s’agissait notamment de mesurer le niveau de « connexité » des graphes, et le nombre de degrés entrants et sortants sur une page donnée.

Les mesures effectuées par Broder et al.

Le graphique en noeud papillon résulte des travaux réalisés par Ravi Kumar, un chercheur du laboratoire d’Almaden, avec l’aide d’Andrei Broder et de Farzin Maghoul, du moteur de recherche Altavista.

Les chercheurs ont analysé les résultats des crawls d’Altavista entre mai octobre 1999.
La taille de l’index utilisé était à l’époque de 200 millions de pages et 1,5 milliards de liens

Les résultats : le graphique en forme de noeud papillon

Les résultats de cette étude de la structure du web aboutissent à plusieurs constats frappants.

Tout d’abord il existe une zone du web composé de pages fortement liées entre elle (la zone SCC (strongly connected component). Dans cette zone, toute page est accessible en suivant les liens émanant de pages de la même zone (même s’il faut suivre plusieurs centaines de liens pour y parvenir). Cette zone comporte 56 millions de pages.

Une deuxième zone de taille plus réduite : 44 million de noeuds (IN) est composée de pages qui permettent d’accéder aux pages de la zone SCC, mais qui ne sont pas accessibles depuis les pages de la zone SCC.

Une troisième zone (OUT), de taille équivalente à IN (44 millions de noeuds) est composée à l’inverse de pages qui sont accessibles depuis la zone SCC, mais les pages de OUT ne renvoient pas vers les pages SCC…

C’est en dessinant le schéma représentant ces trois zones que les chercheurs d’Almaden ont abouti à cette forme de noeud papillon [3]


L’étude du web a permis également de révéler trois autres stuctures :

Des composants isolés : certaines zones du web sont isolées des zones principales SCC, IN et OUT. Aucun lien n’y mène, et aucun lien ne relie ces pages aux zones principales.

Les tubes : certaines zones du web, de taille plus réduites, relient les pages de la zone IN directement aux pages de la zone OUT, sans passer par la zone SCC…

Les vrilles : il s’agit de zones atypiques qui relient des sites isolés de l’ensemble, soit à la zone OUT, soit à la zone IN. Ces zones parfois éloignées s’étendent comme des « pseudopodes » ou des « vrilles de vigne » d’où leur nom… Les vrilles contiennent autant de pages que IN ou OUT

L’un des résultats les plus frappants de l’étude, c’est qu’il n’existe pas, en règle générale un chemin qui permet d’aller d’une page A du web à une page B en suivant les liens hypertextes. Cette propriété est l’apanage de la zone SCC, mais la zone SCC ne contient qu’un minorité de sites web…

Cela laisse songeur… Surtout quand on se remémore comment fonctionnent les crawlers des moteurs de recherche, c’est à dire en suivant les liens contenus dans les pages déjà indexées…

Le web a-t’il toujours la forme d’un noeud papillon ?

Rien n’est moins sûr… En quatre ans, le web a beaucoup changé, et Broder et al. n’avaient en plus analysé que l’index d’Altavista et ce que Scooter [4] voyait à l’époque, c’est à dire pas grand chose…

On peut supposer sans prendre trop de risques que les zones SCC, IN et OUT, les tubes, les vrilles et les composants isolés continuent d’exister… Mais leur taille peut avoir sensiblement évolué.

Ces résultats ont en tout cas ouvert la porte à d’autres études ( notamment sur les portions cachées du web) et révélé que la Toile n’est pas un tout uniforme : même au niveau macroscopique, la Toile est structurée en zones distinctes. Et il vaut mieux en tenir compte lorsque l’on envisage de crawler le web entier, pour faire un moteur de recherche grand public par exemple…

Philippe YONNET

Bibliographie :

Graph structure in the web / Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener

The Web as a graph / Jon M. Kleinberg – Ravi Kumar – Prabhakar Raghavan – Sridhar Rajagopalan – D. Sivakumar – Andrew Tomkins – Eli Upfal (version de 1999)

The Web as a graph / Ravi Kumar – Prabhakar Raghavan – Sridhar Rajagopalan – D. Sivakumar – Andrew Tomkins – Eli Upfal (version de 2000)

L’algorithme HITS et le projet CLEVER / Philippe YONNET – décembre 2003

Webfountain d’IBM / Philippe YONNET – novembre 2003


[1] En 2000, l’équipe du projet CLEVER d’IBM avait abandonné cet algorithme au profit d’une version fortement modifiée de HITS, et Jon M. Kleinberg a disparu des signataires des version réactualisées de l’article

[2] Le titre de l’article allait de soi dans ce contexte

[3] toute autre forme aurait fait l’affaire. Mais force est de constater que cela s’est révélé être une trouvaille… Car l’analogie a frappé les esprits, et donné à ces résultats un habillage compatible avec les réflexes des médias. Et l’article a été commenté d’abord dans les revues de vulagarisation scientifiques. Puis, lorsqu’IBM s’est aperçu que la mayonne prenait, Big Blue a commencé à « communiquer » sur ces résultats dans les médias grand public, où l’image du web en forme de noeud papillon à rencontré un succès certain !

[4] le crawler d’Altavista