Blog

Google PageRank Algoritms

Autors:

Oriģinālo Google PageRank algoritmu aprakstīja Lawrence Peidžs un Sergejs Brins vairākās publikācijās.

PR (A) = (1-d) + d (PR (T1) / C (T1) + … + PR (Tn) / C (Tn))

Kur:

PR(A) ir lapas A PageRank

PR(Ti) ir PageRank lapai Ti kur ir saite uz lapu A

C(Ti) ir izejošo saišu skaits lapai Ti

d ir bremzēšanas faktors, kas var būt starp 0-1

Tātad, pirmkārt, mēs redzam, ka PageRank Algoritms nevērtē tīmekļa vietnes kopumā, bet ir noteikta katrai lapai atsevišķi. Turklāt lapas A PageRank nosaka lapu PageRanks, kur ir saites uz lapu A.

PageRank lapām Ti, kur ir saites uz lapu A, neietekmē lapas A PageRank vienādi. Ar PageRank algoritmu lapu T vienmēr novērtē ar izejošo skaiti saišu C(T) lapai T. Tas nozīmē ja vairāk izejošo saišu lapai T, jo mazāk labuma saņem lapa A ja saite nāk no lapas T.

Lapaspuses Ti PageRank vērtējums pēc tā tiek pacelts uz augšu. Izejot no šī papildus iesakošās saites vienmēr dos papildus plusus lapas A PageRank.

Visbeidzot PageRank vērtējuma summa visām Ti lapām tiek pareizināta ar faktoru d, kurš var būt robežās no 0-1. Tādējādi, paplašinot PageRank ieguvumu lapai, saistot to ar to, ka citas lapās ir saite uz šo lapu tas tiek samazināts.

Nejauša lietotāja modelis

Savās publikācijās Lawrence Peidžs un Sergejs Brins dod ļoti vienkāršu intuitīvu pamatojumu PageRank algoritmam. Tās uzskata, PageRank, kā paraugu lietotāja uzvedībai, kur lietotājs klikšķina uz saiti neņemot vērā saturu.

Nejauš lietotājs apskata tīmekļa lapu ar noteiktu varbūtību, kas izriet no lapas PageRank. Varbūtību, ka nejauš lietotājs noklikšķina uz vienu saiti ir saistīts tikai ar saišu skaitu šajā lapā. Šis ir iemesls kāpēc vienas lapas PageRank nav pilnībā nodots lapai, kas ir mājas lapā, bet ir sadalīts visām izejošajām saitēm lapā.

Tātad, iespējamība, kas attiecās uz nejauša lietotāja varbūtību uzspiest noteiktu saiti mājas lapā ir varbūtības summas saišu skaits ko nejauš lietotājs var uzspiest. Tagad šī varbūtība ir samazināta ar koeficientu d. Tādēļ nejauša lietotāja modeļa pamatojums balstās uz to ka lietotājs neklikšķinās uz neierobežoti skaitu saišu mājas lapā, jo viņam kļūs garlaicīgu un viņš pāries uz citu mājas lapu.

Par nejauš lietotāja varbūtību ka viņš neapstāsies klikšķināt uz saitēm aprēķina pēc koeficienta d, kurš atkarība no ticamības pakāpes ir starp 0 un 1. Jo augstāks d, jo lielāka ticamība ka lietotājs klikšķinās uz saitēm lapā. Ja lietotājs pāriet uz citu lapu pārtraucot klikšķināt uz saitēm, tāpēc varbūtība tiek īstenota kā nemainīga (1-d) uz algoritmu. Neatkarīgi no ienākošām saitēm, vienmēr varbūtība, ka nejauš lietotājs pāries uz citu mājas lapu ir (1-d), tāpēc lapai vienmēr ir mazāks PageRank.

Dažādas piezīmes par PageRank algoritmu

Lawrence Peidžs un Sergejs Brins ir publicējuši divās dažādās versijās par PageRank algoritmu dažādos dokumentos. Otrajā versijā algoritms, lapas PageRank ievada kā

PR (A) = (1-d) / N + d (PR (T1) / C (T1) + … + PR (Tn) / C (Tn))

kur N ir kopējais skaits iekšējo lapu mājas lapā. Otrais algoritma variants, protams, nav protams būtiski atšķirīgs no pirmā varianta. Attiecībā uz nejauš lietotāja modeli, otrais variants lapas Pagerank is faktiska varbūtība, ka lietotājs nonāks mājas lapā noklikšķinot vairākas saites. PageRank varbūtības sadalījums tādā gadījumā mājas lapā visu lapu PageRank summa būs viens.

Pretēji pirmajai algoritma versijai lietotāja nonākšana konkrētā saites varbūtība ir novērtēta ar kopējo skaitu mājas lapās. Tātad šinī versijā PageRank ir gaidāma vērtība nejauša lietotāja apmeklējumu lapā, ja lietotājs atkārto meklējumus tik reize cik mājas lapā ir lapas. Ja mājas lapa ir 100 lapas un lapas PageRank ir 2, tad nejaušais lietotājs sasniegs šo lapu vidēji divas reizes, ja viņš atkārtos 100 reizes meklējumus.

