PageRank, czyli jak Google stał się bogaty

28.09.2009 - Krzysztof Dryś
TrudnośćTrudność

Rozwiązaniem jest...

Czy na portal temperowanie-olowkow.pl ludzie wchodzą tylko ze stron do niego linkujących? Czy opuszczając go zawsze przechodzą na strony, do których on linkuje? Oczywiście, że nie! Czasami ludzi wpisują w pasek wyszukiwania jakiś adres, a czasami korzystają z linków podesłanych przez znajomych.

Czy założenie, że na każdą stronę ludzie teleportują się jednakowo często, jest sensowne? Na pewno trochę kłóci się z naszą intuicją. Należy jednak cały czas mieć w pamięci, że chodzi nam tylko o niezły model.

...teleportacja!

Jeżeli uznamy, że ludzie poruszający się po linkach chodzą po sieci, to odpowiednią nazwą dla skakania do nowego adresu jest teleportacja. Niech $ \alpha $ oznacza liczbę z przedziału $ [0,1) $. Załóżmy, że jeżeli ktoś przegląda jakąś stronę to w $ \alpha $ przypadków kończy się to teleportacją, czyli wybraniem losowego adresu w sieci. Natomiast w $ 1-\alpha $ przypadków zwyczajnie podąża on jednym z linków na tej stronie.

Wróćmy do naszego ostatniego przykładu. Jak zmieni się popularność stron po wprowadzeniu teleportacji? Załóżmy, że $ N $ oznacza ilość wszystkich ludzi przeglądających internet. Wartość $ P(A_1) $ wciąż zależy od $ P(B_1) +  { P(D_1 ) \over 3} $ jednak teraz, z powodu teleportacji, zależy również od $ N $. Dokładniej: $ P(A_1) = (1 - \alpha) \cdot ( P(B_1) +  { P(D_1) \over 3} ) + {\alpha \cdot N \over 8} $ Skąd się wziął ten wzór? Popatrzmy na ludzi na stronach $ B_1 $ i $ D_1 $. Mogą oni opuścić aktualnie oglądane strony albo za pomocą normalnych linków, albo za pomocą teleportacji. Spośród nich $ (1 - \alpha) $ procent wybierze pierwsze rozwiązanie. Natomiast na dowolnej stronie (łącznie z $ A_1 $) $ x $ procent odwiedzających korzysta z teleportacji. Każdy teleportujący się ma szansę $ 1 \over 8 $ trafić na stronę $ A_1 $ - pamiętajmy, że w naszym internecie jest 8 stron!

Uwaga! Do tej pory nasz model zależał tylko od tego, jak strony wzajemnie do siebie linkują. Od teraz będzie zależał jeszcze od parametru $ \alpha $.

W podobny sposób można zapisać równania dla pozostałych stron. Przyjmijmy, dla uproszczenia rachunków, że $ \alpha = 0.1 $. Wtedy rozwiązaniem równań będzie (z dokładnością do trzech miejsc po przecinku): $ P(A_1) = P(A_2) = 0.173 N  $ $ P(B_1) = P(B_2) = 0.157 N  $ $ P(C_1) = P(C_2) = 0.109 N  $ $ P(D_1) = P(D_2) = 0.061 N  $ Znowu uda się nam uszeregować strony względem popularności.

PageRank to algorytm obliczający popularność strony w internecie. A PageRank strony internetowej to właśnie jej popularność, wyliczona w omawianym tutaj modelu. Czyli algorytm PageRank wylicza współczynnik PageRank dla różnych stron internetowych.

Odrobina matematyki

Najpierw zobaczyliśmy przykład grafu dla którego łatwo ułożyć układ równań rozwiązać je i uszeregować strony względem popularności. Potem przekonaliśmy się, że są grafy w których nie jest to takie proste - nawet jeżeli rozwiążemy równania, to nie umiemy jeszcze powiedzieć, które strony są popularne. Na koniec zobaczyliśmy, że ostatnim wypadku pomoże nam teleportacja, która sprawiła, że strony znowu da się uszeregować względem popularności. Czy jednak tak jest zawsze? Okazuje się, że tak! Przy pomocy teorii spacerów losowych da się dowieść, że jeżeli tylko parametr teleportacji jest większy od 0, to po rozwiązaniu równań zawsze będziemy umieli uszeregować strony.

I po kłopocie!

Nareszcie udało się nam rozwiązać nasze równania. W ten sposób umiemy już uporządkować strony w internecie względem ich popularności. Podsumujmy to, co wiemy już o algorytmie PageRank. Działa on w następujący sposób:

1
2
3
 Zbadaj linki między stronami w sieci,
 Stwórz układ równań na podstawie linków,
 Rozwiąż układ równań.
Punkt pierwszy to sprawa czysto techniczna. Przed chwilą zobaczyliśmy, jak rozwiązać punkt drugi. Na podstawie linków zbudowaliśmy układ równań, którego rozwiązaniem jest popularność poszczególnych stron.

Szybkość ma znaczenie

Wydaje się Wam, że wiemy już wszystko co potrzeba o algorytmie PageRank? To niestety nie jest prawda. Wciąż nie wiemy jak poradzić sobie z trzecim krokiem. Oczywiście znane są algorytmy rozwiązujące równania. Ale są one zdecydowanie za wolne! Pamiętajcie, że internet jest bardzo duży -- jest w nim ponad 100 miliardów stron. Możecie sobie wyobrazić, że rozwiązywanie równań, które mają 100 miliardów niewiadomych jest bardzo trudne.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com