PageRank, czyli jak Google stał się bogaty

Internet, prawdopodobieństwo i spacery losowe

Czy spodziewaliście się, że rachunek prawdopodobieństwa może przydać się w internecie? A właśnie okazało się przydaje! Zobaczyliśmy, jak oceniać popularność stron w internecie. Najpierw zbudowaliśmy równania, rozwiązanie którego była właśnie popularność poszczególnych stron. Niestety, nie umiemy szybko rozwiązywać równań, nawet liniowych. Dlatego poszukaliśmy innego rozwiązania. Spróbowaliśmy naśladować surfera internetowego, który jest w pewnym sensie uśrednieniem wszystkich użytkowników internetu. Oczywiście wyniki takiego doświadczenia są w pewnym sensie losowe, ale oczekujemy że będą one bardzo bliskie tym, które uzyskalibyśmy rozwiązując równania.

Algorytm PageRank jest bardzo popularny z dwóch powodów. Przede wszystkim dlatego, że jest skuteczny - jego wyniki mają duży związek z rzeczywistością i tym, co ludzie nazywają popularnością strony. Ale jest też drugi powód. Spacer surfera po grafie można opisać jako spacer losowy. Opisywanie spacery losowych jest bardzo dobrze rozwiniętą dziedziną matematyki. Wszystko to powoduje, że cały algorytm oraz jego przewidywania można bardzo elegancko opisać językiem matematyki. I to w sposób bardzo podobny do tego, jak opisuje zwyczajne rzucanie kostką.

Co dalej?

Oczywiście sukces firmy Google nie kryje się tylko w użyciu tego, bądź co bądź prostego, algorytmu. Na pewno został on zmodyfikowany, a to jak został ulepszony stanowi ściśle strzeżona tajemnicę. Można spodziewać się, że zmieniono między innymi następujące założenia:

• Wszystkie linki są jednakowo ważne. W rzeczywistości zmieniać wagę linków w zależności od tego, gdzie na stronie się znajdują.
• Teleportacja przenosi do każdej strony z takim samym prawdopodobieństwem. To założenie można zmienić mając dane statystyczne dotyczące adresów wpisywanych przez ludzi w wyszukiwarce.
• Nie wiemy nic na temat popularności żadnej strony w internecie. W rzeczywistości możemy na początku algorytmu ręcznie ustalić PageRank części stron.

Jednak istota algorytmu, czyli ocenianie stron na podstawie linków, została zachowana. Warto zapamiętać, że o sukcesie wyszukiwarki firmy Google zadecydował nie tylko sprytny pomysł ale i znajomość teorii spacerów losowych!