Math
Marches aléatoires et PageRank
Suivez la masse de probabilité à travers un graphe dirigé et comparez l'itération de puissance avec une foule de marcheurs aléatoires. La téléportation peut faire converger PageRank vers une distribution unique. Comparez un cycle périodique avec un graphe dont les nœuds pendentifs non corrigés fuient la masse.
Ce qui se passe
Les barres montrent la distribution à l'étape actuelle; Les fines barres montrent un ensemble de marcheurs. Ce n'est pas la fraction de temps passée à chaque nœud par un marcheur. Sur un cycle dirigé, une distribution concentrée à un nœud continue de circuler, tandis que les fractions d'occupation à long terme peuvent encore approcher la distribution stationnaire uniforme.
Avec une probabilité de téléportation positive et des rangées pendantes patchées, la matrice de transition est stochastique et tous les nœuds communiquent : la distribution stationnaire est unique et les itérations convergent. Laisser une ligne suspendue vide crée un modèle sub-stochastique qui fuit. Sa solution de référence est désactivée ici; Cela ne signifie pas que chaque graphe sous-stochastique manque d'une distribution stationnaire.
Le module d'autovaleur sous-dominant décrit le taux de décroissance exponentielle asymptotique lorsque la convergence se produit. Les étapes individuelles peuvent osciller, et les états initiaux spéciaux peuvent manquer le mode le plus lent. Essayez un départ ponctuel, un départ uniforme et différentes valeurs d'amortissement.
Équations du module
Équations marche : P[i][j] = w[i][j] / (somme sur j de w[i][j]) ; une ligne de zéros est un nœud PENDANT matrice de Google : G = d·P + (1 − d)/n, une ligne pendante étant remplacée par la ligne uniforme stationnaire : pi·G = pi avec sum(pi) = 1 ; atteinte par la méthode de la puissance, et résolue directement comme vérification convergence : l'erreur décroît comme |lambda_2|^n, donc |lambda_2| EST le taux - mais la taille du pas ne le suit qu'en moyenne, car une paire sous-dominante complexe fait TOURNER la décroissance (la moyenne géométrique des rapports de pas le retrouve, la moyenne arithmétique est 1.5 % trop haute) borne d'amortissement : |lambda_2| = d·|mu_2(P)| exactement, donc |lambda_2| ≤ d est une INÉGALITÉ - mesurée à 5.0e-16, lâche d'un facteur 0.667 sur le petit web, serrée sur un cycle où |mu_2| = 1 puits de rang : si la ligne pendante est laissée vide, la masse totale décroît vers zéro - le rang s'échappe entièrement du système périodique : un n-cycle orienté a pour valeurs propres les racines n-ièmes de l'unité, toutes de module 1 ; à partir d'un départ ponctuel il revient à ce point tous les n pas et ne se stabilise jamais non orienté : la marche est réversible et pi vaut simplement degré / 2|E| - une ligne d'arithmétique, et la vérification que l'itération résout bien ce qu'elle prétend résoudre
