Article de référence | Réf : AF1527 v1

Le classement des sommets dans les réseaux

Auteur(s) : Claude Brezinski, Michela Redivo-Zaglia

Date de publication : 10 avr. 2017

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

Cet article expose l’un des principaux algorithmes numériques qui, dès l’origine des moteurs de recherche sur le Web, se cache derrière le classement des pages selon leur ordre de pertinence décroissante. Il décrit les méthodes d’analyse numérique qui sont utilisées pour effectuer ce classement, quelles sont leurs propriétés, comment en accélérer la convergence et comment des procédures d’extrapolation et d’approximation permettent de les améliorer. D’autres applications de ces algorithmes à divers graphes et réseaux ainsi que des généralisations récentes sont également mentionnées.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

The Ranking of Nodes in Networks

This article describes one of the main numerical algorithms search engines have always used for ranking Web pages by relevance. It goes on to look at the numerical analysis methods used for performing this ranking, their properties, how to speed up their convergence, and the extrapolation and approximation procedures by which they can be improved. Other applications of these algorithms to graphs and networks are also described, together with new generalizations.

Auteur(s)

  • Claude Brezinski : Professeur - Laboratoire Paul Painlevé, UMR CNRS 8524, UFR de Mathématiques Pures et Appliquées, - Université de Lille – Sciences et Technologies, Villeneuve d’Ascq, France

  • Michela Redivo-Zaglia : Professeur - Dipartimento di Matematica “Tullio Levi-Civita”, - Università degli Studi di Padova, Padova, Italy

INTRODUCTION

Quand on insère des mots-clés dans un moteur de recherche sur le Web, on obtient les pages par ordre décroissant de pertinence. Ce classement n’est pas effectué pour chaque utilisateur à chacune de ses requêtes, mais le moteur de recherche procède de temps en temps à un classement général de toutes les pages du Web selon leur importance. Quand des mots-clés sont introduits, le moteur recherche les pages qui correspondent à la question posée dans cette liste classée complète.

Un problème mathématique et des algorithmes numériques se cachent derrière un tel classement. Les moteurs de recherche utilisent plusieurs stratégies pour effectuer ce classement, dont certaines relèvent du secret industriel. Nous allons exposer ici l’algorithme le plus connu pour effectuer ce classement, l’algorithme PageRank, ainsi que les méthodes mathématiques auxquelles il fait appel. Comme nous le verrons plus loin, cet algorithme a beaucoup d’autres applications que le seul classement des pages du Web. Signalons que PageRank et Google sont des marques déposées.

Une partie de cet article est empruntée à et nous tenons à remercier les éditeurs du journal Matapli ainsi que la Société de Mathématiques Appliquées et Industrielles qui le publie. Ces résultas sont eux-mêmes issus des travaux des auteurs de cet article et sont cités dans la bibliographie.

Le problème des ponts de Königsberg a été résolu en 1736 par le mathématicien suisse Leonhard Euler (1707-1783) qui peut être considéré comme l’inventeur de la théorie des graphes. Cette ville est traversée par une rivière sur laquelle se trouvent deux îles. Sept ponts (les arêtes du graphe) relient les deux rives et les deux îles (les nœuds du graphe). Il s’agissait de trouver un parcours les reliant sans passer deux fois par le même pont. Le problème rencontré par le Web est de nature semblable mais à une toute autre échelle. Il a fallu forger les outils permettant de trouver la bonne information dans cette énorme masse de données, de les structurer et de trouver les nœuds les plus importants. De plus, sur le Web, les nœuds et les arêtes changent constamment.

On peut faire remonter les premières idées sur le classement d’informations aux travaux de Derek J. de Solla Price (1922-1983) en 1965 . Il s’agissait alors d’évaluer les articles scientifiques selon leur nombre de citations. Mathématiquement, il s’agit d’un problème de valeurs propres. On construit une matrice dont chaque élément (i,j) vaut 1 ou 0 selon que l’article i cite ou non l’article j. Il se peut donc que l’élément (i,j) vaille 1 alors que l’élément (j,i) vaut 0. Les articles étaient ainsi classés suivant leur nombre de citations.

