PageRank, czyli jak Google stał się bogaty

28.09.2009 - Krzysztof Dryś
TrudnośćTrudność

Internetowy surfer

Żeby poradzić sobie z tym problemem spróbujemy zupełnie nowego podejścia. Pomoże nam w tym internetowy surfer. Wyobraźcie sobie człowieka, który zaraz po wstaniu rano włącza komputer i zaczyna przeglądać internet. Rozpoczyna to od wejścia na dowolną, losową, stronę internetową. Jest na niej minutę, a następnie podąża za jednym linków zamieszczonych na tej stronie. Na następnej stronie również przebywa chwilę i również opuszcza ją jednym z zamieszonych linków. Od czasu do czasu zamiast podążyć linkiem przechodzi na losową stronę w internecie. W ten sposób postępuje bez końca. Można to zapisać w ten sposób:

1
2
3
4
5
6
7
8
 Wejdź na losową stronę
 Powtarzaj bez końca:
  Oglądaj aktualną stronę przez minutę
  Niech z będzie losową liczbą z przedziału [0,1)
  Jeżeli z jest mniejszy od α:
   Przejdź na losową stronę w internecie
  Jeżeli x jest większy, bądź równy α:
   Przejdź na losową stronę, do której linkuje aktualna strona
Nasz surfer ma być uśrednieniem wszystkich użytkowników internetu. Swoją drogą, trzeba przyznać, że zdecydowanie jest on maniakiem internetowym. Bardzo się nam przyda ta jego cecha.

Topologia sieci to brzmiące mądrze określenie na strukturę linków między stronami.

Pamiętacie jak obliczaliśmy wartość PageRank strony? Najpierw tworzyliśmy układ równań wynikający z topologii sieci. Potem dodawaliśmy równanie $ \sum P(X) = N $, gdzie sumowanie przebiega po wszystkich stronach, a $ N $ to łączna popularność wszystkich stron w sieci. Na końcu rozwiązywaliśmy układ równań i dostawaliśmy wszystkie współczynniki.

Przyjmijmy teraz, że łączna popularność wszystkich stron w internecie wynosi 1. Oznacza to, że $ P $ spełnia następujące równanie: $ \sum P(X) = 1 $

Po co to wszystko? Załóżmy, że surfer przegląda internet już od $ T $ minut. Załóżmy też, że surfer odwiedził stronę $ A $ już $ N_T(A) $ razy. Oczywiście, wartość $ N_T(A) $ zależy od decyzji losowych podejmowanych przez surfera, czyli od tego, które strony będzie wybierał w kolejnych krokach.

Okazuje się jednak, że gdy $ T $ jest coraz większe (czyli upływa coraz więcej czasu) to z bardzo dużym prawdopodobieństwem, $ N_T(A) \over T $ jest coraz bliższe $ P(A) $.

Spójrzmy na to inaczej

Co tak właściwie oznacza ostatnie zdanie? Wyobraźmy sobie następujące doświadczenie losowe: bierzemy kostkę 10-ścienną i rzucamy nią $ T $ razy. Ile razy wypadnie jedynka? Oczekujemy, że około $ {T \over 10} $. Natomiast, jeżeli $ N_T $ oznacza ilość jedynek po $ T $ rzutach, to oczekujemy, że $ N_T \over T $ będzie blisko $ 0.1 $.

Popatrzmy na rysunek poniżej. Widać na nim wynik 10 doświadczeń losowych polegających na rzuceniu kostką sto tysięcy razy. Na osi pionowej zaznaczone ile razy, względem liczby dotychczasowych rzutów, wypadła jedynka. Jak wygląda ten wykres? Widzimy, że na początku wszystkie zależności oscylują daleko od $ 0.1 $. Dopiero po zwiększeniu liczby prób wszystkie wykresy zbliżają się do tej wartości. Gdybyśmy zrobili jeszcze więcej prób, to zobaczylibyśmy jak wszystkie wykresy (bardzo powoli) zbliżają się do $ 0.1 $.

alternative text Ile razy wypadnie jedynka, jeżeli będziemy rzucali kostką 10-ścienną? Powinna wypadać w około $ 10\% $ rzutów. Widzimy, że im więcej razy rzucimy kostką, tym bardziej zbliżamy się do tej wartości.

Na następnym rysunku widać wynik 10 prób losowych, polegających na spacerze naszego surfera po grafie z ostatniego przykładu. Na osi pionowej zaznaczone jest $ N_T(A_1) \over T $. Czyli ile razy, względem ilości czasu, który do tej pory upłynął, surfer był na stronie $ A_1 $.

alternative text Ile razy surfer internetowy odwiedzi stronę $ A $ podczas chodzenia losowego po internecie? Matematyka mówić, że po $ T $ turach powinien być tam około $ P(A) \cdot T $ razy. Podobnie jak w przypadku rzutów kostka widzimy, że im większe $ T $, tym bliżej tej wartości jesteśmy.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com