¿Cuál es la relación entre los vectores propios y el pagerank / search?

Answer 1

Supongamos que tiene 4 páginas (A, B, C y D) y están conectadas entre sí con un gráfico dirigido. A indica B y C, B indica C, C indica D y D indica C. Luego, A vota 1/2 por B y 1/2 por C. Asimismo, B vota 1 por C, C vota 1 por D y D votos 1 por C. (cada nodo puede votar solo por 1 en suma para ser justos) Luego, cuente cuántos votos obtuvieron considerando la importancia de cada página.

P (A) = 0 (voto de A) * P (A) + 0 (de B) * P (B) + 0 (de C) * P (C) + 0 (de D) * P (D)

P (B) = 1/2 (voto de A) * P (A) + 0 (de B) * P (B) + 0 (de C) * P (C) + 0 (de D) * P (D )

P (C) = 1/2 (de A) * P (A) + 1 (de B) * P (B) + 0 (de C) * P (C) + 1 (de D) * P (D)

P (D) = 0 (de A) * P (A) + 0 (de B) * P (B) + 1 (de C) * P (C) + 0 (de D) * P (D)

Convirtiendo la ecuación anterior en un problema matricial,

(P (A), P (B), P (C), P (D)) ‘= M (P (A), P (B), P (C), P (D))’

, donde M es una matriz, [[0 0 0 0], [1/2 0 0 0], [1/2 1 0 1], [0 0 1 0]]

Esto es exactamente un problema de valor propio. El vector de pagerank es el vector propio cuyo valor propio es 1. Curiosamente, la suma de columnas de M siempre es 1. Esta matriz se llama matriz de columna estocástica, que tiene muchas propiedades interesantes 🙂 Por lo tanto, un vector propio de rango de página indica cuántos votos obtiene cada página web de otras páginas web considerando sus importancias.

Ahora, se vuelve un poco complicado.

En M x = x , x1 * m1 + x2 * m2 + x3 * m3 + x4 * m3 = x . Cada componente de x describe cuánto es importante el nodo. Supongamos que x = (0.7, 0.1, 0.1, 0.1). Entonces, el primer nodo es importante, por lo que su voto tiene un 70% de importancia en la ecuación. Del mismo modo, los otros nodos tienen un 10% de importancia. En otras palabras, cada columna de la matriz representa el estado del voto de cada nodo.

Answer 2

El rango de cualquier página (r) se puede expresar como
Q ‘r = r
dónde,
Q ‘es una matriz estocástica limitada a un subgráfico que utiliza un factor de amortiguación, generalmente utilizado como 0,85 por Google.

Este tipo de ecuación es la definición clásica del problema de valor propio / vector. Y el objetivo es encontrar el valor propio correspondiente al mayor valor propio 1.
Google prefiere el Método de energía para encontrar el valor propio.
Para más información vaya a: @http: //www2002.org/CDROM/poster/…

Answer 3

Piense en el modelo de factor SVD o en las transiciones de estado estable de Markov.

Answer 4

Básicamente es solo aplicar vectores propios más agregar una constante (factor de amortiguación). Para una buena explicación del algoritmo y la conexión con los vectores propios, vea PageRank