PageRank (Română)

algoritmul PageRank afișează o distribuție de probabilitate utilizată pentru a reprezenta probabilitatea ca o persoană care face clic aleatoriu pe link-uri să ajungă la o anumită pagină. PageRank poate fi calculat pentru colecții de documente de orice dimensiune. În mai multe lucrări de cercetare se presupune că distribuția este împărțită uniform între toate documentele din colecție la începutul procesului de calcul., Calculele PageRank necesită mai multe treceri, numite „iterații”, prin colecție pentru a ajusta valorile aproximative PageRank pentru a reflecta mai îndeaproape valoarea teoretică adevărată.

o probabilitate este exprimată ca o valoare numerică între 0 și 1. O probabilitate de 0,5 este frecvent exprimată ca o” șansă de 50% ” de a se întâmpla ceva. Prin urmare, un document cu un PageRank de 0,5 înseamnă că există o șansă de 50% ca o persoană care face clic pe un link aleatoriu să fie direcționată către documentul respectiv.

algoritm Simplificatedit

presupunem un mic univers de patru pagini web: A, B, C și D., Linkurile de la o pagină la ea însăși sunt ignorate. Mai multe link-uri de ieșire de la o pagină la alta pagină sunt tratate ca un singur link. PageRank este inițializat la aceeași valoare pentru toate paginile. În forma originală a PageRank, suma PageRank peste toate paginile a fost numărul total de pagini de pe web la acel moment, astfel încât fiecare pagină din acest exemplu ar avea o valoare inițială de 1. Cu toate acestea, versiunile ulterioare ale PageRank, iar restul acestei secțiuni, își asumă o distribuție de probabilitate între 0 și 1. Prin urmare, valoarea inițială pentru fiecare pagină din acest exemplu este 0.25.,

PageRank-ul transferat de la o anumită pagină la țintele legăturilor sale de ieșire la următoarea iterație este împărțit în mod egal între toate legăturile de ieșire.

dacă singurele legături din sistem ar fi de la paginile B, C și D la A, fiecare legătură ar transfera 0.25 PageRank la A la următoarea iterație, pentru 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).\ ,}

Să presupunem că în schimb pagina B avea un link către paginile C și A, Pagina C avea un link către pagina A, iar pagina D avea legături către toate cele trei pagini., Astfel, la prima iterație, pagina B-ar transfera jumătate din valoare existente, sau 0.125, la pagina a și cealaltă jumătate, sau 0.125, la pagina C. Pagina C-ar transfera toate existente valoare, 0.25, la numai pagina e un link, A. Întrucât D a avut trei link-uri în străinătate, s-ar transfera o treime din valoare existente, sau aproximativ 0.083, la A. La finalizarea acestei iterație, O pagina va avea un PageRank de aproximativ 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}}.,\ ,}

cu alte cuvinte, PageRank conferit de o legătură de ieșire este egal cu propriul scor PageRank al documentului împărțit la numărul de legături de ieșire 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)}}.\,}

În cazul general, valoarea PageRank pentru orice pagină u poate fi exprimată ca:

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

de exemplu, PageRank-ul valoare pentru o pagină u este dependentă de PageRank valori pentru fiecare pagină v conținute în setul Bu (set care conține toate paginile conectarea la pagina de u), împărțit la numărul L(v) de link-uri de la pagina v.

Amortizare factorEdit

PageRank teorie susține că un imaginar surfer care este aleatoriu clic pe link-uri în cele din urmă va opri clic. Probabilitatea, la orice pas, că persoana va continua este un factor de amortizare d. diverse studii au testat diferiți factori de amortizare, dar se presupune, în general, că factorul de amortizare va fi stabilit în jurul valorii de 0,85.,

factorul de amortizare este scăzut de la 1 (și în unele variații ale algoritmului, rezultatul este împărțit la numărul de documente (N) din colecție) și acest termen este apoi adăugat la produsul factorului de amortizare și suma scorurilor PageRank primite. Aceasta este,

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 \peste N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \dreapta).}

deci PageRank-ul oricărei pagini este derivat în mare parte din PageRanks-urile altor pagini., Factorul de amortizare ajustează valoarea derivată în jos. Cu toate acestea, lucrarea originală a dat următoarea formulă, ceea ce a dus la o anumită confuzie:

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 \dreapta).}

diferența dintre ele este că valorile PageRank din prima formulă se însumează la una, în timp ce în a doua formulă fiecare PageRank se înmulțește cu N și suma devine N., O declarație în lucrarea Page și Brin că „suma tuturor paginilor este una” și pretențiile altor angajați Google susțin prima variantă a formulei de mai sus.Page și Brin au confundat cele două formule în lucrarea lor cea mai populară „Anatomia unui motor de căutare web hipertextual pe scară largă”, unde au susținut în mod eronat că această din urmă formulă a format o distribuție de probabilitate pe paginile web.Google recalculează scorurile PageRank de fiecare dată când accesează cu crawlere Web-ul și își reconstruiește indexul., Pe măsură ce Google crește numărul de documente din colecția sa, aproximarea inițială a PageRank scade pentru toate documentele.

formula folosește un model al unui surfer aleatoriu care ajunge la site-ul țintă după câteva clicuri, apoi trece la o Pagină aleatorie. Valoarea PageRank a unei pagini reflectă șansa ca surfer aleatoare va ateriza pe acea pagină, făcând clic pe un link. Poate fi înțeles ca un lanț Markov în care stările sunt pagini, iar tranzițiile sunt legăturile dintre pagini – toate acestea sunt la fel de probabile.,

