Przeskocz do treści

Delta mi!

Co to jest?

Jak to działa?

Miara ważności

Krzysztof Diks

o artykule ...

  • Publikacja w Delcie: sierpień 2008
  • Publikacja elektroniczna: 02-02-2011
  • Autor: Krzysztof Diks
    Afiliacja: Instytut Informatyki, Uniwersytet Warszawski

Czy zastanawiałeś się, drogi Czytelniku, dlaczego wyszukiwarka wyświetla adresy stron będących odpowiedzią na Twoje zapytanie właśnie w takiej, a nie innej kolejności?

obrazek

Zanim zacząłem pisać tę krótką notkę, zażądałem od wyszukiwarki google.pl odpowiedzi na pytanie „matematyka”. Pierwszych pięć adresów do stron, które otrzymałem w odpowiedzi, to
(1) www.matematyka.org,
(2) www.matematyka.pl,
(3) www.math.edu.pl,
(4) pl.wikipedia.org/wiki/Matematyka,
(5) www.freewebs.com/podmatematyka.

Google „pochwalił się”, że wybrał je spośród 2 810 000 kandydatów. Dlaczego właśnie te uznano za najważniejsze? Jaka jest miara ważności strony? Okazuje się, że podstawą analizy ważności stron w Google jest analiza połączeń w grafie Internetu. Graf Internetu jest grafem skierowanym, w którym węzłami są strony, a krawędzie odpowiadają dowiązaniom pomiędzy stronami – strona zawierająca adres internetowy innej strony jest początkiem krawędzi, a strona o danym adresie jej końcem. Czy można na podstawie grafu Internetu powiedzieć, które strony są ważniejsze, a które mniej? Strona ważna to strona interesująca. Strona interesująca to taka, do której łatwo dotrzeć, ponieważ wiele innych stron na nią wskazuje. Na dodatek wiele spośród stron wskazujących na ważną stronę też jest ważnych i interesujących, itd. Larry Page i Sergey Brin, twórcy Google, wyrazili to matematycznie w następujący sposób.

Załóżmy, że mamy math stron math Niech math będzie liczbą rzeczywistą dodatnią mierzącą ważność strony math Wówczas żądamy, żeby

display-math

gdzie math jest zbiorem stron zawierających adres strony math (czyli zbiórem początków krawędzi prowadzących do math), zaś math jest liczbą odnośników (krawędzi) wychodzących ze strony math

Powyższy wzór oznacza, że ważność strony mierzy się ważnością stron na nią wskazujących. Jeżeli przyjmiemy na początek, że wszystkie strony są jednakowo ważne i dla każdej z nich math gdzie math to liczba wszystkich stron, to ważność stron można obliczyć za pomocą następującej metody iteracyjnej:

display-math

Na powyższy proces można spojrzeć jak na błądzenie losowe po grafie Internetu. Rozpoczynamy z dowolnej strony, a następnie z każdej oglądanej strony ruszamy losowo do jednej ze stron, do których adresy umieszczono na tej stronie. Jeśli nasz proces będziemy powtarzali bardzo długo, to pewne ze stron będziemy oglądali częściej niż inne. Strony oglądane częściej są ważniejsze.

Niestety, może się zdarzyć, że serfując po stronach, natrafimy na takie, z których nie ma wyjścia, np. strony zawierające zdjęcia. W takim przypadku zakładamy, że w następnym kroku wybierzemy losowo dowolną ze stron w Internecie. Teraz nasz proces iteracyjny wygląda następująco:

display-math

gdzie math oznacza zbiór wszystkich stron końcowych, czyli takich, które nie zawierają dowiązań do żadnych innych stron. Jesteśmy już blisko algorytmu Google ustalania miary ważności stron.

Brin i Page obserwując zachowanie użytkowników Internetu, zauważyli, że czasami porzucają oni bieżące przeszukiwanie i rozpoczynają nowe od (losowo) wybranej strony. Dlatego zmodyfikowali swój proces iteracyjny, wprowadzając parametr math o wartości z przedziału math

W każdej iteracji z prawdopodobieństwem math aktualne przeszukiwanie jest kontynuowane, natomiast z prawdopodobieństwem math rozpoczynane jest nowe przeszukiwanie. Ostatecznie postać każdej iteracji jest następująca:

display-math

Bardziej doświadczeni Czytelnicy pewnie już spostrzegli, że nasz proces iteracyjny jest procesem stochastycznym zbieżnym do stacjonarnego rozkładu prawdopodobieństwa. Celem kolejnych modyfikacji procesu było zapewnienie właśnie takiej zbieżności. Końcowy rozkład prawdopodobieństwa odpowiada mierze ważności stron.

Oczywiście, jest jeszcze wiele pytań, które pozostają bez odpowiedzi: Jak szybko powyższy proces zbiega do końcowego rozkładu? Jak dobierać parametr math? W jaki sposób przeprowadzać obliczenia na grafie Internetu, który w chwili obecnej liczy blisko 100 000 000 domen?

Odpowiedzi na te pytania to już inna historia. Wszystkich zainteresowanych odsyłam do wspaniałej książki autorstwa Amy N. Langville i Carla D. Meyera, Google’s PageRank and Beyond: The Science of Search Engine Rankings.