7  Fundamentos de PageRank

Alguien piensa todavía que ¿el álgebra Lineal no sirve para nada?.

El algoritmo de búsqueda de google es álgebra. Se basa en el cálculo de autovalores y autovectores. Calcular todos los autovalores y autovectores es un problema muy costoso computacionalmente.

7.1 ¿Cómo surge Google?

A finales de la década de 1990, cuando Google se puso en línea, un factor clave que lo distinguía de otros motores de búsqueda era su capacidad para ofrecer constantemente los resultados más relevantes en la parte superior de las listas de búsqueda.

A diferencia de otros motores de búsqueda, donde los usuarios a menudo tenían que cribar páginas de enlaces irrelevantes que simplemente coincidían con la consulta de búsqueda, Google presentaba una experiencia más optimizada.

Esta magia reside en parte en el algoritmo PageRank de Google. Este algoritmo asigna un valor cuantitativo a cada página web, valorando esencialmente su importancia. Al aprovechar PageRank, Google puede clasificar las páginas web y priorizar las más importantes (que normalmente se correlacionan con los resultados más relevantes y útiles) en las listas de búsqueda.

Nuestro objetivo es establecer un método para asignar puntuaciones de importancia a cada página web dentro de la base de datos. Esto permitirá al sistema priorizar estas puntuaciones cuando un usuario realice una búsqueda y se identifique un subconjunto de páginas relevantes.

El foco de esta sección está en el paso clave de definir y cuantificar la “importancia” de una página web dentro de la estructura interconectada de la web.

Nota: Es importante tener en cuenta que si bien la calificación de importancia de una página web es un factor significativo, no es el único determinante de cómo se presentan los enlaces en los resultados de búsqueda.

7.2 PageRank

library(igraph)
library(dplyr)
library(printr)

PageRank es el algoritmo que usa Google en su buscador. Fue desarrollado por Larry Page y Sergey Brin en la Universidad de Stanford.

  • Usa la estructura de enlaces de la web para dar un ranking de la importancia de las páginas web.

  • Si una página \(A\) tiene más enlaces desde otras páginas que otra página \(B\), la página \(A\) es más importante que la página \(B\).

Se basaron en las nociones básicas de Análisis de citas en publicaciones científicas (Bibliometría).

PageRank es una marca registrada y patentada por Google el 9 de enero de 1999 que ampara una familia de algoritmos utilizados para asignar de forma numérica la relevancia de los documentos (o páginas web) indexados por un motor de búsqueda. https://es.wikipedia.org/wiki/PageRank

  • Se calcula para cada página un valor que no depende de la consulta concreta. Refleja la importancia de la página.
  • Los enlaces entre páginas quedan ponderados por las entradas-salidas de la página y por su importancia.
g1 <- graph_from_literal(D-+A, C-+A)
par(mar=c(1,1,1,1))
plot(g1,vertex.size =50)

g2 <- graph_from_literal(E-+B)
plot(g2,vertex.size =50)

  • \(A\) es más importante que \(B\).

  • Cuando desde una página hay un enlace a otra página, el algoritmo le está dando un voto a esa página. Cuantos más votos tenga la página, más importante es.

  • En estos dos grafos \(D\) tiene más votos que \(G\). \(D\) solo recibe un enlace de \(B\) pero \(B\) tiene dos enlaces de entrada. \(G\) recibe un enlace de \(F\) y \(F\) sólo tiene un enlance de entrada.

7.3 Fases

Por tanto se pretende determinar la importancia relativa de los objetos en un grafo en base a enlaces de entrada y salida que reciben. Se construye un grafo ponderado formado por un conjunto de objetos donde los objetos se conectan entre ellos por enlaces (objetos - páginas web, enlaces - hypervínculos entre páginas).

El algoritmo general tiene a grandes rasgos tiene las siguientes etapas:

  • Recopilar enlaces: CollectLinks
  • Crear matriz de enlaces: ConnecitivityMatrix
  • Encontrar las probabilidades de transición: TransitionMatrix
  • Calcular el ranking de las páginas: PageRank

7.4 Un ejemplo en R

Generamos un grafo aleatoriamente

# 10 objetos
# 1 de 4 la probabilidad de enlace entre 2 nodos
g <- random.graph.game(n = 10, p.or.m = 1/4, directed = TRUE)
plot(g,vertex.size =50, layout=layout.auto)

Calculamos PageRank de cada nodo del grafo.

ranking <- page.rank(g)$vector
Warning: `page.rank()` was deprecated in igraph 2.0.0.
ℹ Please use `page_rank()` instead.
ranking
 [1] 0.11719545 0.13099659 0.18098841 0.09948543 0.04907894 0.15518761
 [7] 0.14297613 0.08018575 0.02890570 0.01500000

