Un point sur les brevets : Le Page Rank de Google

Nous en avons parlé le mois dernier dans cette lettre, Google détient un certain nombre de brevets  auprès de l’USPTO, organisme gérant les brevets aux Etats-Unis. Larry Page, co-fondateur de Google, est propriétaire (pour The Board of Trustees of the Leland Stanford Junior University) du brevet dénommé « Method for node ranking in a linked database » (numéro 6,285,999), qui décrit le principe du PageRank  (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/search-bool.html&r=1&f=G&l=50&co1=AND&d=ptxt&s1=’Page+Lawrence’.INZZ.&OS=IN/ »Page+Lawrence »&RS=IN/ »Page+Lawrence« ). On peut d’ailleurs s’étonner que ce brevet n’appartienne pas à Google mais à l’université de Stanford. Si Larry Page s’en allait de Google, qu’adviendrait-il de ses algorithmes de pertinence, fortement basés sur ce brevet ? Le mot « Google » n’est pas énoncé une seule fois dans le texte de ce brevet…

Nous nous sommes penché de façon approfondie sur les explications fournies sur le site de l’USPTO au sujet de ce brevet, afin de mieux comprendre les mécanismes de classement de pertinence de Google.

Voici ce qu’il y est expliqué : l’invention présentée dans le document se rapporte à l’analyse de l’interconnectivité de documents dans des bases de données comparables au Web. Plus particulièrement, elle se rapporte à la façon de donner des classements, des notes, à des « noeuds » de ces bases de données.

Le document relate tout d’abord un bref historique de la façon dont les algorithmes des moteurs de recherche ont été imaginés depuis le début du web, selon certains critères de pertinence :

– Nombre d’occurrence du mot demandé.

– Date de dernière modification du document.

– Proximité des termes demandés entre eux dans le document.

– Etc.

La première conclusion est que ces seules méthodologies ne sont pas assez précises pour fournir des résultats très pertinents. De plus, elles sont potentiellement fortement sujettes au spam.

Le projet HyperLink Search Engine (qui se trouvait à l’adresse http://rankdex.gari.com/, mais celle-ci ne répond plus) est cité par Larry Page comme l’un des premiers outils de recherche à avoir utilisé l’analyse des liens entrants d’une page pour identifier du contenu pertinent. Cet outil utilisait le texte du lien pointant vers le document pour caractériser la pertinence de ce dernier. Exemple :

Si un document A a mis en place un lien vers un document B avec le texte indiqué (le lien est proposé sur le mot « assurance »), le document B sera bien classé sur le mot clé contenu dans le texte du lien du document A (donc, ici, « assurance »).

Cette idée d’associer la pertinence d’un document au texte des liens pointant vers lui avait été implémentée dans un premier temps sur l’outil de recherche World Wide Web Worm (http://www.inf.utfsm.cl/~vparada/html/wwww.html), un très ancien (à l’échelle de l’Internet) moteur. Le but était de se servir non pas du contenu de la page en question pour la classer, mais plutôt de celui des pages pointant vers elle. Ingénieux…

Un calcul basé sur la récursivité

Le brevet déposé par Larry Page reprend l’idée de l’analyse des liens vers un document. Dans un premier temps, et de façon basique, il définit, pour un document A, un « taux de citation » r(A) égal au nombre N de pages ayant placé un lien vers lui :

r(A)=N

Mais, dans un univers hétérogène comme le Web, cette définition simpliste n’est pas satisfaisante. Il est nécessaire d’aller plus loin et de ne pas noter la simple quantité des liens, mais également leur « qualité ». C’est donc ici qu’entre en lice la notion de récursivité du calcul du PageRank : le PageRank d’une page dépend non seulement du nombre de liens pointant vers elle, mais également du PageRank des documents qui les contiennent.

Fichier PDF téléchargeable ici (la lettre Réacteur n’était à cette époque-là disponible que sous cette forme).