Kā minēts iepriekš abas versijas algoritmu būtiski neatšķiras viens no otra. PageRank kas aprēķināts, izmantojot otro versiju algoritmu ir jāreizina ar kopējo skaitu mājas lapu, lai iegūtu PageRank, kas bija aprēķināts pirmajā versijā. Pat Peidžs un Brins ir sajaukuši abas algoritma versijas to populārajā avīzē “The Anatomy of a Large-Scale Hypertextual Web Search Engine”, kur viņi apgalvo pirmā versija algoritmam, lai izveidotu varbūtību sadalījums mājas lapai visas lapas PageRank ir viens.

Turpmāk mēs izmantosim pirmo PageRank algoritma versiju. Tas tādēļ, ka PageRank aprēķinam izmantojot šo algoritmu ir vieglāk aprēķināt, jo mēs varam neņemt vērā kopējo skaitu mājas lapas iekšējās lapas.

PageRank īpašības

PageRank īpašības raksturo mazs piemērs.

Mēs uzskatāmam piemēram paņemam nelielu mājas lapu, kas sastāv no trim iekšējām lapām A, B un C, kur lapa A saites iet uz mājas lapu B un C, lapa B saite iet uz C un lapas C saits iet uz lapu A. Saskaņā ar Paidžs un Brins koeficients d parasti tiek noteikt līdz 0,85, bet lai saglabātu aprēķinu vienkāršāku mēs to nolaidīsim līdz 0,5. Precīzu vērtību izmantošanu koeficientā d protams ietekme PageRank, bet tas neietekmē PageRank pamatprincipus. Tātad mēs iegūstam šādu aprēķinu:

PR (A) = 0,5 + 0,5 PR (C)
PR (B) = 0,5 + 0,5 (PR (A) / 2)
PR (C) = 0,5 + 0,5 (PR (A) / 2 + PR (B))

Šie vienādojumi ir viegli atrisināmi. Mēs saņemam šādas PageRank vērtības lapām:

PR (A) = 14/13 = 1,07692308
PR (B) = 10/13 = 0,76923077
PR (C) = 15/13 = 1,15384615

Ir skaidrs, ka visas lapas PageRanks summa ir 3, un tādējādi ir vienāds ar kopējo skaitu mājas lapu iekšējām lapām. Kā norādīts iepriekš, tas nav precīzs rezultāts, tas ir vienkāršs piemērs, lai Jūs saprastu algoritma paņēmienus.

Mūsu vienkāršajā trīs lappuses piemērā, tas ir viegli atrisināms saskaņā ar vienādojumu sistēmu, lai noteiktu PageRank vērtības. Prakse, internets sastāv no miljons lapām, dokumentu un nav iespējams rast risinājumu veicot pārbaudi kā piemērā.

PageRank iteratīvais aprēķins

Izmēra dēļ faktiskā web, Google meklētājprogramma izmanto aptuvenas, iteratīvs aprēķinam PageRank vērtības. Tas nozīmē kā katrai lapai ir piešķirts sākuma vērtība un PageRank visam lapām tiek aprēķināts pēc vairākiem vienādojumiem ko nosaka PageRank algoritms. Iteratīva aprēķināšana atkal būs ilustrēta mūs trīs lapu mājas lapas piemēra, saskaņā ar kuru katrai lappusei piešķirtā sākuma PageRank vērtība ir 1.

Iteratīvs PR(A)              PR (B)                PR (C)

0           1                        1                          1
1           1                        0.75                    1.125
2           1,0625              0,765625          1,1484375
3           1.07421875     0.76855469     1.15283203
4           1.07641602     0.76910400     1.15365601
5           1.07682800     0.76920700     1.15381050
6           1.07690525     0.76922631     1.15383947
7           1.07691973     0.76922993     1.15384490
8           1.07692245     0.76923061     1.15384592
9           1.07692296     0.76923074     1.15384611
10         1.07692305     0.76923076     1.15384615
11         1.07692307     0.76923077     1.15384615
12         1.07692308     0.76923077     1.15384615

Mēs redzam ka iegūstam aptuveno PageRank vērtību pēc vairākiem iteratīviem. Saskaņā ar publikācijas Lawrence Peidžs un Sergejs Brins aptuveni 100 iterācijas ir nepieciešami, lai iegūtu aptuvenu PageRank vērtības no visas mājas lapas.

Tāpat, izmantojot iteratīvs aprēķinu, ka visas lapas PageRanks summa joprojām tiecas uz kopējo skaitu mājas lapu lapu. Tātad vidējais PageRank mājas lapā ir 1. Tādēļ tur maksimālais PageRank lapai, kas ir norādīts ar DN + (1-d), kur N ir kopējais skaits tīmekļa lapu. Šo maksimālo teorētiski var noteikt, ja visās lapās saite irt tikai uz vienu lapu un šīm lapām ir tikai saite uz sevi.

0


Mārtiņš Lasmanis

Interneta mārketinga speciālists specializējies SEO pakalpojumos ar daudzu gadu pieredzi

Add a Comment