Menu Content/Inhalt
Start
Algorytm PageRank PDF Drukuj
Oceny: / 7
KiepskiBardzo dobry 
13.08.2007.

PageRank jest miarą jakości strony wykorzystywaną przez Google, pomagającą dokładniej przedstawiać wyniki wyszukiwań. PageRank bazuje na demokratycznej naturze internetu i poprzez strukturę powiązań (linków) między stronami przypisuje każdej ze stron jej wartość. Google interpretuje link ze strony A do strony B jako ‘głos’ strony A na stronę B. Ponadto, Google patrzy także na wartość strony która daje głos oraz na jej zawartość – głosy oddawane przez „ważne” strony mają większą wartość i pomagają innym stronom stać się „ważnymi”.

Podstawy matematyczne


Załóżmy, że strona A ma po jednym linku ze stron X­1...Xn. Ponadto S(Xy) oznacza całkowitą ilość linków ze strony Xy do innych stron oraz PR(Xy) oznacza PageRank strony Xy. Niech d oznacza dampening factor1, zwykle ustalany na 0,85, który powoduje, iż algorytm będzie miał skończoną liczbę iteracji.


Równanie2:


PR(A) = (1-d) + d( PR(X1)/S(X1) + ... + PR(Xn)/S(Xn))


pozwoli nam na obliczenie rankingu strony A w/g uproszczonego algorytmu PageRank. Zakładając, iż mamy n=5 stron, PageRank każdej z nich wynosi PR(Xy)=5 oraz z każda ma S(Xy)=10 linków zewnętrznych, możemy policzyć ranking strony A:


PR(A)= (1-0.85) + 0.85( 5/10 + 5/10 + 5/10 + 5/10 + 5/10)=0.15 + 2.125 = 2.275


Obliczenia wyglądają w miarę prosto, aczkolwiek, jeśli założymy, że strona A posiada linki do innych stron (w tym do stron, które linkują stronę A), to jedno obliczenie tego równania nie wystarczy, gdyż ranking stron powiązanych ze sobą będzie się zmieniał z kolejnymi iteracjami tego równania. Dla przykładu, załóżmy, że strony A, B, C i D są wzajemnie powiązane w poniższy sposób:


Tabela 5. Przykładowe powiązanie 4 stron.


do A

do B

do C

do D

z A


1

1

1

z B

1




z C

1

1



z D

1

1

1


Źródło: Opracowanie własne.


Ponadto załóżmy, iż początkowe wartości PR dla A, B, C i D wynoszą 1, oraz d=0.85

Kolejne iteracje algorytmu będą wyglądały następująco:


Tabela 6. Zmiana PR podstron w kolejnych iteracjach algorytmu.

 

Początkowy PR

1

2

3

4

5

6

7

A

1

1.708

1.547

1.553

1.569

1.559

1.563

1.562

B

1

1.141

1.061

1.089

1.083

1.083

1.084

1.083

C

1

0.716

0.756

0.768

0.756

0.761

0.760

0.760

D

1

0.433

0.634

0.558

0.590

0.594

0.591

0.592

Źródło: Opracowanie własne.


Jak można się domyśleć, strona A będzie mieć najwyższy ranking (3 strony „głosują” na nią), zaś najniższy strona D – posiada tylko jeden link z zewnątrz. Jak widać z przedstawionych obliczeń, wartość rankingu strony stabilizuje się z kolejnymi wykonaniami algorytmu. Dzięki dampening factor, algorytm jest skończony, pozostaje jedynie kwestia posiadania odpowiednio wydajnych maszyn do prowadzenia obliczeń.


Można także zauważyć, że jeśli dana strona zawiera załóżmy 4 linki, z czego 2 do zewnętrznych serwisów, to według naszych wyliczeń, tylko połowa głosu, jaki posiada ta strona zostanie przyznana naszemu serwisowi, zaś połowa „ucieknie” w świat. Nie jest to jednak do końca prawdą – algorytm nie jest aż taki prosty. Google w jakiś sposób muszą premiować strony odwołujące się do pokrewnych tematycznie serwisów czy też do stron, które zdobyły już „uznanie” w internecie (wysoki PageRank).

Przedstawiony tutaj algorytm ma za zadanie pokazanie, jaki jest sposób działania oryginalnego algorytmu PageRank, który nie jest jawny – gdyby był jawny pozycjonowanie stron w Google stałoby się zwykłym dopasowaniem strony do znanego algorytmu. Algorytm PageRank uwzględnia także szereg innych czynników o których szerzej w dalszej części rozdziału.

 

1 Brak polskiej nazwy; wskaźnik, dzięki któremu algorytm jest skończony.

2 Chris Ridings and Mike Shishigin, PageRank Uncovered, VERSION 3.0 Last amended – September 2002

 
« poprzedni artykuł