PDF de programación - Seminario 2: Análisis de Redes y Búsqueda en la Web: PageRank

Redes y Sistemas Complejos

Cuarto Curso del Grado en Ingeniería Informática

Seminario 2: Análisis de Redes y Búsqueda en la Web: PageRank

Oscar Cordón García

Dpto. Ciencias de la Computación e Inteligencia Artificial

[email protected]

INTRODUCCIÓN: Búsqueda de Información en la Web (1)

La búsqueda en la web implica ejecutar una consulta en un motor de búsqueda.
Como resultado, ese motor devuelve una lista de páginas web que “casan” con la
consulta realizada

Puesto que la WWW tiene un número enorme de páginas, esa lista de páginas
devuelta suele ser un conjunto muy grande

Por esta razón, es fundamental que la lista esté ordenada, proporcionando los
resultados más relevantes en las primeras posiciones

Los métodos de recuperación de información clásicos solo se basan en el texto,
ordenando los resultados por la similitud del contenido. La determinación de la
importancia de una página web es una medida subjetiva

Los algoritmos de análisis de enlaces consideran la naturaleza hipertextual de la web
(los enlaces entre páginas) para definir ese orden, complementando a los
algoritmos clásicos de búsqueda

INTRODUCCIÓN: Búsqueda de Información en la Web (2)

La mayoría de los sistemas de búsqueda en la Web se basan en los Sistemas de
Recuperación de Información clásicos (Booleano, vectorial, …)

INTRODUCCIÓN: Búsqueda de Información en la Web (3)

Estos sistemas no tienen en cuenta la diferencia estructural existente entre un
documento web y uno de texto plano:

• Estructura interna: Un documento web presenta una estructura semántica

mediante etiquetas HTML

• Estructura externa: Una página web puede estar vinculada a muchas otras y

viceversa. Esa vinculación puede indicar una relación entre documentos

A finales de los 90 se propusieron varios sistemas de búsqueda web que aprovechan
la estructura externa de un documento web como el PageRank de Google

Ese algoritmo se basa en el análisis de enlaces de las redes
sociales. En concreto, implementa una medida de Centralidad
de vector propio en el grafo dirigido de la WWW para medir el
Prestigio de rango de las páginas

ANÁLISIS DE ENLACES: PageRank y HITS

En 1998 se propusieron los dos primeros algoritmos de análisis de enlaces y
búsqueda en la web:

• HITS: Presentado por Jon Kleinberg en Enero de 1998 en el Ninth Annual ACM-

SIAM Symposium on Discrete Algorithms

• PageRank: Presentado por Sergey Brin y Larry Page en Abril de 1998 en la

Seventh International World Wide Web Conference (WWW7)

Ambos se basan en los conceptos básicos del Análisis de Citas en publicaciones
científicas, un área de la Bibliometría

Las ideas principales de ambos algoritmos son similares. Mientras que PageRank
define un orden estático entre las páginas web en función de su prestigio, HITS
establece un orden dinámico que depende de la consulta concreta

PageRank está más extendido al ser el algoritmo empleado por Google

PAGERANK: Introducción (1)

PageRank fue desarrollado por Larry Page (de ahí su nombre)
y Sergey Brin

Surgió del proyecto de ambos para proponer un nuevo tipo de
motor de búsqueda que arrancó en 1995 y derivó en un primer
prototipo funcional en 1998. Poco después fundaron Google

