Skip to content
Retour aux résultats

Centralité PageRank

Introduite par
Page, Brin, Motwani & Winograd
Année
1999
Type
Iterative link-based centrality algorithm
Famille
Centrality

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

PageRank est un algorithme de centralité basé sur les liens qui attribue un score d'importance à chaque nœud dans un graphe orienté en mesurant combien de nœuds de haute qualité pointent vers lui.

Introduit par Larry Page, Sergey Brin, Rajeev Motwani et Terry Winograd à l'Université de Stanford en 1999, il est devenu le fondement mathématique du moteur de recherche Google et reste l'un des algorithmes les plus influents en science des réseaux et en recherche d'information.

L’intuition derrière la méthode

Imaginez un internaute aléatoire qui clique sur des liens au hasard, sautant occasionnellement vers une page complètement aléatoire plutôt que de suivre un lien. La fraction de temps que cet internaute passe sur chaque page, après un nombre infini de clics, est le PageRank de cette page. Une page visitée souvent — parce que de nombreuses pages populaires y mènent — reçoit un score élevé. Le facteur d'amortissement (typiquement 0,85) modélise la probabilité de continuer à cliquer plutôt que de sauter.

Histoire

PageRank a été développé à l'Université de Stanford par Larry Page et Sergey Brin comme mécanisme de classement principal de leur projet de recherche BackRub, devenu Google en 1998. Le rapport technique fondamental, co-écrit avec Rajeev Motwani et Terry Winograd, a été publié en 1999. L'algorithme a popularisé l'utilisation de la centralité basée sur les vecteurs propres dans les réseaux orientés à grande échelle et a directement inspiré des algorithmes d'analyse de liens ultérieurs, notamment HITS et TrustRank.

Quand l’utiliser

PageRank est approprié lorsque vous avez besoin de classer des nœuds dans un graphe orienté par leur importance structurelle globale, en particulier lorsque la direction des arêtes encode l'approbation ou l'influence (hyperliens, citations, suivis sociaux). Il suppose que le graphe peut être modélisé comme une chaîne de Markov et nécessite une composante connexe ou fortement connexe pour une convergence nette. Il est moins adapté aux réseaux non orientés où HITS ou la centralité d'intermédiarité peuvent être préférés, et il peut être sensible au spam de liens ou à un degré entrant artificiellement gonflé.

Limites et points d’attention

  • Nécessite un graphe orienté ; l'application aux réseaux non orientés nécessite des choix de convention
  • La vitesse de convergence dépend du gap spectral de la matrice de transition et peut être lente pour des graphes mal connectés
  • Sensible au choix du facteur d'amortissement d ; différentes valeurs peuvent modifier considérablement les classements
  • Vulnérable à la manipulation par fermes de liens et aux liens entrants artificiellement construits

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Fondation probabiliste principielle via le modèle de chaîne de Markov de l'internaute aléatoire
  • Évolutivité à de très grands graphes grâce aux produits matrice-vecteur creuse et à l'itération de puissance
  • Capture la topologie globale du graphe, récompensant les nœuds approuvés par d'autres nœuds à score élevé
  • Largement validé dans les domaines du web, des citations, de la biologie et des réseaux sociaux

Applications

  • Classement des moteurs de recherche web : ordonnancement des résultats de recherche par l'autorité globale des pages web
  • Analyse des citations académiques : identification des articles ou revues influents dans les réseaux de littérature scientifique
  • Mesure de l'influence sur les réseaux sociaux : classement des utilisateurs par le prestige de leurs abonnés
  • Analyse des réseaux biologiques : identification des protéines ou gènes centraux dans les réseaux d'interaction protéique et de régulation génique
  • Systèmes de recommandation : propagation de signaux de préférence à travers des graphes bipartis utilisateurs-articles

Comment ça marche

Comment ça marche

1

Chaque nœud du graphe commence avec un score PageRank égal de 1/N, où N est le nombre total de nœuds. Cette initialisation uniforme garantit qu'aucun nœud n'a d'avantage artificiel et fournit une distribution de probabilité valide sur le réseau avant la première itération.

Formule
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

Une matrice de transition stochastique par colonne M est construite à partir de la structure d'adjacence du graphe. Chaque entrée M_ij est égale à 1 divisé par le degré sortant du nœud j s'il existe une arête de j vers i, et zéro sinon. Les nœuds pendants (sans arêtes sortantes) sont généralement traités en redistribuant leur score uniformément sur tous les nœuds.

Formule
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

Le vecteur PageRank est mis à jour itérativement en utilisant la formule de l'internaute aléatoire. Avec un facteur d'amortissement d (par défaut 0,85), chaque nœud reçoit une probabilité de téléportation de base (1-d)/N plus d fois la somme pondérée des scores contribués par tous les nœuds qui y mènent. Cette étape est répétée jusqu'à ce que les scores se stabilisent.

Formule
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

Après chaque itération, la norme L1 du changement du vecteur de scores est comparée à une petite tolérance epsilon (par exemple, 1e-6). Lorsque le changement tombe en dessous de ce seuil, l'algorithme a convergé et le vecteur de scores actuel est renvoyé comme distribution PageRank finale.

Formule
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

Pièges courants

  • Ignorer les nœuds pendants (nœuds sans arêtes sortantes) peut briser la propriété stochastique de la matrice de transition et entraîner des scores incorrects
  • Utiliser PageRank sur des graphes non orientés sans conversion en un modèle de transition symétrique peut produire des estimations de centralité trompeuses
  • Définir la tolérance trop lâche conduit à une convergence prématurée ; trop serrée augmente le calcul sans changements de score significatifs
  • Interpréter PageRank comme une métrique d'importance absolue plutôt qu'un classement relatif dans le contexte d'un graphe spécifique

Questions fréquentes

Que représente le facteur d'amortissement d et comment doit-il être choisi ?

Le facteur d'amortissement d (typiquement 0,85) est la probabilité que l'internaute aléatoire suive un lien plutôt que de se téléporter vers un nœud aléatoire. Les valeurs proches de 1 rendent l'algorithme plus sensible à la structure du graphe mais plus lent à converger et plus sujet aux puits de classement ; les valeurs proches de 0 approchent un classement uniforme. La valeur 0,85 a été validée empiriquement par Page et Brin pour le graphe web et est la valeur par défaut standard.

En quoi PageRank diffère-t-il de la centralité de degré ?

La centralité de degré ne compte que le nombre direct de liens entrants vers un nœud, traitant toutes les sources de manière égale. PageRank pondère chaque lien entrant par le score du nœud qui le crée, de sorte qu'une approbation d'un nœud très bien classé contribue plus qu'une approbation d'un nœud mal classé. Cette définition récursive capture la structure globale du graphe plutôt que la simple connectivité locale.

PageRank peut-il être appliqué aux graphes non orientés ?

Oui, mais avec des réserves. Un graphe non orienté doit être converti en une représentation orientée en remplaçant chaque arête non orientée par deux arêtes orientées. Les scores PageRank résultants sont alors égaux à une fonction du degré du nœud, réduisant l'algorithme à une centralité de degré pondérée. Pour les réseaux non orientés, des mesures de centralité alternatives telles que la centralité de vecteur propre ou la centralité d'intermédiarité sont souvent plus informatives.

Méthodes associées

Sources

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    Ouvrir la référence de la publication
    Copié.