Un scientifique découvre un algorithme de type PageRank des années 1940

L'algorithme PageRank est un élément clé de la méthode de Google pour classer les pages Web dans les résultats de recherche. Il utilise le réseau de liens entre les pages Web pour déterminer leur valeur et, notoirement, juge une page importante si elle est liée par d'autres pages importantes.

Une caractéristique cruciale de cette idée est qu'elle nécessite une approche itérative pour réévaluer constamment la valeur d'une page à mesure que l'importance des autres varie. Les algorithmes de classement itératif sont depuis devenus une partie importante de la théorie des réseaux.

PageRank a été développé en 1998 par les fondateurs de Google, Sergey Brin et Larry Page et son impact a été tel qu'il est facile d'oublier que l'approche n'était pas entièrement nouvelle. Massimo Franceschet de l'Université d'Udine en Italie souligne que l'idée a été exploitée avec succès à plusieurs reprises dans la science du 20e siècle, même avant la naissance de Brin et Page. Aujourd'hui, il présente un bref historique des algorithmes de classement itératif et trace leur évolution avant l'émergence de Google.

Il commence dans l'ordre chronologique inverse avec les travaux de Jon Kleinberg, informaticien à l'Université Cornell, qui a développé une approche presque identique du PageRank, quelques années plus tôt. Brin et Page font même référence à son travail dans leur célèbre article présentant le PageRank.

Kleinberg a appelé son algorithme Hypertext Induced Topic Search ou HITS et il a traité les pages Web comme des hubs et des autorités. Il a utilisé la définition circulaire selon laquelle les autorités sont des pages vers lesquelles pointent les hubs et les hubs sont des pages qui pointent vers des autorités et nécessitent une approche itérative pour résoudre.

À l'époque exaltante du boom des dotcom à la fin du 20e siècle, avant que Google ne connaisse un tel succès, le travail de Kleinberg a reçu une couverture médiatique considérable.

Franceschet examine également le travail de Gabriel Pinski et Francis Narin qui ont développé une manière de classer les revues. Leur règle était qu'une revue est importante si elle est citée par d'autres revues importantes. Comme PageRank et HITS, cela nécessite une méthode itérative pour exploiter la structure des liens entre les revues pour arriver à un classement.

Bien avant cela, cependant, Charles H Hubbell de l'Université de Californie à Santa Barbara, analysait les réseaux sociaux d'une manière similaire. En 1965, il a publié une technique pour déterminer l'importance des individus en fonction de l'importance des personnes qui les soutiennent. Cela a à nouveau la définition circulaire caractéristique et la solution itérative. Hubbell est reconnu par beaucoup, y compris Kleinberg, comme un pionnier de la théorie du classement itératif.

Mais la grande surprise est la découverte par Franceschet d'un précurseur encore plus ancien du PageRank dans les travaux de l'économiste de Harvard Wassily Leontief. En 1941, Leontief a publié un article dans lequel il divise l'économie d'un pays en secteurs qui fournissent et reçoivent des ressources les uns des autres, mais pas dans une mesure égale. Une question importante est : quelle est la valeur de chaque secteur lorsqu'ils sont si étroitement intégrés ? La réponse de Léontief a été de développer une méthode itérative de valorisation de chaque secteur en fonction de l'importance des secteurs qui l'alimentent. Semble familier? En 1973, Léontief a reçu le prix Nobel d'économie pour ce travail.

Ce qui est clair, c'est que les idées derrière le PageRank ont ​​une histoire vénérable, mais la surprise est qu'elles remontent au moins aux années 1940. Il sera intéressant de voir si quelqu'un peut trouver un travail similaire antérieur à cela.

Réf : arxiv.org/abs/1002.2858 : PageRank : Tenez-vous sur les épaules des géants

cacher