Math
Błądzenia losowe i PageRank
Śledź masę prawdopodobieństwa poprzez ukierunkowany wykres i porównaj iterację mocy z tłumem losowych spacerowiczów. Teleportacja może sprawić, że PageRank zbiegnie się do unikalnego rozkładu. Porównaj cykl okresowy z grafem, którego niepoprawione wiszące węzły przeciekają masę.
Co się dzieje
Słupki pokazują rozkład w bieżącym kroku; Cienkie słupki pokazują zespół spacerowiczów. Nie jest to ułamek czasu spędzonego w każdym węźle przez jednego spacerowicza. W cyklu ukierunkowanym rozkład skoncentrowany w jednym węźle nadal krąży, podczas gdy długoterminowe frakcje zatrudnienia mogą nadal zbliżać się do jednolitego rozkładu stacjonarnego.
Z dodatnim prawdopodobieństwem teleportu i poprawionymi wiszącymi wierszami, macierz przejścia jest stochastyczna i wszystkie węzły komunikują się: rozkład stacjonarny jest unikalny, a iteracje zbiegają się. Pozostawienie pustego wiersza wiszącego tworzy nieszczelny, sub-stochastyczny model. Jego rozwiązanie referencyjne jest wyłączone tutaj; Nie oznacza to jednak, że każdy graf podstocjastyczny nie posiada rozkładu stacjonarnego.
Moduł wartości własnej subdominującej opisuje asymptotyczną szybkość rozpadu wykładniczego, gdy występuje zbieżność. Poszczególne kroki mogą oscylować, a specjalne stany początkowe mogą przegapić najwolniejszy tryb. Wypróbuj punktowy start, jednolity start i różne wartości tłumienia.
Równania modułu
Równania błądzenie: P[i][j] = w[i][j] / (suma po j z w[i][j]); wiersz zer to węzeł WISZĄCY macierz Google: G = d·P + (1 − d)/n, przy czym wiersz wiszący zastępowany jest wierszem jednostajnym stacjonarny: pi·G = pi przy sum(pi) = 1; osiągany przez iterację potęgową i rozwiązywany bezpośrednio jako kontrola zbieżność: błąd maleje jak |lambda_2|^n, więc |lambda_2| JEST tempem - ale rozmiar kroku śledzi je tylko średnio, ponieważ zespolona para subdominująca sprawia, że zanikanie się OBRACA (średnia geometryczna ilorazów kroków odtwarza je, średnia arytmetyczna jest o 1.5 % za wysoka) ograniczenie tłumienia: |lambda_2| = d·|mu_2(P)| dokładnie, więc |lambda_2| ≤ d jest NIERÓWNOŚCIĄ - zmierzone z dokładnością 5.0e-16, luźne o czynnik 0.667 na małej sieci, ścisłe na cyklu, gdzie |mu_2| = 1 pochłaniacz rangi: gdy wiersz wiszący zostaje pusty, całkowita masa zanika do zera - ranga wycieka z systemu całkowicie okresowy: skierowany n-cykl ma za wartości własne pierwiastki n-tego stopnia z jedności, wszystkie o module 1; ze startu w punkcie wraca do tego punktu co n kroków i nigdy się nie ustala nieskierowany: błądzenie jest odwracalne, a pi to po prostu stopień / 2|E| - jedna linijka arytmetyki i kontrola, że iteracja rozwiązuje to, co deklaruje