Wikipedia: “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”

Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th
International Web Conference (WWW 98), 1998 y Computer Networks and ISDN Systems
30:1-7 (1998) 107-117 (versión extendida: http://infolab.stanford.edu/~backrub/google.html)

Page L., Brin S., Motwani, R., Winograd, T. The PageRank Citation Ranking: Bringing
Order to the Web. Technical Report. Stanford InfoLab (1998-99)

PAGERANK: Introducción (2)

Pagerank define un orden estático en la WWW. Se calcula un valor PR basado en
la medida de prestigio en redes sociales para cada página, que no depende de la
consulta concreta

El PageRank confía en la estructura democrática de la web, considerando su vasta
estructura de enlaces como un indicador de la importancia de una página individual

En esencia, interpreta un hiperenlace de una página x a otra y como un voto de la
página x por la página y

Sin embargo, no sólo cuenta el número absoluto de votos sino que los pondera por la
importancia de la página que efectúa el voto

Así, no es cuestión sólo de las páginas que te apuntan, sino de cuántas páginas
apuntan a ellas y de su importancia: definición recursiva → Centralidad de vector
propio = Prestigio de rango en la red de la WWW

PAGERANK: Análisis de enlaces web (1)

• La web tiene enlaces de entrada y de

salida

• En 1998, la web ya presentaba 150

millones de páginas y 1.7 billones de
enlaces

• PageRank se basa en considerar la

red dirigida de la web y los conceptos
de análisis de citas y centralidad de
vector propio:

• Las páginas que reciben más

enlaces son más “importantes”
que las que reciben pocos enlaces

PAGERANK: Análisis de enlaces web (2)

Las páginas web varían muchísimo en lo que respecta al número de hiperenlaces
recibidos:

Ejemplo: www.joe-schmoe.com contra www.stanford.edu:

• www.stanford.edu recibe 23400 enlaces

• www.joe-schmoe.com recibe 1 enlace

Intuitivamente, una página es tanto más importante cuántos más enlaces recibe. Por
ejemplo, en 1998 la página de Netscape recibía 62804 enlaces

Sin embargo, eso no es suficiente y puede ser contraintuitivo. ¿Qué pasa si una
página recibe un solo enlace pero viene de Yahoo? ¿Es menos importante que otra
que reciba varios enlaces de páginas “poco importantes”?

¡No todos los hiperenlaces son iguales!

PAGERANK: Formulación básica recursiva (1)

Basada en la Centralidad de vector propio (prestigio de rango):

• El peso del voto de cada enlace es proporcional a la importancia (valor

PR) de la página web que emite el voto

• Si una página i con importancia (prestigio) PR=x tiene n hiperenlaces de

salida, reparte su importancia entre ellos: cada enlace recibe x/n votos

• Así, el valor PR de una página es la suma de los valores PR de todas las

páginas que apuntan a ella (la suma ponderada de los votos que recibe)

Con esta definición recursiva es mucho más difícil aumentar artificialmente la
importancia de una página en un motor de búsqueda web (search engine
optimization, SEO)

PAGERANK: Formulación básica recursiva (2)

PAGERANK: Formulación básica recursiva (3)

Para formular estas ideas se considera el grafo de la WWW G=(V,E), donde V es el
conjunto de páginas (n=|V|) y E el de hiperenlaces

El valor PR de una página i, P(i), se calcula como:
donde Oj es el número de enlaces de salida de la página j

iP

)(

=

∑

(

ij

),

∈

E

)

(

jP
jO

Matemáticamente, tenemos un sistema de n ecuaciones con n incógnitas, que se
puede representar de forma matricial:

P=(P(1), …, P (n))T

A

ij

=






1

O
i
,0

,

si

(i,j)

∈

E

en

otro



caso

P = AT·P

Esta ecuación coincide con la ecuación característica para encontrar los vectores
y valores propios de la matriz AT. La solución P es un vector propio de AT, el vector
propio principal, con valor propio 1

PAGERANK: Resolución con el Método de las Potencias

Método iterativo sencillo (funciona cuando la matriz es estocástica):

1. k ← 0

2. Inicializar Pk = (1/n, …, 1/n)T

3. Iterar Pk+1 = AT·Pk

4. Parar cuando ||Pk+1 - Pk||1 < ε

•

||x||1 = ∑i |xi| es la distancia L1

• Se pueden usar otras como la Euclidea

PAGERANK: Ejemplo simple de cálculo del PageRank, primera iteración

AT

= P

= P

PAGERANK: Ejemplo simple de cálculo del PageRank, segunda iteración

AT

= P

= P

PAGERANK: Ejemplo simple de cálculo del PageRank, convergencia

AT

= P

= P

PAGERANK: Interpretación de caminos aleatorios en grafos. El “surfero” aleatorio

Patente de Google PageRank:

“The rank of a page can be interpreted as the probability that a surfer will be at the
page after following a large number of forward links”

•

Imaginemos un surfero que recorre el grafo de la web de forma aleatoria:

• En un instante de tiempo t, el surfero está en alguna página web i

• En el instante de tiempo t+1, el surfero escoge aleatoriamente un hiperenlace

de salida de i y lo sigue, llegando a alguna página j

• El proceso se repite indefinidamente

• Sea p(t)=(p1(t), …, pn(t)) un vector cuyo i-ésima componente indica la probabilidad

de que el surfero esté en la página i en el tiempo t

• p(t) representa una distribución de probabilidad sobre las páginas web

PAGERANK: Interpretación con caminos aleatorios en grafos: El “surfero” aleatorio (2)

El movimiento aleatorio del surfero en la web es un proceso estocástico modelado por
una cadena de Markov:

• cada página web (nodo) i es un estado en el que puede estar el surfero,

• cada hiperenlace (enlace) es una transición que lleva de un estado i a otro j con

una probabilidad (almacenada en la celda aij de la matriz de adyacencia A),

• El surfero, localizado en una página web i, se mueve a otra página j aleatoriamente

de acuerdo a las probabilidades existentes en A según la ecuación: p(t+1)=AT·p(t)

• El vector p(t)=(p1(t), …, pn(t)) es una distribución de probabilidad estacionaria de la

localización del surfero en una página i en el instante de tiempo t (del camino
aleatorio realizado)

• Dicho vector satisface que p=AT·p

(vector propio)

• Una página tiene un prestigio de rango alto

si su probabilidad de ser visitada es alta

PAGERANK: Existencia y unicidad del vector propio P/p

Resultado central de los Procesos de Markov/Teoría de Caminos Aleatorios:

En grafos que satisfagan unas ciertas condiciones, la distribución

estacionaria p (aka. el vector propio P) es única y se alcanzará

independientemente de la distribución inicial de probabilidad

en el instante t=0

Para ello, se debe cumplir que la matriz de transición/adyacenci