Math
Zufallswege und PageRank
Verfolgen Sie die Wahrscheinlichkeitsmasse durch einen gerichteten Graphen und vergleichen Sie die Power-Iteration mit einer Menge zufälliger Wanderer. Teleportation kann den PageRank zu einer einzigartigen Verteilung konvergieren lassen.Vergleichen Sie einen periodischen Zyklus mit einem Graphen, dessen ungepatchte baumelnde Knoten Masse lecken.
Was passiert
Die Balken zeigen die Verteilung im aktuellen Schritt; Die dünnen Balken zeigen ein Ensemble von Wanderern. Dies ist nicht der Bruchteil der Zeit, die ein Wanderer an jedem Knoten verbringt. In einem gerichteten Zyklus zirkuliert eine Verteilung, die sich auf einen Knoten konzentriert, weiter, während langfristige Besetzungsfraktionen sich noch der gleichmäßigen stationären Verteilung nähern können.
Bei positiver Teleportwahrscheinlichkeit und gepatchten hängenden Zeilen ist die Übergangsmatrix stochastisch und alle Knoten kommunizieren: die stationäre Verteilung ist einzigartig und die Iterationen konvergieren. Wenn Sie eine hängende Zeile leer lassen, entsteht ein undichtes, substochastisches Modell. Seine Referenzlösung ist hier deaktiviert; Dies bedeutet nicht, dass jedem substochastischen Graphen eine stationäre Verteilung fehlt.
Das subdominante Eigenwertmodul beschreibt die asymptotische exponentielle Zerfallsrate, wenn Konvergenz eintritt. Einzelne Schritte können oszillieren, und spezielle Anfangszustände können den langsamsten Modus verpassen. Versuchen Sie einen Punktstart, einen gleichmäßigen Start und verschiedene Dämpfungswerte.
Gleichungen des Moduls
Gleichungen Zufallsweg: P[i][j] = w[i][j] / (Summe über j von w[i][j]); eine Zeile aus Nullen ist ein HÄNGENDER Knoten Google-Matrix: G = d·P + (1 − d)/n, wobei eine hängende Zeile durch die gleichverteilte Zeile ersetzt wird stationär: pi·G = pi mit sum(pi) = 1; erreicht durch Potenzmethode und zur Kontrolle direkt gelöst Konvergenz: der Fehler fällt wie |lambda_2|^n, also IST |lambda_2| die Rate - aber die Schrittweite folgt ihr nur im Mittel, weil ein komplexes subdominantes Paar den Abfall DREHEN lässt (das geometrische Mittel der Schrittverhältnisse stellt sie wieder her, das arithmetische Mittel liegt 1.5 % zu hoch) Dämpfungsschranke: |lambda_2| = d·|mu_2(P)| exakt, also ist |lambda_2| ≤ d eine UNGLEICHUNG - gemessen auf 5.0e-16, um den Faktor 0.667 zu locker im kleinen Netz, scharf auf einem Zyklus, in dem |mu_2| = 1 Rangsenke: bleibt die hängende Zeile leer, zerfällt die Gesamtmasse auf null - der Rang fließt vollständig aus dem System ab periodisch: ein gerichteter n-Zyklus hat die n-ten Einheitswurzeln als Eigenwerte, alle vom Betrag 1; von einem Punkt aus kehrt er alle n Schritte zu diesem Punkt zurück und kommt nie zur Ruhe ungerichtet: die Irrfahrt ist reversibel und pi ist einfach der Grad / 2|E| - eine Zeile Arithmetik und die Kontrolle, dass die Iteration löst, was sie zu lösen vorgibt
