PageRank

PageRank – metoda nadawania indeksowanym stronom internetowym określonej wartości liczbowej, oznaczającej ich jakość.

Algorytm PageRank jest wykorzystywany przez popularną wyszukiwarkę internetową Google. Został opracowany przez założycieli przedsiębiorstwa Google Larry’ego Page’a i Sergeya Brina podczas ich studiów na Uniwersytecie Stanforda w 1998 roku. Nazwa algorytmu pochodzi nie od angielskiego wyrazu określającego stronę (ang. page), lecz od nazwiska twórcy, czyli Larry’ego Page’a. Wynik PageRank był pokazywany jako jedna z opcji dostępnych w pasku narzędziowym Google, sprawdzać można było go również w wielu serwisach niezależnych. PageRank wycofano powoli, w 2009 roku informację o algorytmie usunięto z Google Webmaster Tools (obecne Google Search Console). Wartość PageRank ostatnio aktualizowano w lutym 2013 roku. W 2016 roku Google całkowicie usunęło narzędzie Google PageRank z wyszukiwarki^[1].

Nazwa „PageRank” jest znakiem handlowym Google, a sam algorytm został 9 stycznia 1998 opatentowany w Stanach Zjednoczonych (nr patentu US6285999)^[2]. Patent należy jednak do Uniwersytetu Stanforda, a nie przedsiębiorstwa Google. Uzyskała ona od Uniwersytetu Stanforda prawa licencyjne na wyłączność, a w zamian za zezwolenie na korzystanie z patentu uniwersytet otrzymał 1,8 miliona akcji Google^[3]. Akcje zostały sprzedane w 2005 za 336 milionów dolarów^[4]. Od 2016 dane na temat rankingu stron, które można było zobaczyć m.in. poprzez Google Toolbar przestały być publiczne dostępne^[5]. Okres ważności patentu na główny algorytm PageRank zakończył się w roku 2019^[6].

Działanie

PageRank jest rozwinięciem znanej od dawna heurystyki, wedle której jakość tekstu jest proporcjonalna do liczby tekstów na niego się powołujących^{[potrzebny przypis]}. Ulepszenie zaproponowane przez autorów Google polegało na ważeniu jakości odnośników wskazujących na rozpatrywany tekst ich własną wartością PageRank. Innymi słowy: jeśli na dany tekst powołuje się artykuł, który sam ma wysoką ocenę, ma to większe znaczenie, niż gdy na ten sam tekst powołuje się mało popularna strona^[7].

Metody zbliżone do algorytmu PageRank są obecnie coraz śmielej wprowadzane do mechanizmów innych wyszukiwarek internetowych^{[potrzebny przypis]}. Szczegóły właściwego algorytmu nigdy nie zostały upublicznione i są jednymi ze ściśle strzeżonych tajemnic Google^[7]. Do tego są najprawdopodobniej sukcesywnie poprawiane, aby zwiększać efektywność mechanizmu. Wszystkie informacje dostępne jawnie przedstawiają jedynie wzorcową wersję algorytmu stosowanego w wyszukiwarce Google. Ponadto PageRank jest tylko jednym z wielu elementów decydujących o ostatecznej pozycji danej strony wśród wyników wyszukiwania, a wprowadzane zmiany powodują, iż ma on coraz mniejszy na nią wpływ^{[potrzebny przypis]}.

Algorytm

Poniższy algorytm jest tylko wersją wzorcową. Szczegóły algorytmu nie zostały upublicznione.

P\!R_{x}={\frac {1-d}{N}}+d\left({\frac {P\!R_{y}}{L_{y}}}+{\frac {P\!R_{z}}{L_{z}}}\dots \right),

gdzie:

PR – PageRank danej strony
d – współczynnik tłumienia, liczba pomiędzy 0 i 1. Dla obliczeń przyjmuje się zazwyczaj wartość 0,85
N – liczba stron internetowych
L – liczba linków do których odsyła dana strona internetowa

Algorytm ten można interpretować jako znajdowanie stanu ustalonego w łańcuchu Markowa, albo jako problem diagonalizacji macierzy. Nietrywialną kwestią techniczną pozostaje implementacja tego algorytmu, aby nadawał się do przetwarzania danych opisujących sieć WWW. Wielkość macierzy wymaga specjalistycznych algorytmów rozproszonych i równoległych uruchamianych jednocześnie na wielu (tysiącach) komputerów.

Przykład

Zakładamy, że w Internecie istnieją tylko 4 strony internetowe i mają one wyjściowo PageRank równy 1,0:

A.pl
B.com
C.net
D.org

Ponadto:

strona A.pl linkuje do stron B.com i D.org
strona B.com linkuje do A.pl
strona C.net linkuje do B.com i A.pl
strona D.org linkuje do C.net

PageRank obliczony według algorytmu przedstawia się następująco:

A.pl – 0,35
B.com – 0,27
C.net – 0,19
D.org – 0,19

Jeśli w Internecie pojawi się nowa strona – E.pl i będą do niej linkować wszystkie istniejące strony, PageRank dla tych stron wyniesie:

A.pl – 0,22
B.com – 0,20
C.net – 0,15
D.org – 0,15
E.pl – 0,28

Patenty

Część systemów wykorzystujących PageRank i podobne algorytmy została opatentowana w Stanach Zjednoczonych. W ich tekście można znaleźć wiele szczegółów dotyczących funkcjonowania tych algorytmów^[8].