Le moteur de recherche phénomène.
Avant son apparition, même si les moteurs de recherche étaient pratiques, leurs résultats laissés souvent à désirer. Il fallait faire le tri entre les site commerciaux et pornographiques pour trouver les sites réellement intéressants.
GoOgle à changer tout ça.
Comment ? Pourquoi ? Et bien avec une idée simple : il faut ordonner les résultats en fonction de leur pertinence et pas sur des critères abscons ou sans fondement comme l'ordre alphabétique.
Mais qu'est ce donc qu'un tri sur la pertinence ?
Dans une recherche sur le web, on peut voir la pertinence sous 2 aspects :
- Pertinence des pages trouvées vis à vis de la question ;
- Pertinence des pages trouvées dans l'absolue.
La pertinence vis à vis de la question est-elle formellement définissable ? Peut-on établir des critères efficaces sur la question ? L'expérience a prouvé, jusqu'à présent, que non.
Il ne nous reste plus que la pertinence absolue d'une page et ça comment fait-on ?
Topologie du web et classification des pages
Papillon
Certains chercheurs ont observé que l'on pouvait définir la topologie du web par suivant le schéma dit du papillon. Ce schéma présente le web comme composé de 3 sous-graphes aux propriétés différentes :
- L'ensemble des pages entrantes qui n'est à priori pas fortement connexe
- L'ensemble des pages sortantes qui n'est à priori pas fortement connexe
- L'ensemble des pages connexes, qui est à priori fortement connexe.
Les 2 premiers ensemble désignent les pages qui soient ne disposent d'aucun lien entrant et fournissent des liens vers des pages dans l'ensemble connexe (pages dites entrantes), soient ne disposent pas de lien sortants mais des liens entrant depuis l'ensemble connexe. Le premier ensemble peut être assimilé à un point d'entrée, tandis que le second peut être assimilé à un cul de sac.
À priori, les pages vraiment pertinentes devraient se trouver dans la composante fortement connexe et fondamentalement, c'est cette partie du web que les moteurs de recherche tente d'indexer. Mais pour l'instant, la caractéristique topologie du web n'est pas suffisante, il faut quelque chose de plus précis.
Hubs et Références
Les études sur le web ont découvert également 2 types de comportement pour une page web. Ces 2 comportements ne décrivent pas à eux seuls l'ensemble des pages connexes, mais par contre il fournit une idée de comment établir la pertinence d'une page.
Hubs : Une page est considérée comme un hub, si elle concentre une certaine quantité de liens vers d'autres pages (souvent liées entre elles par une thématique commune.) Les hubs agissent comme des annuaires.
Références : Une page est considérée comme une référence, si elle concentre une certaine quantité de lien entrant depuis d'autres pages. Une référence est une page citée par tous (ou par un grand nombre) et souvent fait en quelque sorte autorité sur un sujet.
Classification des Pages
En partant de l'observation précédente, on peut construire un modèle pour la pertinence d'une page. Plus une page est pointée par d'autre page, plus cette page peut être considérée comme pertinente, de plus les pages qui pointent sur elle sont pertinentes, plus cette page sera pertinente. Enfin, il faut aussi tenir compte (dans une moindre mesure) de la quantité de liens sortant et la pertinence des pages pointées.
Si l'on dispose du
graphe du web, on peut calculer cette
pertinence, par saturation et propagation sur le graphe. Il existe divers algorithme qui font ça, dont ceux utilisés par
GoOgle. Le principal, c'est que ces algorithmes construisent, en fait, pour chaque la probabilité que cette page soit rencontrée lors d'une
MarcheAleatoire infinie.
Le résultat est sans comparaison avec les techniques précédentes. Globalement, les pages
importantes sortent presque toujours parmi les premières, comme lors de l'une première démonstration de
GoOgle, où contrairement aux autres moteurs de recherche,
GoOgle proposait le site officiel du W3C en premier lien pour la requête "w3c" (ce qui parait logique tout de même ... )
Un Monde Parfait ?
Non, il existe principalement deux problèmes liés à cette technique :
- Le coût de l'indexation et de la classification des pages. Il y a 5 ans, on évalué le temps moyen pour reconstruire le graphe et recalculer la pertinence de chaque page à 3 semaines.
- L'auto-influence et la validité du modèle choisi. On peut se demander si le critère des liens entrants/sortants est correct, on peut aussi se demander si ce choix n'alimente pas artificiellement la cote de certaines pages.
Il existe plusieurs réponses au premier problème. Principalement,
GoOgle ne reconstruit pas complètement le graphe à chaque fois et il ne recalcule pas la pertinence de toutes les pages avec la même fréquence. L'idée est d'utiliser la vivacité des pages (la fréquence de leurs mise à jours) pour cibler les calculs les plus importants. Ce critère de vivacité peut aussi d'ailleurs enrichir la classification.
Le second problème est plus complexe. La question de la correction de cette méthode est fortement dépendante de la vision que l'on a du web. L'idée que défend cette approche, c'est que la diversité et la masse des pages sur le web garantissent dans une certaine mesure un avis global impartial sous la forme de ces liens entrants. Le seul soucis dans tout ça c'est l'effet secondaire des moteurs de recherche eux même : par exemple, un lien vers le résultat d'une recherche sur une page indexé, peut fausser l'évaluation des pages apparaissants dans la recherche. Je ne suis pas sûr que l'auto-influence des moteurs de recherche sur leur classification avait été étudiée.