PageRank

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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 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. 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.

Nazwa "PageRank" jest znakiem handlowym Google, a sam algorytm został 9 stycznia 1998 opatentowany w Stanach Zjednoczonych (nr patentu US6285999)[1]. Patent należy jednak do Uniwersytetu Stanforda, a nie firmy 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[2]. Akcje zostały sprzedane w 2005 za 336 milionów dolarów[3].

Działanie[edytuj | edytuj kod]

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.

Algorytm[edytuj | edytuj kod]

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} ... \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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[4].

Zobacz też[edytuj | edytuj kod]

Wikimedia Commons

Przypisy

  1. Patents. Method for node ranking in a linked database (ang.). www.google.com, 2001-09-04. [dostęp 2013-01-08].
  2. Richard Brandt: Starting Up. How Google got its groove (ang.). Stanford magazine. [dostęp 2013-01-08].
  3. Lisa M. Krieger: Stanford Earns $336 Million Off Google Stock (ang.). www.redorbit.com, 2005-12-01. [dostęp 2013-01-08].
  4. Lista patentów w USA zawierających termin PageRank