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 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[1]. Wynik PageRank pokazywany jest jako jedna z opcji dostępnych w pasku narzędziowym Google, sprawdzać można go również w wielu serwisach niezależnych.
Spis treści |
[edytuj] 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.
[edytuj] 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 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.
[edytuj] 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
[edytuj] 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[2].
[edytuj] Zobacz też
Przypisy
|
||||||||||||||||||||||||
