Duda

El secreto de

´ y el Algebra lineal

Pablo Fern´ndez Gallardo a
Departamento de Matem´ticas a Universidad Aut´noma de Madrid o pablo.fernandez@uam.es Valladolid, 4 de mayo de 2004

Resumen: Desde hace unos a˜os, Google se ha convertido en el buscador est´ndar en la red. Uno de n a sus “secretos”, quiz´s la clave de su ´xito, es el algoritmo (PageRank) que utiliza para ordenar a e losresultados de las b´squedas. El objeto de esta charla es describir el modelo y los resultados u matem´ticos que est´n en la base de estos algoritmos de ordenaci´n: un sabroso c´ctel de Teor´ de a a o o ıa ´ Grafos y Algebra lineal que nos facilita la vida.

Pablo Fern´ndez Gallardo a

´ El secreto de Google y el Algebra lineal

El buscador

Creado en 1998 por Sergei Brin y Lawrence Page enla Universidad de Stanford. El nombre es una variaci´n sobre el t´rmino googol, 10100 . o e Cuestiones importantes a la hora de dise˜ar un buscador en la red: n 1. Computacionales: c´mo o c´mo o c´mo o c´mo o almacenar la informaci´n; o actualizarla; manejar/responder a peticiones; buscar en las bases de datos.

Los n´meros de 1997: 100 millones de p´ginas web. Altavista, 20 millones de consultasdiarias. u a Seg´n la p´gina de Google, hoy atiende a 200 millones de consultas diarias e indexa varios miles de millones u a de p´ginas web. a
3

Pablo Fern´ndez Gallardo a

´ El secreto de Google y el Algebra lineal

2. Tenemos los resultados de una b´squeda: ¿c´mo los mostramos, en qu´ orden? u o e Necesitamos un criterio de ordenaci´n, una asignaci´n de importancias a cada sitio de lared: o o sitios importancias

−→ −→

P1 , . . . , Pn x1 , . . . , x n

Google utiliza el llamado sistema PageRank. Un objetivo: basta leer los 10 primeros resultados para tener la respuesta.
Nota. Hay un par de ingredientes que Google combina con el que veremos aqu´ ı: no es lo mismo que un cierto t´rmino aparezca en una p´gina en el t´ e a ıtulo, en negrita, en un tipo de letra peque˜a,etc. n Para b´squedas combinadas, tampoco es lo mismo que los t´rminos buscados aparezcan u e “cerca” o “lejos” unos de otros.

4

Pablo Fern´ndez Gallardo a

´ El secreto de Google y el Algebra lineal

El modelo

Primer paso: descripci´n de la informaci´n, con un grafo dirigido G. Cada sitio de la red es un v´rtice, y o o e a a hay una arista (dirigida) entre Pi y Pj si desde la p´ginaPi hay un enlace a la p´gina Pj . Matricialmente,
sitio P1
-

sitio P1
?

sitio Pj
?

sitio Pn
?

las entradas mij de la matriz M son

mij =

1 0

si hay enlace Pj → Pi si no

sitio Pi

-

mij

-

enlaces a p´gina Pi a

sitio Pn

-

?

enlaces desde p´gina Pj a
5

Pablo Fern´ndez Gallardo a

´ El secreto de Google y el Algebra lineal

Primer intento: xjes proporcional al n´mero de p´ginas que enlazan con Pj . u a Problema: si una p´gina se cita, digamos, una sola vez, pero desde www.microsoft.com o desde a www.amazon.com. . . Queremos combinar: p´ginas muy citadas; a poco citadas, pero desde sitios importantes. Segundo intento: xj es proporcional a la suma de las importancias de las p´ginas que enlazan con Pj . a a o Por ejemplo, la p´gina P1es citada desde las p´ginas P2, P25 y P256 , mientras que P2 s´lo se cita desde a P1 y P256 , etc. Nuestra asignaci´n x1, . . . , xn debe cumplir que o

x1 x2

= = . . .

K (x2 + x25 + x256 ) , K (x1 + x256) ,

6

Pablo Fern´ndez Gallardo a

´ El secreto de Google y el Algebra lineal

Matricialmente,



  x1 0  x2   .  =K  1  .  . . . . xn

P1 P2 ↓ ↓ 1 0 . . . 0 0 . .. ··· ··· . . . 0 0 . . .

P25 ↓ 1 0 . . . 0 0 . . . ··· ··· . . . 0 0 . . .

P256 ↓ 1 1 . . . 0 0 . . .

 x1 ···  x  · · ·   .2   .  . . . . xn 



Como m´gicamente, hemos transformado el problema en uno de autovalores y autovectores: a

M x = λx .
Buscamos x que sea autovector de M . ¡Pero necesitamos que sus entradas sean no negativas!, lo que escribiremos como x ≥ 0....