Matriz de Google

Una matriz de Google es una matriz estocástica específica que utiliza el algoritmo PageRank de Google . Esta matriz representa un grafo con aristas que representan enlaces entre páginas. El PageRank de cada página se puede generar iterativamente a partir de la matriz de Google mediante el método de potencia . Sin embargo, para que este método converja, la matriz debe ser estocástica, irreducible y aperiódica .

Para generar la matriz de Google G , primero debemos generar una matriz de adyacencia A que represente las relaciones entre páginas o nodos.

Suponiendo que hay N páginas, podemos completar A haciendo lo siguiente:

1. Un elemento de matriz${\displaystyle A_{i,j}}$se llena con 1 si nodo${\displaystyle j}$tiene un enlace al nodo${\displaystyle i}$y 0 en caso contrario; esta es la matriz de adyacencia de enlaces.
2. Una matriz relacionada S correspondiente a las transiciones en una cadena de Markov de una red dada se construye a partir de A dividiendo los elementos de la columna "j" por un número de${\displaystyle k_{j}=\Sigma _{i=1}^{N}A_{i,j}}$dónde${\displaystyle k_{j}}$es el número total de enlaces salientes desde el nodo j a todos los demás nodos. Las columnas con elementos de matriz cero , correspondientes a nodos colgantes, se reemplazan por un valor constante 1/N . Este procedimiento agrega un enlace desde cada sumidero, estado colgante ${\displaystyle a}$a todos los demás nodos.
3. Ahora bien, por construcción, la suma de todos los elementos de cualquier columna de la matriz S es igual a la unidad. De esta forma, la matriz S está bien definida matemáticamente y pertenece a la clase de cadenas de Markov y a la clase de operadores de Perron-Frobenius. Esto hace que S sea adecuada para el algoritmo PageRank .

Entonces, la matriz final de Google G se puede expresar a través de S como:

${\displaystyle G_{ij}=\alpha S_{ij}+(1-\alpha ){\frac {1}{N}}\;\;\;\;\;\;\;\;\;\;\;(1)}$

Por construcción, la suma de todos los elementos no negativos dentro de cada columna de la matriz es igual a la unidad. El coeficiente numérico${\displaystyle \alpha }$se conoce como factor de amortiguación.

Por lo general, S es una matriz dispersa y, para las redes dirigidas modernas ^, tiene solo unos diez elementos distintos de cero en una fila o columna, por lo que solo se necesitan unas 10 N multiplicaciones para multiplicar un vector por la matriz G. [ ^{2 ] [ 3 ]} 

Un ejemplo de la matriz${\displaystyle S}$La construcción mediante la ecuación (1) dentro de una red simple se presenta en el artículo CheiRank .

Para la matriz real, Google utiliza un factor de amortiguación.${\displaystyle \alpha }$alrededor de 0,85. ^{[ 2 ] [ 3 ] [ 4 ]} El término${\displaystyle (1-\alpha )}$le da a un surfista la probabilidad de saltar aleatoriamente a cualquier página. La matriz${\displaystyle G}$pertenece a la clase de operadores de Perron-Frobenius de cadenas de Markov . ^{[ 2 ]} Los ejemplos de la estructura de la matriz de Google se muestran en la Fig. 1 para la red de hipervínculos de artículos de Wikipedia en 2009 a pequeña escala y en la Fig. 2 para la red de la Universidad de Cambridge en 2006 a gran escala.

Para${\displaystyle 0<\alpha <1}$Solo existe un valor propio máximo.${\displaystyle \lambda =1}$con el vector propio derecho correspondiente que tiene elementos no negativos${\displaystyle P_{i}}$que puede considerarse como una distribución de probabilidad estacionaria. ^{[ 2 ]} Estas probabilidades ordenadas por sus valores decrecientes dan como resultado el vector PageRank.${\displaystyle P_{i}}$con PageRank${\displaystyle K_{i}}$utilizado por la búsqueda de Google para clasificar páginas web. Normalmente se tiene para la World Wide Web que${\displaystyle P\propto 1/K^{\beta }}$con${\displaystyle \beta \approx 0.9}$. El número de nodos con un valor de PageRank determinado se escala como${\displaystyle N_{P}\propto 1/P^{\nu }}$con el exponente${\displaystyle \nu =1+1/\beta \approx 2.1}$. ^{[ 6 ] [ 7 ]} El vector propio izquierdo en${\displaystyle \lambda =1}$tiene elementos de matriz constantes. Con${\displaystyle 0<\alpha }$Todos los valores propios se mueven como${\displaystyle \lambda _{i}\rightarrow \alpha \lambda _{i}}$excepto el valor propio máximo${\displaystyle \lambda =1}$, que permanece sin cambios. ^{[ 2 ]} El vector PageRank varía con${\displaystyle \alpha }$pero otros autovectores con${\displaystyle \lambda _ {i}<1}$permanecen sin cambios debido a su ortogonalidad al vector izquierdo constante en${\displaystyle \lambda =1}$. La brecha entre${\displaystyle \lambda =1}$y otro valor propio siendo${\displaystyle 1-\alpha \approx 0.15}$proporciona una rápida convergencia de un vector inicial aleatorio al PageRank aproximadamente después de 50 multiplicaciones en${\displaystyle G}$matriz.

En${\displaystyle \alpha =1}$la matriz${\displaystyle G}$ Generalmente tiene muchos valores propios degenerados.${\displaystyle \lambda =1}$ (véase, por ejemplo, [6] ^{[ 8 ] ). En la figura 3 de [ 5 ]} y en la figura 4 de ^{[ 8 ]} se muestran ejemplos del espectro de valores propios de la matriz de Google de varias redes dirigidas.

La matriz de Google también puede construirse para las redes de Ulam generadas por el método de Ulam [8] para mapas dinámicos. Las propiedades espectrales de dichas matrices se discuten en [9,10,11,12,13,15]. ^{[ 5 ] [ 9 ]} En varios casos, el espectro se describe mediante la ley fractal de Weyl [10,12].

La matriz de Google también se puede construir para otras redes dirigidas, por ejemplo, para la red de llamadas a procedimientos del software del kernel de Linux introducida en [15]. En este caso, el espectro de${\displaystyle \lambda }$se describe mediante la ley fractal de Weyl con la dimensión fractal${\displaystyle d\approx 1.3}$(véase la figura 5 de ^{[ 9 ]} ). El análisis numérico muestra que los autoestados de la matriz${\displaystyle G}$están localizados (véase la figura 6 de ^{[ 9 ]} ). El método de iteración de Arnoldi permite calcular muchos valores propios y vectores propios para matrices de tamaño bastante grande [13]. ^{[ 5 ] [ 9 ]}

Otros ejemplos de${\displaystyle G}$La matriz incluye la matriz de Google del cerebro [17] y la gestión de procesos de negocio [18], véase también. ^{[ 1 ]} Las aplicaciones del análisis de la matriz de Google a las secuencias de ADN se describen en [20]. Este enfoque de la matriz de Google también permite analizar el entrelazamiento de culturas mediante la clasificación de artículos multilingües de Wikipedia sobre personas [21]

La matriz de Google con factor de amortiguación fue descrita por Sergey Brin y Larry Page en 1998 [22], véanse también los artículos sobre la historia de PageRank [23], [24].

• CheiRank
• iteración de Arnoldi
• cadena de Markov
• Operador de transferencia
• Teorema de Perron-Frobenius
• motores de búsqueda web

• Matriz de Google en Scholarpedia
• Cierre de relaciones públicas de Google
• Videoconferencias del taller del IHES "Matriz de Google: fundamentos, aplicaciones y más allá", octubre de 2018.