dacă o pagină nu are legături către alte pagini, ea devine o chiuvetă și, prin urmare, încheie procesul de navigare aleatorie. Dacă navigatorul aleatoriu ajunge la o pagină de chiuvetă, acesta alege o altă adresă URL la întâmplare și continuă să navigheze din nou.

atunci când se calculează PageRank, paginile fără legături de ieșire se presupune că se leagă de toate celelalte pagini din colecție. Scorurile lor PageRank sunt, prin urmare, împărțite în mod egal între toate celelalte pagini. Cu alte cuvinte, pentru a fi corect cu paginile care nu sunt chiuvete, aceste tranziții aleatorii sunt adăugate la toate nodurile din Web. Această probabilitate reziduală, d, este de obicei setată la 0.,85, estimat din frecvența pe care un surfer Mediu utilizează caracteristica de marcaj a browserului său. Deci, ecuația este după cum urmează:

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-c}{N}}+d\sum _{p_{j}\în M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}

PageRank valorile sunt intrările de poziție dominantă dreapta vector propriu a modificat matricea de adiacență modificată, astfel încât fiecare coloană se adaugă până la unul.,_{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. elementele fiecărei coloane însumează până la 1, deci matricea este o matrice stocastică (pentru mai multe detalii, consultați secțiunea de calcul de mai jos). Astfel, aceasta este o variantă a măsurării centralității eigenvector utilizate în mod obișnuit în analiza rețelei.

Din cauza eigengap mare a matricei adjacency modificate de mai sus, valorile vectorului propriu PageRank pot fi aproximate într-un grad ridicat de precizie în doar câteva iterații.,fondatorii Google, în lucrarea lor originală, au raportat că algoritmul PageRank pentru o rețea formată din 322 de milioane de legături (în margini și în margini) converge într-o limită tolerabilă în 52 de iterații. Convergența într-o rețea de jumătate din dimensiunea de mai sus a durat aproximativ 45 de iterații. Prin intermediul acestei date, au ajuns la concluzia algoritmul poate fi scalate foarte bine și că factorul de scalare pentru extrem de mari rețele ar fi de aproximativ liniar în jurnal ⁡ n {\displaystyle \log n} , unde n este dimensiunea rețelei.,ca urmare a teoriei lui Markov, se poate demonstra că PageRank-ul unei pagini este probabilitatea de a ajunge la acea pagină după un număr mare de clicuri. Acest lucru se întâmplă cu T-1 {\displaystyle T^{-1}} unde t {\displaystyle t} este așteptarea numărului de clicuri (sau salturi aleatorii) necesare pentru a ajunge de la pagină înapoi la ea însăși.un dezavantaj principal al PageRank este că favorizează paginile mai vechi. O pagină nouă, chiar și una foarte bună, nu va avea multe link-uri decât dacă face parte dintr-un site existent (un site fiind un set de pagini dens conectate, cum ar fi Wikipedia).,

Mai multe strategii au fost propuse pentru a accelera calculul PageRank.diverse strategii de manipulare a PageRank au fost folosite în eforturi concertate pentru a îmbunătăți clasamentul rezultatelor căutării și pentru a genera bani din linkurile publicitare. Aceste strategii au afectat grav fiabilitatea conceptului PageRank, care pretinde să determine ce documente sunt de fapt foarte apreciate de comunitatea Web.,din decembrie 2007, când a început să penalizeze în mod activ site-urile care vând link-uri text plătite, Google a combătut fermele de link-uri și alte scheme concepute pentru a umfla artificial PageRank. Modul în care Google identifică fermele de legături și alte instrumente de manipulare PageRank se numără printre secretele comerciale ale Google.

ComputationEdit

PageRank poate fi calculat fie iterativ, fie algebric. Metoda iterativă poate fi văzută ca metoda iterației de putere sau metoda puterii. Operațiile matematice de bază efectuate sunt identice.,

IterativeEdit

La t = 0 {\displaystyle t=0} , o primă distribuție de probabilitate presupune, de obicei,

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

unde N este numărul total de pagini și p i; 0 {\displaystyle p_{i}; 0} este pagina i la ora 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}O)^{T}} ,

în cazul în care Un {\displaystyle A} reprezintă matricea de adiacență a grafului și K {\displaystyle K} este o matrice diagonală cu outdegrees în diagonală.

calculul probabilității se face pentru fiecare pagină la un moment dat, apoi se repetă pentru următorul punct de timp. Calculul se termină atunci când pentru unele mici ϵ {\displaystyle \epsilon }

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

de exemplu, atunci când convergența se presupune.,

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} } .,

soluția există și este unic pentru 0 < d < 1 {\displaystyle 0<d<1} . Acest lucru poate fi văzut de remarcat faptul că M {\displaystyle {\mathcal {M}}} este prin construcție o matrice stochastic și, prin urmare, are un eigenvalue egal cu unul ca o consecință a Perron–Frobenius teorema.,

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 } .,

Rețineți că în ecuația (3) matricea de pe partea dreaptă în paranteză poate fi interpretat ca

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

în cazul în care P {\displaystyle \mathbf {P} } este o primă distribuție de probabilitate. În cazul de față

P := 1 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 exemplu tipic este folosind Scala de programare funcțională cu Apache Spark RDDs pentru a calcula iterativ Pagina Rândurile.

MATLAB/OctaveEdit

Exemplu de cod de asteptare rangul funcția definită mai sus:

M = ;rank2(M, 0.80, 0.001)

PythonEdit

Acest exemplu utilizează ≈13 iterații să conveargă.