Le premier moteur de recherche qui classifiait automatiquement les pages du Web afin d’identifier les plus pertinentes d’entre elles a été Altavista dans les années 1997-1998. Ce moteur recherchait le nombre d’occurrences des mots-clés introduits par l’utilisateur, leur proximité et leur positionnement dans le texte. Les limites de cette méthode de sélection ont conduit à la recherche d’autres critères de classification. On est ainsi passé à des critères indépendants du contenu des pages pour passer à des méthodes de tri basées sur la popularité. C’est sur la co-citation que se base l’algorithme HITS (Hyperlink-Induced Topic Search ou Hubs and authorities) développé par Jon M. Kleinberg, professeur à Cornell University , ou l’algorithme PageRank que nous allons exposer maintenant. Nous n’en donnerons ici qu’une description simplifiée alors que le procédé complet est bien plus complexe.

En 1996, deux étudiants de l’université de Stanford, Larry Page et Sergey Brin (ils seront les fondateurs de la société Google), proposèrent un nouvel algorithme de classement des pages du Web . Selon cet algorithme, l’importance d’une page est définie par son rang dans une liste, appelé PageRank (nous conserverons ici l’appelation anglo-saxonne). À l’heure actuelle, les moteurs de recherche sur Internet ne se contentent pas de ce seul algorithme, mais utilisent simultanément de nombreux autres facteurs de classement, environ 200. Récemment, ces algorithmes ont reçu des applications dans divers domaines qui seront évoqués à la fin de cet article.

Il existe différentes façons d’appréhender intuitivement l’idée dominante de PageRank. La première d’entre elles est de savoir que cet algorithme a été bâti afin d’utiliser la structure d’un graphe pour quantifier l’importance de chacun de ses nœuds. Les utilisations de cet algorithme, en dehors du contexte du Web, font cependant toutes appel à une notion d’importance qui, selon l’application, peut prendre des significations diverses.

On peut interpréter PageRank comme un fluide circulant dans un réseau, passant d’un nœud à l’autre par ses arêtes et mettant en relation les nœuds les plus importants. Une autre interprétation consiste à le penser en termes de suffrages : un nœud acquiert les votes des autres nœuds le long des arêtes entrantes, et il donne sa voix à des nœuds plus importants, ceux qui ont intuitivement le plus de valeur. Enfin, une autre façon de penser l’algorithme est en termes de marche aléatoire à travers un réseau. Le PageRank d’un certain nœud est simplement la probabilité de se retrouver à ce nœud après être parti d’un nœud quelconque dans le réseau et en circulant pas à pas dans le graphe après avoir sélectionné une arête aléatoire à chaque nœud. C’est la simplicité et l’élégance de PageRank et le fait qu’il utilise uniquement la structure d’un graphe qui en font un outil qui peut être appliqué à d’autres réseaux.

Nous avons volontairement limité la bibliographie car elle est très vaste. On en trouvera une bonne partie dans . Un certain nombre de notions simples d’algèbre linéaire sont nécessaires pour aborder cet article (voir [AF1221]).

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

ranking of nodes   |   PageRank   |   Markov chains   |   graphs

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1527


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - BARABÁSI (A.-L.), RÉKA (A.) -   Emergence of scaling in random networks.  -  Science, 286, 509-512 (1999).

  • (2) - BOLDI (P.), SANTINI (M.), VIGNA (S.) -   PageRank as a function of the damping factor,  -  in Proc. of the Fourteenth International World Wide Web Conference, ACM Press, pp. 557-566, (2005).

  • (3) - BREZINSKI (C.), REDIVO-ZAGLIA (M.) -   Extrapolation Methods. Theory and Practice,  -  North-Holland, Amsterdam, (1991).

  • (4) - BREZINSKI (C.), REDIVO-ZAGLIA (M.) -   The PageRank vector : properties, computation, approximation, and acceleration,  -  SIAM J. Matrix Anal. Appl., 28, 551–575 (2006).

  • (5) - BREZINSKI (C.), REDIVO-ZAGLIA (M.) -   Rational extrapolation for the PageRank vector,  -  Math. Comp., 77, 1585-1598 (2008).

  • (6) - BREZINSKI (C.), REDIVO-ZAGLIA...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS