PageRank

PageRank

Działanie algorytmu 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. 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.

Metody zbliżone do algorytmu PageRank są obecnie coraz śmielej wprowadzane do mechanizmów innych wyszukiwarek internetowych. Szczegóły właściwego algorytmu nigdy nie zostały upublicznione i są jednymi ze ściśle strzeżonych tajemnic Google. 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^[7].

Algorytm

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

${\displaystyle P\!R_{x}={\frac {1-d}{N}}+d\left({\frac {P\!R_{y}}{L_{y}}}+{\frac {P\!R_{z}}{L_{z}}}...\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].

Zobacz też

• miara w matematyce

Przypisy