ZAWWW-2st1.2-w13.tresc-1.0-Slajd20
Losowy spacer (2)
Niech v oznacza wektor prawdopodobieństw przebywania w dowolnym dokumencie indeksowanej sieci. Stan początkowy wektora v nie ma żadnego znaczenia. Najczęściej inicjalizuje się pozycje wektora v pewną niską wartością, obrazującą jednostajne prawdopodobieństwo rozpoczęcia losowego spaceru w dowolnym dokumencie sieci. Dysponując wektorem v i macierzą stochastyczną M można wyliczyć rozkład prawdopodobieństwa przebywania w każdym dokumencie po wykonaniu jednego kroku, rozkład ten jest dany przez wektor v '= Mv . Zakładając nieskończony ciąg kroków, rozkład prawdopodobieństwa przebywania w dowolnym dokumencie w dowolnej chwili spaceru losowego jest dany przez granicę M(M(M(…M( Mv )…) ) ). A zatem, wektor wynikowy (po nieskończonej liczbie kroków) to wektor własny (ang. principal eigenvector) macierzy M. Wartości tego wektora (czyli prawdopodobieństwa przebywania w dowolnym dokumencie w dowolnej chwili spaceru losowego) nazywamy wartościami PageRank dokumentów. W algorytmie PageRank wartość i-tej pozycji wektora własnego macierzy M stanowi ważność i-tego dokumentu.