Embed Size (px)
Citation preview
Las Matematicas de PageRanky otros metodos de busqueda web
Eustasio del Barrio
Universidad de Valladolid. IMUVA.
Marzo, 2013
Eustasio del Barrio Las Matematicas de PageRank 1 / 31
Plan
Plan
1 Busqueda de informacion
2 Motores de busqueda
3 Analisis de enlaces
4 Conclusiones
5 Referencias
Eustasio del Barrio Las Matematicas de PageRank 2 / 31
Plan
Plan
1 Busqueda de informacion
2 Motores de busqueda
3 Analisis de enlaces
4 Conclusiones
5 Referencias
Eustasio del Barrio Las Matematicas de PageRank 2 / 31
Plan
Plan
1 Busqueda de informacion
2 Motores de busqueda
3 Analisis de enlaces
4 Conclusiones
5 Referencias
Eustasio del Barrio Las Matematicas de PageRank 2 / 31
Plan
Plan
1 Busqueda de informacion
2 Motores de busqueda
3 Analisis de enlaces
4 Conclusiones
5 Referencias
Eustasio del Barrio Las Matematicas de PageRank 2 / 31
Plan
Plan
1 Busqueda de informacion
2 Motores de busqueda
3 Analisis de enlaces
4 Conclusiones
5 Referencias
Eustasio del Barrio Las Matematicas de PageRank 2 / 31
Busqueda de informacion
Busqueda de informacion: (pre)historia
Busqueda de informacion (IR) = busqueda en coleccion de documentosde informacion particular (consulta)
A.C.: colecciones pequenas; etiquetas en rollos de papiro
A.C.: papiro → pergamino; formato libro
Siglo XII: “invencion” del papel; colecciones en monasterios;organizacion por secciones; listas de documentos
1450: Gutemberg, imprenta
Siglo XVIII: primeras bibliotecas publicas; busqueda orientada
1872: clasificacion decimal (Dewey)
1900: Catalogo de tarjetas (por autor, tıtulo)
1940-1950: Ordenador
1989: nacimiento del www (Berner-Lee)
Eustasio del Barrio Las Matematicas de PageRank 3 / 31
Motores de busqueda
El metodo SMART
1960’s; implementado en IBM 7094 & IBM 360Basado en metodos matriciales (matrices termino-documento)
Comienza con diccionario de terminos (palabras o expresiones)
Se indexa cada documento
frecuencia fi,j = #veces termino i aparece en documento j
Matriz termino-documento
Eustasio del Barrio Las Matematicas de PageRank 4 / 31
Motores de busqueda
Vector de consulta:
qT = [q1, . . . , qm] qi ={
1 si termino i presente en consulta0 si no
¿Es el documento i una buena respuesta a la consulta?
¿Esta el vector q cerca de la columna Ai?
Se usa δi = cos θi =qTAi
‖q‖‖Ai‖Se ordenan documentos por δi creciente
Se sugiere documento i a usuario si δi ≥ tol
Mejoras posibles “comprimiendo” matriz A(Dumais, 1989,1994; Bel Labs)
Eustasio del Barrio Las Matematicas de PageRank 5 / 31
Motores de busqueda
Busqueda de informacion: metodos “antiguos”
Ventajas
Encuentran conexiones ocultas
Pueden usarse para identificar clusters de documentos (textmining)
Funcionan bien en colecciones pequenas + homogeneas +estaticas
Inconvenientes
Ranking dependiente de consulta (recalculado para cada consulta)
Solo usa contenido semantico (vıctima facil de spam, estructurade enlaces ignorada)
Dıficil anadir/borrar documentos
Compresion optima no sencilla
Eustasio del Barrio Las Matematicas de PageRank 6 / 31
Motores de busqueda
Busqueda indexada en web
Eustasio del Barrio Las Matematicas de PageRank 7 / 31
Motores de busqueda
Busqueda indexada en web (pre 1998)
patrulla fronteriza: 4; 567; 809; 1103; . . . (8,700,000 en total)
Hezbollah: 9; 12; 339; 942; 15158; . . . (15,100,000 en total)
calentamiento global: 178; 12980; 445532; . . . (33,200,000 en total)
demasiados enlaces por busqueda
facil spam
Yahoo: jerarquıas de sitios web, organizacion humana
Eustasio del Barrio Las Matematicas de PageRank 8 / 31
Motores de busqueda
Cuando se proclamo que la Biblioteca abarcaba todos loslibros, la primera impresion fue de extravagante felicidad.Todos los hombres se sintieron senores de un tesoro intacto ysecreto. No habıa problema personal o mundial cuyaelocuente solucion no existiera: en algun hexagono.. . . A la desaforada esperanza, sucedio, como es natural, unadepresion excesiva. La certidumbre de que algun anaquel enalgun hexagono encerraba libros preciosos y de que esos librospreciosos eran inaccesibles, parecio casi intolerable. Una sectablasfema sugirio que cesaran las buscas. . .
Eustasio del Barrio Las Matematicas de PageRank 9 / 31
Analisis de enlaces
1998: hiperenlaces en accion
Nuevos metodos combinan ranking IR con nuevo ranking depopularidad
La web es diferente de otras colecciones de documentos
es enorme
es dinamica
carece de organizacion centralizada
tiene hiperenlaces
Eustasio del Barrio Las Matematicas de PageRank 10 / 31
Analisis de enlaces
Elementos de un motor de busqueda web
Eustasio del Barrio Las Matematicas de PageRank 11 / 31
Analisis de enlaces
Modulo de ranking: genera ranking de popularidad
mide importancia de cada pagina
medida independiente de consulta, basada en estructura de enlaces
calculado offline, antes de atender consultas de usuarios
algoritmo PageRank de Google se impuso a competidores
Google PageRank = Google $$$
Eustasio del Barrio Las Matematicas de PageRank 12 / 31
Analisis de enlaces
Eustasio del Barrio Las Matematicas de PageRank 13 / 31
Analisis de enlaces
Google PageRank: Lawrence Page & Sergey Brin, 1998
Idea
Crear ranking r(P ) independiente de consulta
Calculos off-line; ahorro computacion en consultas
La web vota con in-links; in-links de sitios importantes pesan mas
in-links de sitio con muchos out-links pesan menos
Eustasio del Barrio Las Matematicas de PageRank 14 / 31
Analisis de enlaces
El algoritmo PageRank
r(P ) =∑
Q∈BP
r(Q)|Q|
BP paginas con enlaces a P ; |Q| numero de paginas enlazadas desde Q
Metodo iterativo: inicialmente r0(P ) = 1n para todas paginas
P1, . . . , Pn
r1(P ) =∑
Q∈BP
r0(Q)|Q|
r2(P ) =∑
Q∈BP
r1(Q)|Q|
...
Eustasio del Barrio Las Matematicas de PageRank 15 / 31
Analisis de enlaces
El algoritmo PageRank
r(P ) =∑
Q∈BP
r(Q)|Q|
BP paginas con enlaces a P ; |Q| numero de paginas enlazadas desde Q
Metodo iterativo: inicialmente r0(P ) = 1n para todas paginas
P1, . . . , Pn
r1(P ) =∑
Q∈BP
r0(Q)|Q|
r2(P ) =∑
Q∈BP
r1(Q)|Q|
...
Eustasio del Barrio Las Matematicas de PageRank 15 / 31
Analisis de enlaces
Tras iteracion k, πTk = [rk(P1), . . . , rk(Pn)],
πTk+1 = πT
k H, hi,j ={
1/|Pi| si i→ j0 si no
Vector PageRank πT = lımk→∞ πTk = πTH (autovector de H)
si el lımite existe
¿se estabilizan los iterantes?¿mide realmente la importancia de las paginas?
Eustasio del Barrio Las Matematicas de PageRank 16 / 31
Analisis de enlaces
Tras iteracion k, πTk = [rk(P1), . . . , rk(Pn)],
πTk+1 = πT
k H, hi,j ={
1/|Pi| si i→ j0 si no
Vector PageRank πT = lımk→∞ πTk = πTH (autovector de H)
si el lımite existe¿se estabilizan los iterantes?
¿mide realmente la importancia de las paginas?
Eustasio del Barrio Las Matematicas de PageRank 16 / 31
Analisis de enlaces
Tras iteracion k, πTk = [rk(P1), . . . , rk(Pn)],
πTk+1 = πT
k H, hi,j ={
1/|Pi| si i→ j0 si no
Vector PageRank πT = lımk→∞ πTk = πTH (autovector de H)
si el lımite existe¿se estabilizan los iterantes?
¿mide realmente la importancia de las paginas?
Eustasio del Barrio Las Matematicas de PageRank 16 / 31
Analisis de enlaces
Tras iteracion k, πTk = [rk(P1), . . . , rk(Pn)],
πTk+1 = πT
k H, hi,j ={
1/|Pi| si i→ j0 si no
Vector PageRank πT = lımk→∞ πTk = πTH (autovector de H)
si el lımite existe¿se estabilizan los iterantes?
¿mide realmente la importancia de las paginas?
Eustasio del Barrio Las Matematicas de PageRank 16 / 31
Analisis de enlaces
El modelo del internauta aleatorio
Internauta parte de pagina web. Aleatoriamente elige enlace a otrapagina
Xn = pagina visitada en instante n
Eustasio del Barrio Las Matematicas de PageRank 17 / 31
Analisis de enlaces
El modelo del internauta aleatorio
Internauta parte de pagina web. Aleatoriamente elige enlace a otrapagina
Xn = pagina visitada en instante n
Eustasio del Barrio Las Matematicas de PageRank 17 / 31
Analisis de enlaces
El modelo del internauta aleatorio
Internauta parte de pagina web. Aleatoriamente elige enlace a otrapagina
Xn = pagina visitada en instante n
Eustasio del Barrio Las Matematicas de PageRank 17 / 31
Analisis de enlaces
El modelo del internauta aleatorio
Internauta parte de pagina web. Aleatoriamente elige enlace a otrapagina
Xn = pagina visitada en instante n
Eustasio del Barrio Las Matematicas de PageRank 17 / 31
Analisis de enlaces
El modelo del internauta aleatorio
Internauta parte de pagina web. Aleatoriamente elige enlace a otrapagina
Xn = pagina visitada en instante n
Eustasio del Barrio Las Matematicas de PageRank 17 / 31
Analisis de enlaces
Xn es una cadena de Markov
P2 es un estado absorbente (dangling node; pagina sin enlaces)
πT = [0, 1, 0, 0, 0, 0]; P2 es un ‘sumidero’ de ranking
Ranking no resulta interesante
‘Dangling nodes’ no cortan navegacion de internautas reales;permitimos salto al azar
Cambiamos filas de ceros por eT
n = [ 1n , . . . ,
1n ]
Eustasio del Barrio Las Matematicas de PageRank 18 / 31
Analisis de enlaces
S es una matriz estocastica, m. de transicion de una cadena de Markov
πT = πTS πT distribucion estacionaria
La web no es ‘fuertemente conexa’; S no es irreducible (hay i 9 j)
Puede haber ‘ciclos’: i→ j → i
Teorema
Si S irreducible y aperiodica existe una unica distribucion estacionaria,πT . Ademas
πTk → π independientemente de πT
0
Eustasio del Barrio Las Matematicas de PageRank 19 / 31
Analisis de enlaces
La matriz Google
Solucion a problemas: permitir salto aleatorio desde cualquier pagina
G = αS + (1− α)eeT
n
G es irreducible y aperiodica tiene distribucion estacionaria unica
πj = proporcion de tiempo que el internauta aleatorio pasa en pagina j
Eustasio del Barrio Las Matematicas de PageRank 20 / 31
Analisis de enlaces
Algunos aspectos importantes
En la Web real n ∼ 1012
La matriz de hiperenlaces es dispersa (menos de 10 out-links en media)
Aun ası almacenamiento de G costoso y calculo de πTk+1 tambien
Cada iteracion requiere ∼ 1024 operaciones
Pero hay buenas noticias
Teorema ∑j
|π(k)j − πj | ≤ 2αk
Si α = 0.85, 50-100 iteraciones garantizan buena aproximacion(10−3 − 10−7) independiente de dimension!!
El resto de la historia es conocido
Eustasio del Barrio Las Matematicas de PageRank 21 / 31
Analisis de enlaces
Algunos aspectos importantes
En la Web real n ∼ 1012
La matriz de hiperenlaces es dispersa (menos de 10 out-links en media)
Aun ası almacenamiento de G costoso y calculo de πTk+1 tambien
Cada iteracion requiere ∼ 1024 operaciones
Pero hay buenas noticias
Teorema ∑j
|π(k)j − πj | ≤ 2αk
Si α = 0.85, 50-100 iteraciones garantizan buena aproximacion(10−3 − 10−7) independiente de dimension!!
El resto de la historia es conocido
Eustasio del Barrio Las Matematicas de PageRank 21 / 31
Analisis de enlaces
Eustasio del Barrio Las Matematicas de PageRank 22 / 31
Analisis de enlaces
HITS (Hypertext Induced Topic Selection, Jon Kleinberg, 1997)
Distincion entre autoridades y distribuidores (hubs)
Buenas autoridades enlazadas desde buenos hubs
Buenos hubs enlazan a buenas autoridades
Eustasio del Barrio Las Matematicas de PageRank 23 / 31
Analisis de enlaces
HITS (Hypertext Induced Topic Selection, Jon Kleinberg, 1997)
Distincion entre autoridades y distribuidores (hubs)
Buenas autoridades enlazadas desde buenos hubs
Buenos hubs enlazan a buenas autoridades
Eustasio del Barrio Las Matematicas de PageRank 23 / 31
Analisis de enlaces
HITS (Hypertext Induced Topic Selection, Jon Kleinberg, 1997)
Distincion entre autoridades y distribuidores (hubs)
Buenas autoridades enlazadas desde buenos hubs
Buenos hubs enlazan a buenas autoridades
Eustasio del Barrio Las Matematicas de PageRank 23 / 31
Analisis de enlaces
HITS (Hypertext Induced Topic Selection, Jon Kleinberg, 1997)
Distincion entre autoridades y distribuidores (hubs)
Buenas autoridades enlazadas desde buenos hubs
Buenos hubs enlazan a buenas autoridades
Eustasio del Barrio Las Matematicas de PageRank 23 / 31
Analisis de enlaces
HITS
ai = puntuacion como autoridad para pagina Pi
hi = puntuacion como hub para pagina Pi
Inicialmente hi = 1; h0 =
1...1
Puntuacion inicial de autoridad ai =∑
j:Pj→Pihi; a1 =
a1...an
= LTh0
Li,j ={
1, Pi → Pj
0, Pi 9 Pj
Eustasio del Barrio Las Matematicas de PageRank 24 / 31
Analisis de enlaces
HITS
ai = puntuacion como autoridad para pagina Pi
hi = puntuacion como hub para pagina Pi
Inicialmente hi = 1; h0 =
1...1
Puntuacion inicial de autoridad ai =∑
j:Pj→Pihi; a1 =
a1...an
= LTh0
Li,j ={
1, Pi → Pj
0, Pi 9 Pj
Eustasio del Barrio Las Matematicas de PageRank 24 / 31
Analisis de enlaces
HITS
ai = puntuacion como autoridad para pagina Pi
hi = puntuacion como hub para pagina Pi
Inicialmente hi = 1; h0 =
1...1
Puntuacion inicial de autoridad ai =∑
j:Pj→Pihi; a1 =
a1...an
= LTh0
Li,j ={
1, Pi → Pj
0, Pi 9 Pj
Eustasio del Barrio Las Matematicas de PageRank 24 / 31
Analisis de enlaces
HITS
ai = puntuacion como autoridad para pagina Pi
hi = puntuacion como hub para pagina Pi
Inicialmente hi = 1; h0 =
1...1
Puntuacion inicial de autoridad ai =∑
j:Pj→Pihi; a1 =
a1...an
= LTh0
Li,j ={
1, Pi → Pj
0, Pi 9 Pj
Eustasio del Barrio Las Matematicas de PageRank 24 / 31
Analisis de enlaces
HITS
Se refina puntuacion hub: hi =∑
j:Pi→Pjaj ; h1 = La1
En pasos sucesivos a2 = LTh1, h2 = La2,. . .
A = LTL matriz de autoridades ak+1 = Aak
H = LLT matriz de hubs hk+1 = Hhk
ak → a; hk → h; autovectores
a,h no bien definidos si A,H reducibles
Eustasio del Barrio Las Matematicas de PageRank 25 / 31
Analisis de enlaces
HITS
Se refina puntuacion hub: hi =∑
j:Pi→Pjaj ; h1 = La1
En pasos sucesivos a2 = LTh1, h2 = La2,. . .
A = LTL matriz de autoridades ak+1 = Aak
H = LLT matriz de hubs hk+1 = Hhk
ak → a; hk → h; autovectores
a,h no bien definidos si A,H reducibles
Eustasio del Barrio Las Matematicas de PageRank 25 / 31
Analisis de enlaces
HITS
Se refina puntuacion hub: hi =∑
j:Pi→Pjaj ; h1 = La1
En pasos sucesivos a2 = LTh1, h2 = La2,. . .
A = LTL matriz de autoridades ak+1 = Aak
H = LLT matriz de hubs hk+1 = Hhk
ak → a; hk → h; autovectores
a,h no bien definidos si A,H reducibles
Eustasio del Barrio Las Matematicas de PageRank 25 / 31
Analisis de enlaces
HITS
Se refina puntuacion hub: hi =∑
j:Pi→Pjaj ; h1 = La1
En pasos sucesivos a2 = LTh1, h2 = La2,. . .
A = LTL matriz de autoridades ak+1 = Aak
H = LLT matriz de hubs hk+1 = Hhk
ak → a; hk → h; autovectores
a,h no bien definidos si A,H reducibles
Eustasio del Barrio Las Matematicas de PageRank 25 / 31
Analisis de enlaces
HITS
Se refina puntuacion hub: hi =∑
j:Pi→Pjaj ; h1 = La1
En pasos sucesivos a2 = LTh1, h2 = La2,. . .
A = LTL matriz de autoridades ak+1 = Aak
H = LLT matriz de hubs hk+1 = Hhk
ak → a; hk → h; autovectores
a,h no bien definidos si A,H reducibles
Eustasio del Barrio Las Matematicas de PageRank 25 / 31
Analisis de enlaces
Problema reducido si se calculan a,h sobre grafo asociado aquery+vecinos
HITS da dos rankings interesantes
ranking es query-dependent; demasiada computacion por consulta
A, H no estocasticas; modificaciones posibles
SALSA (Stochastic Approach for Link-Structure Analysis, Lempel& Moran)
Eustasio del Barrio Las Matematicas de PageRank 26 / 31
Analisis de enlaces
Problema reducido si se calculan a,h sobre grafo asociado aquery+vecinos
HITS da dos rankings interesantes
ranking es query-dependent; demasiada computacion por consulta
A, H no estocasticas; modificaciones posibles
SALSA (Stochastic Approach for Link-Structure Analysis, Lempel& Moran)
Eustasio del Barrio Las Matematicas de PageRank 26 / 31
Analisis de enlaces
Problema reducido si se calculan a,h sobre grafo asociado aquery+vecinos
HITS da dos rankings interesantes
ranking es query-dependent; demasiada computacion por consulta
A, H no estocasticas; modificaciones posibles
SALSA (Stochastic Approach for Link-Structure Analysis, Lempel& Moran)
Eustasio del Barrio Las Matematicas de PageRank 26 / 31
Analisis de enlaces
Problema reducido si se calculan a,h sobre grafo asociado aquery+vecinos
HITS da dos rankings interesantes
ranking es query-dependent; demasiada computacion por consulta
A, H no estocasticas; modificaciones posibles
SALSA (Stochastic Approach for Link-Structure Analysis, Lempel& Moran)
Eustasio del Barrio Las Matematicas de PageRank 26 / 31
Analisis de enlaces
Problema reducido si se calculan a,h sobre grafo asociado aquery+vecinos
HITS da dos rankings interesantes
ranking es query-dependent; demasiada computacion por consulta
A, H no estocasticas; modificaciones posibles
SALSA (Stochastic Approach for Link-Structure Analysis, Lempel& Moran)
Eustasio del Barrio Las Matematicas de PageRank 26 / 31
Analisis de enlaces
Enganando a PageRank
PageRank asume ‘buena fe’ en enlaces y paginas (don’t be evil)
Manipular PageRank puede producir beneficios (rendimientopublicitario, divertirse un poco,. . . )
Eustasio del Barrio Las Matematicas de PageRank 27 / 31
Analisis de enlaces
Enganando a PageRank
PageRank asume ‘buena fe’ en enlaces y paginas (don’t be evil)
Manipular PageRank puede producir beneficios (rendimientopublicitario, divertirse un poco,. . . )
Eustasio del Barrio Las Matematicas de PageRank 27 / 31
Analisis de enlaces
Eustasio del Barrio Las Matematicas de PageRank 28 / 31
Analisis de enlaces
Eustasio del Barrio Las Matematicas de PageRank 28 / 31
Analisis de enlaces
Paginas accedidas desde paginas relacionadas con consultaconsideradas relevantes tambien
Bomba desactivada; otras debilidades descubiertas
El vector PageRank es estable; el ranking, no
SEO’s, link farms
Efecto de link farms controlable (?) analizando grafo
Eustasio del Barrio Las Matematicas de PageRank 29 / 31
Analisis de enlaces
Paginas accedidas desde paginas relacionadas con consultaconsideradas relevantes tambien
Bomba desactivada; otras debilidades descubiertas
El vector PageRank es estable; el ranking, no
SEO’s, link farms
Efecto de link farms controlable (?) analizando grafo
Eustasio del Barrio Las Matematicas de PageRank 29 / 31
Analisis de enlaces
Paginas accedidas desde paginas relacionadas con consultaconsideradas relevantes tambien
Bomba desactivada; otras debilidades descubiertas
El vector PageRank es estable; el ranking, no
SEO’s, link farms
Efecto de link farms controlable (?) analizando grafo
Eustasio del Barrio Las Matematicas de PageRank 29 / 31
Analisis de enlaces
Paginas accedidas desde paginas relacionadas con consultaconsideradas relevantes tambien
Bomba desactivada; otras debilidades descubiertas
El vector PageRank es estable; el ranking, no
SEO’s, link farms
Efecto de link farms controlable (?) analizando grafo
Eustasio del Barrio Las Matematicas de PageRank 29 / 31
Analisis de enlaces
Paginas accedidas desde paginas relacionadas con consultaconsideradas relevantes tambien
Bomba desactivada; otras debilidades descubiertas
El vector PageRank es estable; el ranking, no
SEO’s, link farms
Efecto de link farms controlable (?) analizando grafo
Eustasio del Barrio Las Matematicas de PageRank 29 / 31
Conclusiones
Matematicas resuelven problemas; soluciones utiles en problemasconcretos
Historia no terminada: link farms, SEO, Google Panda, GooglePenguin,. . .
Machine learning, BigData, Social Netwokrs, . . . areas activas deinvestigacion matematica/estadıstica/informatica teorica yaplicada
Tambien una gran fuente de empleo
Eustasio del Barrio Las Matematicas de PageRank 30 / 31
Referencias
Libros:
Langville, A. N. y Meyer, C. D. (2006). Google’s PageRank andBeyond: The Science of Search Engine Rankings. Princeton Univ. Press.
Manning, C.D., Raghavan, P. y Schutze, H. (2008). Introduction toInformation Retrieval, Cambridge University Press.
Bonato, A. (2008). A Course on the Web Graph. A.M.S. - GraduateStudies in Mathematics.
Algorithms and Models for the Web-Graph. Lecture Notes in ComputerScience. Springer. (9o workshop en 2012)
Artıculo:
Langville, A. N. y Meyer, C. D. (2003). Deeper inside pagerank.Internet Mathematics, 1, 335–380.
Eustasio del Barrio Las Matematicas de PageRank 31 / 31
