Działanie algorytmu PageRank
PageRank – metoda nadawania indeksowanym stronom internetowym określonej wartości liczbowej, oznaczającej jej jakość.
Algorytm PageRank jest wykorzystywany przez popularną wyszukiwarkę internetową Google. Został opracowany przez założycieli firmy Google Larry'ego Page'a oraz 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[1]. Wynik PageRank pokazywany jest jako jedna z opcji dostępnych w pasku narzędziowym Google, sprawdzać da się go także w wielu serwisach niezależnych.
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ż kiedy na ten sam tekst powołuje się mało popularna strona.
Metody zbliżone do algorytmu PageRank są aktualnie coraz śmielej wprowadzane do mechanizmów innych wyszukiwarek internetowych. Szczegóły właściwego algorytmu wcale nie zostały upublicznione oraz 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 powodują zaledwie 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.
Algorytm
Poniższy algorytm jest tylko wersją wzorcową. Szczegóły algorytmu nie zostały upublicznione.
Gdzie:
- PR - PageRank danej strony
- d - współczynnik tłumienia, liczba pomiędzy 0 oraz 1. Dla obliczeń przyjmuje się zwykle wartość 0.85
- N - liczba stron internetowych
- L - liczba linków do których odsyła dana strona internetowa
Algorytm ten da się 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 oraz równoległych uruchamianych równocześnie na wielu (tysiącach) komputerów.
Przykład
Zakładamy, że w internecie są tylko 4 strony internetowe oraz posiadają one wyjściowo PageRank równy 1.0:
Ponadto:
- strona A.pl linkuje do stron B.com oraz D.org
- strona B.com linkuje do A.pl
- strona C.net linkuje do B.com oraz A.pl
- strona D.org linkuje do C.net
PageRank obliczony wedle 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 oraz 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 oraz podobne algorytmy była opatentowana w Stanach Zjednoczonych. W ich tekście da się znaleźć wiele szczegółów dotyczących funkcjonowania tych algorytmów[2].
Sprawdź też
Przypisy
