pagerank

Algoritmo PageRank.
Matem´aticas Discretas
Sergio Hern´andez
Facultad de ciencias de la Ingenieria
Universidad Cat´olica del Maule
shernandez@ucm.cl

1

Introducci´
on

Una aplicaci´on de la teor´ıa de grafos es la b´
usqueda en internet. Por ejemplo, el algoritmo
c PageRank utilizado por Google, se basa en una representaci´
on de p´aginas web como
v´ertices y las aristas son loshiperv´ınculos hacia otras p´aginas web. De esta forma es
posible representar la web como grafo dirigido G = (V, E) y al mismo tiempo tambi´en
podemos asignar un valor num´erico PR(v) a cada p´agina de manera de determinar su
relevancia en el contexto de una b´
usqueda en la web.

PR < 5%

PR > 80%

La idea central detr´
as del algoritmo es que dado un conjunto de p´aginas web V queresulta
despu´es de realizar una b´
usqueda, podemos ordenar los resultados utilizando la cantidad
de aristas que entran al v´ertice como m´etrica de importancia o relevancia del sitio. Sin
embargo, aparte de cuantificar la cantidad de aristas de entrada, tambie´en al calcular la
importancia de un v´ertice tambi´en se pondera la importancia de cada v´ertice con aristas
dirigidas hacia.

1Dado que la relevancia de una p´agina web se mide por la cantidad de links que apuntan
hacia ella, podemos interpretar esta importancia de manera proabilistica desde el punto
de vista de un sistema din´
amico (caminatas aleatorias en grafos). Esto quiere decir que
si una p´agina tiene cuatro links, existe una probabilidad apriori de transici´on de x =
[0.25, 0.25, 0.25, 0.25] hacia cada unade ellas.
La matriz de adyacencia A = aij de un grafo nos sirve para representar numericamente
las relaciones entre los v´ertices del grafo, por lo tanto es posible obtener una interpretaci´on
probabilistica cuando normalizamos las filas de matriz A y obtenemos la llamada matriz
de caminata
Definici´
on 1. Matriz de caminata
Sea G = (V, E) un grafo dirigido cuya matriz de adyacencia es A =aij . La
matriz de camino de W con cj = j aij es la suma de la fila i y di = j aij es
la suma de la columna j. Las cantidades cj y di corresponden a los grados de
salida y entrada respectivamente.
La matriz de camino W toma elementos:

wij =

aij /cj
0

si existe una arista entre i y j
de lo contrario

(1)

Los elementos de esta matriz son valores 0 < wij < 1 y corresponden a lasprobabilidades de transici´
on de una cadena de Markov, donde la suma de cada
columna es igual a uno.
Por ejemplo, consideremos el siguiente multi-grafo dirigido:

1

3


0
0
A=
1
1

2

1
0
0
0

4

La correspondiente matriz de caminata de A ser´ıa:
T
0 1/3 1/3 1/3
 0
0 1/2 1/2

W =
 1
0
0
0 
1/2 0 1/2 0


2

1
1
0
1


1
1

0
0Ahora consideremos el vector propio x de la matriz G, tal que:
W x = λx
Dado que W es una matriz estoc´astica izquierda (columnas suman uno), es posible
demostrar que un valor propio de W es λ = 1, por lo tanto podemos escribir la identidad
W x = x (Teorema de Perron-Frobenius). Un m´etodo para obtener el principal vector
propio (o vector PageRank) es conocido como el m´etodo de potencia yconsiste en iniciliazar
x = [1/n, . . . , 1/n] y luego calcular de manera iterativa el vector x∗ , tal que despues de K
iteraciones tenemos:
x ∗ = GK x
El siguiente c´odigo nos muestra como obtener el vector PageRank en Matlab.

3

Program 1 M´etodo de potencia
G=[0,1/3,1/3,1/3;0,0,1/2,1/2;1,0,0,0;1/2,0,1/2,0];
niter=10;
% vector inicial
x=ones(4,1)/4;
for k=1:niter
x=G’*x;
end
Elgr´
afico 1 muestra los vectores PageRank de inicio y despu´es de diez iteraciones.
Figure 1: Vectores PageRank inicial y despu´es de 10 iteraciones
Ejercicio 1
1.1 Calcule el vector PageRank para el grafo en la siguiente Figura. Qu´e pasa con el
vector de relevancia en el caso de los v´ertices que no cuentan con aristas salientes?

1

3

2

4

Es posible observar que este m´etodo...