lunes, 26 de septiembre de 2011

PageRank: Loops y la Creación de un PageRank Personalizado

Loops
Un posible problema del PageRank son los loops. Por ejemplo, si dos páginas web se linkean entre sí, el algoritmo se quedaría atrapado entre esas dos webs. Cuando ocurre eso el método falla porque no logra distribuir adecuadamente la reputación de esas dos webs al resto de la red. En el trabajo “The PageRank Citation Ranking: Bringing Order to the Web”, Page propone una sencilla solución para este problema. La idea consiste en pensar que nuestro navegante aleatorio cada tanto salta al azar a cualquier otra página de la red. Uno podría imaginarse que el usuario se cansa de dar vueltas entre estos dos sitios que se referencian mutuamente y pasa a visitar otro sitio cualquiera. La solución técnica consiste en distribuir de forma homogénea una porción de la reputación total a cada una de las webs de la red. En concreto, sea u una página web. Luego, definamos a Fu como el conjunto de páginas a las cuales u apunta y a Bu al conjunto de webs que apuntan hacia u. Sea Nu=|Fu| el número de links que salen de u y c el factor de normalización. Entonces el PageRank de cada página web queda definido como:
En donde E(u) es el vector que otorga una fuente inicial de ranking a cada web. Obsérvese que es una función recursiva.

PageRank Personalizado
La solución a los loops abre también una variante para personalizar el PageRank. Si bien uno puede trabajar de manera que a cada web de la red le corresponda la misma cantidad inicial de ranking, esto es alterable. Page indica que originalmente comenzaron a estudiar Internet otorgando a cada sitio un porcentaje inicial ídentico de reputación, independientemente de qué sitio fuera. Por el sólo hecho de existir cada página recibía un:
en el cómputo inicial de su PageRank. Sin embargo, si se modifica el vector E(u) y en vez de distribuir ese 0,15 entre todas las páginas se lo concentra en una sola o en unas pocas, podemos generar un PageRank personalizado que dé más relevancia a ciertas páginas en función de algún criterio que seleccionemos a priori.

PageRank Personalizado aplicado al Subte
Cuando uno realiza una búsqueda en Google.com suele obtener resultados diferentes que cuando la realiza en Google.com.ar. Por ejemplo, los primeros cuatro resultados de búsqueda de la palabra “economía” en Google.com son:
Mientras que los cuatro primeros resultados de Google.com.ar son:
Esto sucede porque Google trabaja con PageRank´s personalizados por países. Google reconoce que cada cultura tiene su propia valoración de los documentos que están en Internet. El idioma, por ejemplo, es una barrera que divide muy marcadamente lo que un argentino mira en Internet de lo que un chino observa. Y eso hace que los chinos enlacen páginas que están escritas en su idioma y los argentinos generen links a páginas que toquen temas de su interés y que estén en castellano. Google trabaja con PageRanks personalizados por países, por idioma, de imágenes, de videos, de libros, de blogs, académicos, etc. Todas esas herramientas trabajan con un ranking personalizado para que la respuesta sea más ajustada a lo que el usuario está interesado en encontrar.

Como decíamos, una forma de lograr la personalización del PageRank es alterando el vector E(u). Imaginemos que en la línea C del subte de la Ciudad de Buenos Aires se habla castellano, mientras que en el resto de las líneas se hablan otros idiomas. Dado que nosotros hablamos en castellano, estamos más interesados en aquello que se haya dicho en ese idioma. Si la red de subte fuera Internet, entonces nuestro buscador personalizado debería priorizar aquellas conversaciones que se hayan dado en la línea C. Para hacer eso alteré el vector E(u) distribuyendo el 0,15 del PageRank inicial sólo entre las 9 estaciones de subte de esa línea. Como se puede observar en la imagen esto provocó que el PageRank se distribuyera más entre los nodos de la línea C y sus adyacentes más cercanos. Esta forma de personalizar el ranking permite agregar mayor valoración a aquello que quien diseña el método quiera priorizar.
Click aqui para ver la imagen más grande (pdf)

No hay comentarios: