PageRank (Français)

L’algorithme PageRank produit une distribution de probabilité utilisée pour représenter la probabilité qu’une personne cliquant aléatoirement sur des liens arrive à une page particulière. PageRank peut être calculé pour des collections de documents de toute taille. Il est supposé dans plusieurs articles de recherche que la distribution est répartie uniformément entre tous les documents de la collection au début du processus de calcul., Les calculs de PageRank nécessitent plusieurs passages, appelés « itérations », à travers la collection pour ajuster les valeurs approximatives de PageRank afin de refléter plus étroitement la valeur réelle théorique.

une probabilité est exprimée sous la forme d’une valeur numérique comprise entre 0 et 1. Une probabilité de 0,5 est généralement exprimée comme une « chance de 50% » que quelque chose se produise. Par conséquent, un document avec un PageRank de 0,5 signifie qu’il y a 50% de chances qu’une personne cliquant sur un lien aléatoire soit dirigée vers ledit document.

algorithme Simplifiémodifier

supposons un petit univers de quatre pages web: A, B, C et D., Les liens d’une page vers elle-même sont ignorés. Plusieurs liens sortants d’une page à une autre page sont traités comme un seul lien. PageRank est initialisé à la même valeur pour toutes les pages. Dans la forme originale de PageRank, la somme de PageRank sur toutes les pages était le nombre total de pages sur le web à ce moment-là, de sorte que chaque page dans cet exemple aurait une valeur initiale de 1. Cependant, les versions ultérieures de PageRank, et le reste de cette section, supposent une distribution de probabilité entre 0 et 1. Par conséquent, la valeur initiale pour chaque page dans cet exemple est 0.25.,

le PageRank transféré d’une page donnée aux cibles de ses liens sortants lors de l’itération suivante est divisé également entre tous les liens sortants.

Si les seuls liens du système provenaient des pages B, C et D vers A, chaque lien transférerait 0,25 PageRank vers A lors de l’itération suivante, pour un total de 0,75.

P R (A) = P R ( B) + P R ( C) + P R ( D). {\displaystyle PR(A)=PR(B)+PR(C)+PR (D).\ ,}

supposons plutôt que la page B ait un lien vers les pages C et A, que la page C ait un lien vers la page A et que la page D Ait des liens vers les trois pages., Ainsi, lors de la première itération, la page B transférerait la moitié de sa valeur existante, soit 0,125, à la page A et l’autre moitié, soit 0,125, à la page C. La Page C transférerait toute sa valeur existante, soit 0,25, à la seule page à laquelle elle renvoie, A. puisque D avait trois liens sortants, elle transférerait un tiers de sa valeur existante, soit environ 0,083, à A. à la fin de cette itération, la page A aura un PageRank d’environ 0,458.

P R (A) = P R ( B ) 2 + P R ( C ) 1 + P R (D ) 3 . {\displaystyle PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.,\ ,}

en d’autres termes, le PageRank conféré par un lien sortant est égal au score de PageRank du document divisé par le nombre de liens sortants L( ).

P R (A) = P R ( B) L ( B) + P R ( C) L ( C) + P R ( D) L ( D). {\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\ ,}

dans le cas général, la valeur PageRank pour toute page u peut être exprimée comme suit:

P r ( u ) = ∑ v ∈ B u P R ( v ) L ( v ) {\displaystyle PR(u)=\sum _{V\in B_{u}}{\frac {PR(v)}{L(v)}}},

c’est-à-dire, la valeur de PageRank pour une page u dépend des valeurs de PageRank pour chaque page v contenue dans l’ensemble Bu(l’ensemble contenant toutes les pages reliant à la page u), divisé par le nombre L (v) de liens de la page v.

facteur D’amortissement edit

La théorie du PageRank soutient qu’un internaute imaginaire qui La probabilité, à n’importe quelle étape, que la personne continue est un facteur d’amortissement d. Diverses études ont testé différents facteurs d’amortissement, mais il est généralement admis que le facteur d’amortissement sera fixé autour de 0,85.,

Le facteur d’amortissement est soustraite à partir de 1 (et dans certaines variantes de l’algorithme, le résultat est divisé par le nombre de documents (N) dans la collection), et ce terme est ensuite ajoutée au produit du facteur d’amortissement et la somme des entrants score de PageRank. C’est − à-dire

P R ( A ) = 1-d N + d ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ) . {\displaystyle PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}

donc, le PageRank de n’importe quelle page est dérivé en grande partie des PageRanks des autres pages., Le facteur d’amortissement ajuste la valeur dérivée vers le bas. Le document original, cependant, a donné la formule suivante, ce qui a conduit à une certaine confusion:

P R ( A ) = 1 − d + d ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ) . {\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}

la différence entre eux est que les valeurs de PageRank dans la première formule sont égales à un, tandis que dans la deuxième formule, chaque PageRank est multiplié par N et la somme devient N., Une déclaration dans le document de Page et Brin selon laquelle » la somme de toutes les PageRanks est une  » et les affirmations d’autres employés de Google soutiennent la première variante de la formule ci-dessus.

Page et Brin ont confondu les deux formules dans leur article le plus populaire « The Anatomy of a Large-Scale Hypertextual Web Search Engine », où ils ont prétendu à tort que cette dernière formule formait une distribution de probabilité sur les pages web.

Google recalcule les scores PageRank chaque fois qu’il explore le Web et reconstruit son index., Comme Google augmente le nombre de documents dans sa collection, l’approximation initiale de PageRank diminue pour tous les documents.

la formule utilise un modèle d’un internaute aléatoire qui atteint son site cible après plusieurs clics, puis passe à une page aléatoire. La valeur PageRank d’une page reflète la chance que l’internaute aléatoire atterrisse sur cette page en cliquant sur un lien. Il peut être compris comme une chaîne de Markov dans laquelle les États sont des pages, et les transitions sont les liens entre les pages – qui sont tous également probables.,

si une page n’a pas de liens vers d’autres pages, elle devient un évier et met donc fin au processus de navigation aléatoire. Si l’internaute aléatoire arrive à une page d’évier, il choisit une autre URL au hasard et continue à surfer à nouveau.

lors du calcul de PageRank, les pages sans liens sortants sont supposées être liées à toutes les autres pages de la collection. Leurs scores PageRank sont donc répartis de manière égale entre toutes les autres pages. En d’autres termes, pour être juste avec les pages qui ne sont pas des puits, ces transitions aléatoires sont ajoutées à tous les nœuds du Web. Cette probabilité résiduelle, d, est généralement définie sur 0.,85, estimé à partir de la fréquence à laquelle un internaute moyen utilise la fonction de signet de son navigateur. Ainsi, l’équation est la suivante:

P R ( P i ) = 1 − d N + D ∑ p J ∈ M ( p I ) P R ( P j ) L ( P j ) {\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{l(p_{j})}}}

le les valeurs PageRank sont les entrées du vecteur propre droit dominant de la matrice d’adjacence modifiée redimensionnée de sorte que chaque colonne en ajoute une.,_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R} } ∑ i = 1 N ℓ ( p i , p j ) = 1 {\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1} ,

i.,e. les éléments de chaque colonne de la somme jusqu’à 1, donc la matrice est une matrice stochastique (pour plus de détails, voir le calcul ci-dessous). Il s’agit donc d’une variante de la mesure de centralité du vecteur propre couramment utilisée dans l’analyse de réseau.

en raison de la grande portée propre de la matrice d’adjacence modifiée ci-dessus, les valeurs du vecteur propre PageRank peuvent être approximées avec un haut degré de précision en seulement quelques itérations.,

Les fondateurs de Google, dans leur article original, ont rapporté que L’algorithme PageRank pour un réseau composé de 322 millions de liens (in-edges et out-edges) converge vers une limite tolérable en 52 itérations. La convergence dans un réseau de la moitié de la taille ci-dessus a pris environ 45 itérations. Grâce à ces données, ils ont conclu que l’algorithme peut être très bien mis à l’échelle et que le facteur de mise à l’échelle pour les réseaux extrêmement grands serait à peu près linéaire dans log n n {\displaystyle \log n} , où n est la taille du réseau.,

à la suite de la théorie de Markov, on peut montrer que le PageRank d’une page est la probabilité d’arriver à cette page après un grand nombre de clics. Cela arrive à T − 1 égal {\displaystyle T^{-1}} où t {\displaystyle T} est l’attente du nombre de clics (ou de sauts aléatoires) requis pour revenir de la page à elle-même.

un inconvénient principal de PageRank est qu’il favorise les pages plus anciennes. Une nouvelle page, même très bon, n’aura pas beaucoup de liens, sauf si elle fait partie d’un site existant (un site densément connecté à un ensemble de pages, comme Wikipédia).,

Plusieurs stratégies ont été proposées pour accélérer le calcul du PageRank.

diverses stratégies de manipulation de PageRank ont été utilisées dans des efforts concertés pour améliorer le classement des résultats de recherche et monétiser les liens publicitaires. Ces stratégies ont gravement affecté la fiabilité du concept PageRank, qui vise à déterminer quels documents sont réellement très appréciés par la communauté Web.,

Depuis décembre 2007, Lorsqu’il a commencé à pénaliser activement les sites vendant des liens texte payants, Google a combattu les fermes de liens et autres systèmes conçus pour gonfler artificiellement PageRank. La façon dont Google identifie les fermes de liens et autres outils de manipulation de PageRank fait partie des secrets commerciaux de Google.

ComputationEdit

PageRank peut être calculé de manière itérative ou algébrique. La méthode itérative peut être considérée comme la méthode d’itération de puissance ou la méthode de puissance. Les opérations mathématiques de base effectuées sont identiques.,

IterativeEdit

À t = 0 {\displaystyle t=0} , une première distribution de probabilité est supposé, en général,

P R ( p i ; 0 ) = 1 N {\displaystyle PR(p_{i};0)={\frac {1}{N}}} .

où N est le nombre total de pages, et p i ; 0 {\displaystyle p_{i};0} est la page i au temps 0.,

(1)

The matrix M {\displaystyle {\mathcal {M}}} is defined as

M i j = { 1 / L ( p j ) , if j links to i 0 , otherwise {\displaystyle {\mathcal {M}}_{ij}={\begin{cases}1/L(p_{j}),&{\mbox{if }}j{\mbox{ links to }}i\ \\0,&{\mbox{otherwise}}\end{cases}}}

i.,e.,

M := ( K − 1 ) T {\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}} ,

lorsqu’Un {\displaystyle A} désigne la matrice d’adjacence du graphe et K {\displaystyle K} est la matrice diagonale avec les outdegrees dans la diagonale.

le calcul de probabilité est effectué pour chaque page à un point temporel, puis répété pour le point temporel suivant. Le calcul se termine lorsque, pour une petite ϵ {\displaystyle \epsilon }

| R ( t + 1 ) − R ( t ) | < ϵ {\displaystyle |\mathbf {R} (t+1)-\mathbf {R} (t)|<\epsilon } ,

c’est à dire, lorsque la convergence est supposé.,

AlgebraicEdit

—For t → ∞ {\displaystyle t\to \infty } (i.e., in the steady state), the equation (1) reads

(2)

The solution is given by

R = ( I − d M ) − 1 1 − d N 1 {\displaystyle \mathbf {R} =(\mathbf {I} -d{\mathcal {M}})^{-1}{\frac {1-d}{N}}\mathbf {1} } ,

with the identity matrix I {\displaystyle \mathbf {I} } .,

La solution existe et est unique pour 0 < d < 1 {\displaystyle 0<d<1} . Cela peut être vu en notant que M {\displaystyle {\mathcal {m}}} est par construction une matrice stochastique et a donc une valeur propre égale à un en conséquence du théorème de Perron–Frobenius.,

Power methodEdit

(3)

x ( t + 1 ) = M ^ x ( t ) {\displaystyle x(t+1)={\widehat {\mathcal {M}}}x(t)} ,

until

| x ( t + 1 ) − x ( t ) | < ϵ {\displaystyle |x(t+1)-x(t)|<\epsilon } .,

Notez que dans l’équation (3) la matrice sur le côté droit dans la parenthèse peut être interprété comme

1 − d N E = ( 1 − d ) P 1 t {\displaystyle {\frac {1-d}{N}}\mathbf {E} =(1-d)\mathbf {P} \mathbf {1} ^{t}} ,

où P {\displaystyle \mathbf {P} } s’agit d’une première distribution de probabilité. Dans le cas actuel

P := 1 N N 1 {\displaystyle \mathbf {P} :={\frac {1}{N}}\mathbf {1} } .,therwise {\displaystyle \mathbf {D} _{i}={\begin{cases}1,&{\mbox{if }}L(p_{i})=0\ \\0,&{\mbox{otherwise}}\end{cases}}}

In this case, the above two computations using M {\displaystyle {\mathcal {M}}} only give the same PageRank if their results are normalized:

R power = R iterative | R iterative | = R algebraic | R algebraic | {\displaystyle \mathbf {R} _{\textrm {power}}={\frac {\mathbf {R} _{\textrm {iterative}}}{|\mathbf {R} _{\textrm {iterative}}|}}={\frac {\mathbf {R} _{\textrm {algebraic}}}{|\mathbf {R} _{\textrm {algebraic}}|}}} .,

ImplementationEdit

Scala/Apache SparkEdit

un exemple typique est l’utilisation de la programmation fonctionnelle de Scala avec Apache Spark RDD pour calculer itérativement les rangs de Page.

MATLAB/OctaveEdit

Exemple de code qui appelle la fonction rang définis ci-dessus:

M = ;rank2(M, 0.80, 0.001)

PythonEdit

Cet exemple prend ≈13 itérations pour converger.