PageRank, czyli jak Google stał się bogaty

28.09.2009 - Krzysztof Dryś
TrudnośćTrudność

Prosty przykład

Załóżmy, że Białego Pudelka odwiedza dziennie 100 000 osób oraz, że linkuje on do 1000 innych stron. Jeden z tych linków prowadzi do temperowanie-olowkow.pl. Można więc spodziewać się, że $ 100000 \cdot {1 \over 1000} = 100 $ osób dziennie przejdzie z pierwszego portalu na drugi. Strony temperowanie-kredek.pl i temperowanie-dlugopisow.pl odwiedza dziennie odpowiednio tylko $ 60 $ i $ 30 $ osób. Każda z nich linkuje do $ 3 $ stron. Szacujemy więc, że z pierwszej na temperowanie-olowkow.pl będzie dwudziestu gości, a z drugiej dziesięciu.

Na Białym Pudelku jest 1000 linków. Zakładamy, że ludzie przeglądający tę stronę z równym prawdopodobieństwem skorzystają z każdego z nich. Czy to założenie ma sens? Pewnie, że jest dalekie od rzeczywistości. Ale pamiętajcie, że my chcemy stworzyć niezły model, który da nam dobre przybliżenie rzeczywistej popularności stron.

Właśnie oszacowaliśmy, że na stronę temperowanie-dlugopisow.pl zagląda dziennie 130 osób. Ale żeby to zrobić musieliśmy wiedzieć, ile osób dziennie zagląda do stron, które do naszego portalu linkują. Niestety, takiej wiedzy raczej nie będziemy posiadać. Na szczęście okazuje się, że wcale nie jest nam ona konieczna!

alternative text Internet dla początkujących zawiera tylko cztery strony. Może to trochę mniej niż w jego rzeczywistej wersji, ale zdecydowanie uprości nam rachunki.

Załóżmy, dla uproszczenia, że internet składa się z czterech stron. Nazwijmy je: A,B,C i D. Na rysunku obok widać jak te strony wzajemnie do siebie linkują. Spróbujmy oszacować wartość $ P(A) $. Na stronie C są dwa linki, w tym jeden do strony A. Oznacza to, że połowa ludzi ze strony C przechodzi na stronę A. Podobnie jedna trzecia ludzi ze strony D przechodzi na stronę A. Oznacza to, że: $ P(A) = P(B) +  { P(D) \over 3}  $ Tyle, że my nie znamy ani $ P(C) $ ani $ P(D) $ ! Spróbujmy oszacować $ P(B) $, $ P(C) $ i $ P(D) $ w ten sam sposób, jak poprzednio oszacowaliśmy $ P(A) $. To znaczy, patrząc na linki do tych stron. Daje to następujące równania: $ P(B) = { P(A) \over 2} + {P(C) \over 2} + {P(D) \over 3} $ $ P(C) = {P(A) \over 2} + {P(D) \over 3} $ $ P(D) = {P(C) \over 2} $ Na koniec załóżmy, że łącza popularność stron $ A $, $ B $, $ C $ i $ D $ wynosi $ N $. Oznacza to równanie: $ P(A) + P(B) + P(C) + P(D) = N $ Teraz umiemy rozwiązać wszystkie równania. Uzyskujemy wynik: $ P(A) = {5 \over 14 } \cdot N  $ $ P(B) = {9 \over 28}  \cdot N  $ $ P(C) = {3 \over 14}  \cdot N  $ $ P(D) = {3 \over 28}  \cdot N  $

Na początku mówiliśmy o dziennej liczbie wizyt na stronie. Ten termin jest fajny, bo przemawia do wyobraźni. Ale lepiej mówić o popularności strony, bo ten termin jest szerszy i zawiera w sobie nie tylko liczbę wizyt, ale również zaufanie do strony.

Chcemy powiedzieć, która strona jest najbardziej popularna. W ogóle nie potrzebujemy do tego N. Już teraz umiemy powiedzieć, że najpopularniejsza jest strona B. Następna w kolejności jest A, a potem C i D.

W ten sposób udało się nam ustalić względną popularność stron patrząc tylko na linki między nimi. Właśnie poznaliśmy ogólną ideę stojącą za algorytmem PageRank - szacowanie popularności strony na podstawie prowadzących do niej linków. Podsumujmy założenia, które zrobiliśmy:

  • Każda strona ma swoją popularność. Popularność strony $ X $, to $ P(X) $,
  • Jeżeli na stronie $ X $ jest $ n $ linków, to każdej z linkowanych stron przekazuje ona $ {1 \over n} $-tą swojej popularności,

5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com