PageRank jako łańcuch Marka: Model nudziącego się surfersza

ciągi Markowa i rozkład stationarny

ciąg Markowa to ciąg stanów, w którym prawdopodobieństwo przejścia do następnego stanu zależy tylko od bieżącego, zapisane w macierzy przestosowanej P transizionej, gdzie Pᵢⱼ to prawdopodobieństwo przejścia z stanu i do stanu j. Dla internetu, stanami są strony, a Pᵢⱼ = 1/k, jeśli strona i ma k wychodzących linków i jeden z nich prowadzi do strony j. Rozkład stationarny π* spełnia równanie π*·P = π* — to jest lewej wektorka własna macierzy P dla wartości własnej 1 — a π*ᵢ to długoterminowa ułamka czasu, jaki ciąg spędza w stanie i, pod warunkiem, że ciąg jest niezmiarkowany i nieokresowy. PageRank dokładnie odpowiada π* dla ciągu surfera internetowego: strony o najwyższej prawdopodobieństwie stationarnym mają najwyższy rank.

Surfer losowy i czynnik tłumienia

Wyobraźmy się surfa, który na każdym kroku kliknie losowo wybrany z wychodzących linków z prawdopodobieństwem d (czynnik tłumienia, zwykle 0,85), lub zacznie od nowa i przeleci do losowej strony z prawdopodobieństwem (1−d). Ten mechanizm przeskoku zapewnia, że surfer nie zostanie nieskończenie długą drogę w podgrafie bez wyjścia i gwarantuje, że łańcuch jest niezmienniczy i aperiodyczny. Dzięki temu istnieje zawsze jednoznaczna rozkład stały, niezależnie od struktury grafu łączeń. Węzeł zawiesiny — strona bez żadnych wychodzących linków — ma swoją prawdopodobieństwo rozłożone równomiernie po wszystkich N stronach, jakby łączyła się z każdym; bez tego poprawienia prawdopodobieństwo skupione na tej stronie by straciło się w systemie.

Iteracja mocy: mnożenie macierzy, powtarzane

Zamiast rozwiązywać równanie π·P = π — niemożliwe dla miliarda stron — PageRank używa iteracji mocy: zaczyna od rozłożenia jednorodnego i wielokrotnie mnoży przez macierz przejścia, aż przestanie się zmieniać. Każda iteracja kosztuje O(E), dotykając każdego krawędzi exactly once, co sprawia, że PageRank jest zarządzalny na skalę internetu — mnożenie macierzy gęstej kosztowałoby O(N²) i byłoby całkowicie niemożliwe. Zbieżność gwarantuje twierdzenie Perrona-Frobeniusa: ponieważ każda wartość w macierzy przejścia zatrzaskanej jest co najmniej (1−d)/N > 0, macierz ma jednoznaczny największy wartości własny λ₁ = 1 z wektorem własnym o wartościach dodatnich, a powtarzane mnożenie wyprowadza wszystkie pozostałe komponenty wartości własnych na szybkość ograniczoną przez czynnik zatrzaskiwania d.

PR(p) = (1 − d)/N + d · Σ_(q→p) PR(q) / L(q)

d = 0.85 → ~50-100 power-iteration steps to converge
π_t = π₀·P^t → v₁ as t → ∞     (convergence rate ∝ |λ₂|^t, bounded by d)

Poza siecią internet

Taka sama idea "przechadzającego się losowo + stała rozkładu" występuje tam, gdzie potrzebne jest rangowanie węzłów według strukturalnej ważności zamiast lokalnych cech: wyniki wpływów w sieciach społecznych, rangi papierów oparte na cytowaniu (pierwotna inspiracja PageRanka), systemy rekomendacji indywidualizowane, które skupiają się na znanych zainteresach poprzez przeskok, proteinie strukturalnie centralne w sieciach interakcji biologicznych, oraz próbkowanie Metropolis-Hastings, które podporządkowuje metody Monte Carlo Markowa.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz PageRank i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.