PDF de programación - Métodos de cálculo del vector PageRank

Bol. Soc. Esp. Mat. Apl. no0 (0000), 1–24

Métodos de cálculo del vector PageRank

F. Pedroche*

Institut de Matem`atica Multidisciplinar

Universitat Polit`ecnica de Val`encia.

[email protected]

Resumen

Los algoritmos de búsqueda de información en internet, como el
PageRank de Google, constituyen un ejemplo excelente de aplicación de
las herramientas básicas del análisis matricial, las cadenas de Markov y
el álgebra lineal numérica. En este trabajo se ilustran los métodos de
solución que se usan para el cálculo del vector PageRank: el método
de la potencia y sus derivados (extrapolación, adaptativo, Arnoldi y
BlockRank), y los basados en la resolución de un sistema lineal por
métodos iterativos (Jacobi, Gauss-Seidel, Schwarz aditivo, métodos de
subespacios de Krylov).

Palabras clave :

Motores de búsqueda, PageRank, procesos de Markov,

matrices no negativas, sistemas lineales, métodos iterativos, cálculo científico.

Clasificación por materias AMS :

15A06, 65C40, 65F10, 65F15, 65F50

1.

Introducción

En mayo de 2005, una consulta en internet usando el motor de búsqueda
Google1 informaba de que se estaba realizando la petición sobre un total de
8,085 millones de páginas. Otra búsqueda, esta vez realizada el 26 de octubre
de 2006, permite estimar que, al menos, hay unos 24,640 millones de páginas
web indexadas2 por Google. Estos datos dan una idea del tamaño y la velocidad
de crecimiento de internet. Si a esto unimos las posibilidades de negocio

*Trabajo subvencionado por los proyectos DGI número MTM2004-02998 y DGI número

MTM2007-64477.

1Una idea de la popularidad de este tipo de búsquedas es que el verbo to google fue
añadido oficialmente al Oxford English Dictionary, en junio de 2006, con el significado de
usar el buscador Google para obtener información en internet.

2Estimación hecha a partir de la petición ”+el** ” OR ”+the**” OR ”+le**” OR ”+der**”
OR ”+O**” OR ”+il**”. El signo más obliga a buscar el artículo el, the, etc. y los asteriscos
son dos palabras cualesquiera; v. [53] para más trucos de Google.

1

2

F. Pedroche

mediante anuncios publicitarios3 que el mismo Google promueve [79], tenemos
que es fundamental disponer de un sistema de clasificación de páginas rápido
y fiable, para poner orden en toda esta maraña de datos que ha ido creciendo
vertiginosamente; para un análisis sobre la estructura de la World Wide Web,
véanse, por ejemplo, [22], [44], [55], [59], [66].

El PageRank [57], el método inicial de cálculo que usaron los fundadores
de Google4 para clasificar las páginas web según su importancia, es objeto
de constantes mejoras. La finalidad del método es la obtención de un vector,
también llamado PageRank, que da la importancia relativa de las páginas5.
Dado que el vector PageRank se calcula en función de la estructura de las
conexiones de la web (v. [24] en un número anterior del Boletín de SEMA) se
dice que es independiente de la petición de la persona que realiza la búsqueda.
Algunas modificaciones del PageRank para hacer intervenir la petición se han
propuesto en [33], [36], [60]. También hay modificaciones del PageRank que
incorporan la utilización del botón de página anterior [70].

Desde el punto de vista de la persona que administra una página web se ha
mostrado que la técnica para obtener un PageRank óptimo consiste en incluir
enlaces a páginas importantes de nuestra misma comunidad web, mientras que
los enlaces irrelevantes nos penalizan a nosotros y a toda nuestra comunidad
[3]. Un análisis del algoritmo PageRank así como diversas propiedades se puede
encontrar, por ejemplo, en [8], [10] [18], [23], [24], [37], [38], [47], [51], [71].

En este trabajo nos centraremos en los nuevos métodos de cálculo del vector
PageRank haciendo especial hincapié en aquellos conceptos del álgebra6 lineal
que intervienen en los modelos. Estos modelos se basan, por una parte, en
desarrollar técnicas para acelerar el método clásico de la potencia (que había
caído en el abandono y prácticamente casi ni se usaba) y, por otra, en usar una
formulación con un sistema de ecuaciones lineales y aplicar entonces un esquema
iterativo. El cálculo práctico, atendiendo a las estucturas de computación
utilizadas, puede ser centralizado (utilizando un procesador) o en paralelo
(usando múltiples procesadores).

El resto del trabajo se estructura de la manera siguiente. En la sección 2 se
introduce el concepto de vector clasificador de páginas PageRank y en la sección
3 se revisa el modelo de Brin y Page para su cálculo. En la sección 4 se resumen
los métodos de solución basados en el método de la potencia. En la sección 5 se
resumen las características de los métodos basados en la escritura de un sistema
de ecuaciones lineales. Finalmente, se dan unas conclusiones del trabajo.

3Los beneficios por publicidad en internet, en EEUU, han crecido un 36 % en el primer

semestre de 2006 [78].

4Véase [76] para conocer detalles sobre los inicios de la compañia Google Inc.
5Las personas registradas en Google pueden instalarse el indicador de PageRank (PR)
incluido en la Google Toolbar. Con esto se puede conocer el PR, en una escala de 0 a 10, de
las páginas que visitemos. Por ejemplo, un diario estatal tiene un PR en torno a 8, mientras
que la página de una universidad tiene un PR alrededor de 5.

6El uso actual de la palabra álgebra proviene del título del libro Kitab al-jabr wa l-muqabala,
(Libro de la reducción y la comparación) escrito en el siglo IX por Mohammed Ibn Musa al-
Khwarizmi [65], [80]; las palabras guarismo y algoritmo derivan de su nombre [4].

Métodos de cálculo del vector PageRank

3

2. El vector PageRank de Google

Una de las características del PageRank es que si uno navega aleatoriamente
por internet y está un tiempo suficientemente grande paseando, entonces
tendrá una gran probabilidad de encontrar las páginas con mayor PageRank.
Para centrar ideas, consideremos un conjunto de cuatro páginas web como en la
figura 1. Vemos que desde la página 1 podemos tomar un enlace a las páginas
2 ó 3. También se ve que desde las páginas 2 ó 4 se pueden acceder al resto de
páginas.

1

2

3

4

2
3

1
3
4

1
2

1
2
3

Figura 1: Una web con cuatro páginas mostrando sus enlaces salientes.

1

3

2

4

Figura 2: Grafo dirigido correspondiente a la web de la figura 1.

Esta estructura de enlaces entre las páginas se puede representar mediante
un grafo dirigido, como el de la figura 2. Dado un conjunto de n páginas web
definimos su matriz de conectividad G como la matriz cuadrada de orden n
cuyos elementos, denominados gij, 1 ≤ i, j ≤ n, valen 1 si hay enlace de la
página j a la página i, con i = j, y 0 en otro caso. La matriz de conectividad
correspondiente al grafo de la figura 2 viene dada entonces por:

(1)




G =


 .

0
1
1
0

1 1
0 1
1 0
1 0

1
1
1
0

Imaginemos que tenemos una persona (un o una surfista) que va saltando
de manera aleatoria de unas páginas a otras. Queremos construir una matriz
de transición P , cuyos elementos den las probabilidades condicionadas de salto.
Para ello, vamos a asumir que, cuando se encuentra en una página, tiene la
misma probabilidad de elegir cualquier enlace saliente. Esta elección es la base
del modelo de Brin y Page. En nuestro ejemplo (figura 1), si el surfista está en
la página 2 entonces tiene una probabilidad de 1/3 de ir a cualquiera de las

4

F. Pedroche

páginas 1, 3 ó 4. Aplicando este razonamiento a las cuatro páginas obtenemos
que la matriz de transición P del surfista aleatorio es en este caso:




P =


 .

1/3 1/2 1/3
0
1/2
0
1/2 1/3
1/3
0
1/2 1/3
0
1/3
0
0

(2)



Desde el punto de vista del cálculo es muy fácil obtener la matriz P a partir
de la matriz G: basta dividir cada columna de G por la suma de los elementos
de G en dicha columna, siempre que esta cantidad no sea cero, es decir, siempre
que esta columna no corresponda a una página sin salida. Para formalizar este
hecho, definamos el número de enlaces salientes (out-degree) de una página j
1 ≤ j ≤ n. Ahora ya podemos construir la matriz P
como: cj =
asociada a la estructura del conjunto de páginas web de acuerdo con nuestra
hipótesis de probabilidad de saltos. Ha de ser P = (pij) ∈ R

n×n, tal que:

n

i=1 gij,

si cj = 0.
en otro caso.

1 ≤ i, j ≤ n.

pij =

gij/cj

Es obvio que si cj

(3)
0
= 0, para todo j, entonces P es una matriz
estocástica por columnas, es decir, la suma de cada columna vale 1 y cada
elemento toma un valor entre 0 y 1. Como ejemplo, la matriz P dada por
la ecuación (2) es estocástica. Además, esta matriz tiene otras propiedades
matemáticas interesantes: su espectro (conjunto de valores propios) es: σ(P ) =
{1,−1/2,−1/3,−1/6}. Su radio espectral7 es ρ(P ) = 1, y la matriz P es
irreducible8 y primitiva9. Estas propiedades son importantes ya que el vector
PageRank [57] es el vector límite de distribución de probabilidad de una cadena
de Markov ergódica: el vector de estado límite10 existe, coincide con el vector
de estado estacionario (un vector de probabilidad asociado al valor propio 1)
y es independiente del vector de estado inicial. Esta propiedad del vector de
estado límite se verifica, en particular, para matrices estocásticas y primitivas:
P ≥ 0, P irreducible y P sólo tiene un valor propio (λ = 1) de módulo el radio
espectral ρ(P ) = 1.
≈
el vector de


con el de estado límite) resulta: vT
, y es el vector PageRank de las cuatro páginas. La
interpretación es la siguiente: si un surfista aleatorio se mueve por un conjunto
de cuatro páginas enlazadas como en la figura 2, entonces, para un tiempo

estado estacionario (que

0,29 0,32 0,29 0,10

2/7 9/28 2/7 3/28

coincide

En este

ejemplo,

est =



7Se define el radio espectral de una matriz cuadrada como el valor máximo, en valor

absoluto, de sus valores propios.
8Una matriz A es irreducible, si, y s