Math
Cammini aleatori e PageRank
Seguire la massa di probabilità attraverso un grafico diretto e confrontare l'iterazione di potenza con una folla di camminatori casuali. Il teletrasporto può far convergere PageRank ad una distribuzione unica. Confronta un ciclo periodico con un grafo i cui nodi pendenti non patchati perdono massa.
Cosa succede
Le barre mostrano la distribuzione allo step corrente; Le sottili barre mostrano un insieme di camminatori. Questi non sono la frazione di tempo trascorso in ogni nodo da un camminatore. In un ciclo diretto, una distribuzione concentrata in un nodo continua a circolare, mentre le frazioni di occupazione a lungo termine possono ancora avvicinarsi alla distribuzione stazionaria uniforme.
Con probabilità di teletrasporto positiva e righe pendenti patched, la matrice di transizione è stocastica e tutti i nodi comunicano: la distribuzione stazionaria è unica e le iterazioni convergono. Lasciare vuota una riga pendente crea un modello sub-stocastico con perdite. La sua soluzione di riferimento è disabilitata qui; Questo non significa che ogni grafo sub-stocastico non abbia una distribuzione stazionaria.
Il modulo dell'autovalore subdominante descrive il tasso di decadimento esponenziale asintotico quando si verifica la convergenza. I singoli passi possono oscillare, e gli stati iniziali speciali possono perdere la modalità più lenta. Prova un punto di partenza, un inizio uniforme e diversi valori di smorzamento.
Equazioni del modulo
Equazioni cammino: P[i][j] = w[i][j] / (somma su j di w[i][j]); una riga di zeri è un nodo SENZA USCITE matrice di Google: G = d·P + (1 − d)/n, con una riga senza uscite sostituita dalla riga uniforme stazionaria: pi·G = pi con sum(pi) = 1; raggiunta con l'iterazione delle potenze, e risolta direttamente come verifica convergenza: l'errore scende come |lambda_2|^n, quindi |lambda_2| È il tasso - ma la dimensione del passo lo segue solo in media, perché una coppia subdominante complessa fa RUOTARE il decadimento (la media geometrica dei rapporti dei passi lo ricostruisce, la media aritmetica resta più alta dell'1.5 %) limite dello smorzamento: |lambda_2| = d·|mu_2(P)| esattamente, quindi |lambda_2| ≤ d è una DISUGUAGLIANZA - misurato fino a 5.0e-16, lasco di un fattore 0.667 sulla piccola rete, stretto su un ciclo dove |mu_2| = 1 pozzo di rango: se la riga senza uscite resta vuota la massa totale decade a zero - il rango fuoriesce del tutto dal sistema periodico: un n-ciclo orientato ha le radici n-esime dell'unità come autovalori, tutte di modulo 1; partendo da un punto ritorna in quel punto ogni n passi e non si assesta mai non orientato: il cammino è reversibile e pi è semplicemente il grado / 2|E| - una riga di aritmetica, e la verifica che l'iterazione risolva ciò che dichiara