Visualizamos el ranking. Por filas mostramos cada objeto y su importancia de mayor a menor. El primer objeto de este data.frame es el más relevante.

df <- data.frame(Object = 1:10, PageRank = ranking)
arrange(df, desc(PageRank))
Object PageRank
3 0.1809884
6 0.1551876
7 0.1429761
2 0.1309966
1 0.1171954
4 0.0994854
8 0.0801858
5 0.0490789
9 0.0289057
10 0.0150000

8 ¿Cómo funciona PageRank?

8.1 Matriz de Conectividad - \(M_c\)

  • La matriz de conectividad \(M_c\) almacenará los enlaces de entrada y salida. No es otra cosa que lo que denominamos habitualmente matriz de adyacencia.

  • \(M_c(i,j)=1\) representa un enlace de \(i\) a \(j\) (arco de la \(i\) a la \(j\)).

8.2 Matriz de transiciones

A partir de la matriz anterior \(M_c\) calcularemos las probabilidades de transición: sustituir los 0’s y 1’s con las probabilidades de transición entre \(i\) y \(j\).

Algunos parámetros:

  • outdegree: Número de arcos desde nodo \(k\).

  • indegree: Número de enlaces a nodo \(k\).

  • p: fracción de tiempo en el que un enlace de una web será seguida y \(1-p\) la fracción de tiempo que una web arbitaria será seguida. Es un valor estimado. \(p=0.85\)

Si \(outdegree[j]\) es 0, no hay enlaces salientes desde esta página. Se considera igual la probabilidad de permanecer en la url \(j\) que visitar otra. Por tanto, a todo elemento en una columna que sume 0 se le da como probabilidad de transición \(\frac{1}{n}\).

En esta etapa al final se ha creado una matriz con las probabilidades de transición de una página a alguna de las páginas a las que enlaza.

Si en grafo hay conexión de \(i\) a \(j\) en la matriz de conexión colocamos un 1 en la posición \((j,i)\),

Si las conexiones las tenéis almacenadas en la matriz de accesibilidad \(M_c\), la matriz de transiciones será su traspuesta.

Dada la matriz de enlaces \(M_c\) y siendo \(n\) el número total de páginas coleccionadas, calculamos el outdegree de la matriz completa.

Si \(outdegree[j]>0\) entonces

\[M_t[i,j]=\frac{M_c[i,j]*p}{outdegree[j]}+\delta\]

donde \(\delta=\frac{1-p}{n}\).

8.3 PageRank en un motor de búsqueda

  • Se parte de las probabilidades de transición (transitionMatrix).
  • Solo necesitamos el autovalor mayor en módulo. Puesto que es una matriz estocástica el mayor autovalor vale 1. Y su autovector correspondiente nos resuelve el problema del ranking de las páginas.
  • Habitualmente se usa el método de la Potencia.
  • El autovector contiene los rankings de las páginas para cada web contenida en la matriz de conectividad.
  1. Un web crawler recopila urls, se le asigna un número ID y un conjunto de tokens significativos para esa página (lexicon - palabras que podrían usarse para inferir importancia y significado).
  1. Se almacenan los enlaces de cada página a otras páginas. Se forman listas con enlaces hacia y enlaces desde.
  1. Pagerank aplica el algoritmo de ranking de las páginas y devuelve el orden de relevancia.

8.4 Motor de búsqueda

Por tanto, un sistema de ordenación de páginas en la web funciona de la siguiente forma:

  • En el lado web:
    • Recopilación de documentos de textos - webs
    • Análisis de los documentos
    • Representación de los documentos

En el lado del usuario:

  • Consulta del usuario
  • Análisis de la consulta
  • Representación de la consulta

Ranking:

  • Con ambas representaciones documentos versus consulta, se hace un cálculo de similitud
  • Se hace una ordenación y se extraen los top k documentos para la consulta
  • Visualizar los top k documentos

Con más detalle, tras una búsqueda de un usuario, el motor de búsqueda hace lo siguiente:

  1. Parsea la consulta
  2. Convierte las palabras claves en la consulta a wordIDs
  1. Busca en la lista de páginas ordenadas según la relevancia, la lista de wordIDS confrontando con los tokens asociados a cada web.
  2. Cuando los tokens de una página confrontan con la lista de wordIDS de la búsqueda calula el ranking de esta página para la consulta específica.
  3. Repite hasta que haya encontrado un cierto número de resultados
  4. Ordena las urls seleccionadas por el ranking y devuelve los top k resultados.

Por tanto, los resultados de la búsqueda son una combinación de Pagerank + IR (relevance) score.

IR scores asigna pesos a los tokens de cada búsqueda.

