Math
Paseos aleatorios y PageRank
Sigue la masa de probabilidad a través de un gráfico dirigido y compara la iteración de potencia con una multitud de caminantes al azar. Compara un ciclo periódico con un gráfico cuyos nodos colgantes sin parche pierden masa.
Qué ocurre
Las barras muestran la distribución en el paso actual; Las barras finas muestran un conjunto de caminantes. Estos no son la fracción de tiempo que pasa en cada nodo por un caminante. En un ciclo dirigido, una distribución concentrada en un nodo sigue circulando, mientras que las fracciones de ocupación a largo plazo todavía pueden acercarse a la distribución estacionaria uniforme.
Con probabilidad de teletransporte positiva y filas colgantes parcheadas, la matriz de transición es estocástica y todos los nodos se comunican: la distribución estacionaria es única y las iteraciones convergen. Dejar una fila colgante vacía crea un modelo subestocástico con fugas. Su solución de referencia está desactivada aquí; Esto no significa que cada grafo subestocástico carezca de una distribución estacionaria.
El módulo de autovalor subdominante describe la tasa de desintegración exponencial asintótica cuando se produce la convergencia. Los pasos individuales pueden oscilar, y los estados iniciales especiales pueden perder el modo más lento. Pruebe un punto de inicio, un inicio uniforme y diferentes valores de amortiguación.
Ecuaciones del módulo
Ecuaciones paseo: P[i][j] = w[i][j] / (suma sobre j de w[i][j]); una fila de ceros es un nodo COLGANTE matriz de Google: G = d·P + (1 − d)/n, con una fila colgante sustituida por la fila uniforme estacionario: pi·G = pi con sum(pi) = 1; se alcanza por iteración de la potencia y se resuelve directamente como comprobación convergencia: el error disminuye como |lambda_2|^n, así que |lambda_2| ES la tasa - pero el tamaño del paso solo la sigue en promedio, porque un par complejo subdominante hace que el decaimiento ROTE (la media geométrica de las razones de paso la recupera, la media aritmética queda 1.5 % por encima) cota de amortiguamiento: |lambda_2| = d·|mu_2(P)| exactamente, así que |lambda_2| ≤ d es una DESIGUALDAD - medida hasta 5.0e-16, holgada por el factor 0.667 en la web pequeña, ajustada en un ciclo donde |mu_2| = 1 sumidero de rango: con la fila colgante dejada vacía la masa total decae a cero - el rango se escapa por completo del sistema periódico: un n-ciclo dirigido tiene las raíces enésimas de la unidad como valores propios, todos de módulo 1; desde un inicio en un punto vuelve a ese punto cada n pasos y nunca se estabiliza no dirigido: el paseo es reversible y pi es simplemente grado / 2|E| - una línea de aritmética, y la comprobación de que la iteración resuelve lo que dice resolver