8.5 Matriz de adyacencia ponderada

  • Grafo ponderado: grafo en el que a cada nodo (\(v_i\))se le asigna un valor no negativo, \(p(v_i)\) que es su peso

  • Si de un nodo \(p(v_i)\) parte un solo enlace, \(p(v_i)=1\).

  • Puesto que los valores \(p(v_i)\) se normalizan, \(0 \leq p(v_i) \leq 1\).

  • Los pesos deben cumplir que la suma de \(p(v_i) =1\) para cada fila:

    • el reparto se hace de forma equitativa \(p(v_i)=\frac{1}{j}\) (j enlaces de salida)
    • arbitraria

Con la información de estas ponderaciones, se construye la matriz ponderada:

  • \(M(j,i)=p(\overrightarrow{ij})\) cuando \(i\) y \(j\) son adyacentes.

  • Si \(i \rightarrow j\) entonces \(M(j,i)=\frac{1}{d_i}\) (\(d_i\) es el grado de salida del nodo \(i\))

  • \(M(i,j)=0\) cuando \(i\) y \(j\) no son adyacentes

Nota: nodos sumidero, hipótesis grado fuertemente conectado.

8.6 Matriz estocástica

Vector de probabilidad: aquel vector fila \(v\) con componentes no negativos y cuya suma vale uno. Matriz estocástica: matriz cuadrada en la que cada vila es un vector de probabilidad.

  • Cadenas de Markov

  • Existe un vector de probabilidad, llamado vector punto fijo \(v\) en el que se verifica que cualquier transición de acuerdo con la matriz \(M\) no tiene efecto en sus probabilidades.

\[v=P v\]

  • Cálculo de autovalores y autovectores

Una vez que tenemos esta matriz de transición, existen múltiples librerías que permiten calcular valores y vectores propios. De hecho, el propio R base tiene la función eigen() que calcula tanto los autovalores como los autovectores de una matriz dada (teniendo en cuenta que, por defecto, va a trabajar en \(\mathbb{C}\)).

Internamente, utilizan técnicas numéricas para los cálculos. Es decir, no resuelven los sistema de ecuaciones ni la ecuación característica.

  • Método de la potencia

El método más usado se denomina método de la potencia, que, partiendo de un vector \(\boldsymbol{v}_0\), calcula la siguiente sucesión de vectores: \[\boldsymbol{v}_1 = \frac{M\boldsymbol{v}_0}{\|M\boldsymbol{v}_0\|}, \boldsymbol{v}_2 = \frac{M\boldsymbol{v}_1}{\|M\boldsymbol{v}_1\|}, \ldots, \boldsymbol{v}_{k+1} = \frac{M\boldsymbol{v}_k}{\|M\boldsymbol{v}_k\|}\] hasta que el cambio entre dos de estos vectores sea suficientemente pequeño, es decir, hasta que \(\|\boldsymbol{v}_{k+1} - \boldsymbol{v}_k\| < \varepsilon\), para algún valor pequeño de \(\varepsilon\). Nota: \(\|\boldsymbol{v}\|\) denota la norma euclídea (o módulo) del vector \(\boldsymbol{v}\). Se puede demostrar que este método de la potencia converge, es decir, se detiene en algún momento, y el vector resultante es un autovector asociado al valor propio de mayor valor (en valor absoluto).

Este método se usa todavía en aplicaciones de alto coste computacional, con grandes matrices (millones de filas y columnas, o incluso más), donde solo se necesite el autovalor dominante y su autovector asociado. Concretamente, es el método usado en el algoritmo PageRank de Google.

En R, este método se encuentra implementado en la librería matlib, en la función powerMethod. Si lo usamos con la matriz \(M\) ya normalizada, tenemos:

library(matlib)
resultado <- powerMethod(M)

Podemos ver el autovalor determinado:

resultado$value

y el autovector correspondiente:

resultado$vector

En nuestro caso, como siempre, queremos un vector cuya componentes sumen 1, así que hacemos lo siguiente:

resultado$vector / sum(resultado$vector)

que es prácticamente igual al vector de importancias \(\boldsymbol{x}\).

9 Ejercicio a entregar

En este ejercicio se pide aplicar este algoritmo PageRank a un grafo dirigido ponderado de vuestra elección, bajo ciertas condiciones:

  1. El grafo debe ser procedente de casos reales - alguna red social (buscar grafos por web, Kaggle, etc.
  2. Debe tener, al menos, 50 nodos.
  3. Explicar:
    1. Descripción breve del grafo.
    2. De dónde procede el grafo (fuente de los datos).
    3. Cómo se calculan la matriz y los autovalores y autovectores necesarios.
    4. Dar una tabla ordenada con los nodos más importantes.