Ppagerank

Pr´actica 4 de Computaci´on Cient´ıfica I Proyecto: Algoritmo PageRank

Fecha de distribuci´on: 13-14/11/2008 Fecha de entrega: 15/01/2009

1.

Ejercicios obligatorios

1. El objetivo del proyecto es ordenar, seg´ un su relevancia, las p´aginas de un sitio web, seg´ un las ideas del algoritmo PageRank empleado en el buscador de Google. El proyecto se desarrollar´a sobre los siguientes sitios web: a) http://www.eps.uam.es b) http://www.uam.es. Dado el volumen de este sitio, ser´a necesario usar t´ecnicas espec´ıficas para matrices sparse. Las fases a seguir ser´an: a) Obtener las relaciones (qu´e p´agina apunta a cu´al) entre las p´aginas del sitio web. Para ello se podr´a usar un Web Spider/Crawler, como por ejemplo el disponible en http://www.openwebspider.org Se recomienda ejecutar el spider fuera de horas de trabajo, en horario nocturno o fin de semana, para evitar cargar los servidores del sitio web. Tambi´en se recomienda usar las siguientes opciones: descargar s´olo las relaciones entre p´aginas (por ejemplo, opci´on ’-r 2’ de openwebspider) y no las p´aginas en s´ı, con su contenido evitar la indexaci´on de las p´aginas (opci´on ’-n’ de openwebspider) evitar saltar a nodos externos al suministrado (opci´on ’-e’ de openwebspider) b) A partir de las relaciones entre p´aginas construir la matriz correspondiente a la cadena de Markov subyacente. Para ello se recomienda usar alguna herramienta de proceso de ficheros de texto, como awk o perl. c) Desarrollar y aplicar el algoritmo PageRank para ordenar las p´aginas Se pide: a) Un programa octave que implemente el algoritmo Pagerank, usando el m´etodo de potencias para el c´alculo de autovalores. 1

16 de enero de 2009, Pr´actica 4 de Computaci´on Cient´ıfica I-Proyecto: Algoritmo PageRank

2

1) Estudiar bajo qu´e condiciones se cumple que X

xi = 1 .

i

2) Aplicar el resultado anterior para trabajar s´olo con matrices sparse. b) Partiendo de los ficheros con la matriz de relaciones entre p´aginas suministrados, o de los obtenidos por el alumno, la lista de las 100 p´aginas m´as importantes de cada los sitios web de la UAM y la EPS, junto con la puntuaci´on obtenida para cada una. Discutir los resultados. c) Un estudio sobre el efecto de alterar el valor del par´ametro de damping α (incluyendo el caso en que valga 1) sobre la convergencia y los resultados obtenidos. d ) Unos programas en awk, perl, etc. que generen: 1) un fichero con los identificadores num´ericos asignados a cada p´agina; 2) un fichero octave con la matriz de relaciones a partir de los ficheros de texto plano con las p´aginas enlazadas y sus identificadores num´ericos. e) Realizar el proceso completo para las webs de la EPS y de la UAM, y alguna otra como http://www.upm.es, http://www.ucm.es o http://www.uc3m.es: 1) Ejecutar openwebspider para obtener los enlaces entre p´aginas. 2) Descargar estos enlaces de la base de datos MySQL a un fichero plano. 3) Generar el fichero octave con la matriz de enlaces entre p´aginas a partir del fichero de texto anterior. 4) Aplicar el algoritmo Pagerank para obtener las 100 p´aginas m´as importantes junto con su puntuaci´on.

2. 2.1.

Ayuda Formato de los archivos suministrados

1. links: pagina origen—pagina destino, donde la pagina origen contiene un enlace a la pagina destino. 2. IDs: url pagina—id numerico. 3. matrices: el elemento Aij es 1 si la p´agina con ID = i tiene un enlace a la p´agina con ID = j. De lo contrario, el elemento es cero.

2.2.

openwebspider sobre linux

1. Descargar la versi´on 0.7 de http://prdownloads.sourceforge.net/openwebspider/openwebspider-0.7.zip?download. 2. Se requiere instalar mysql-server y la parte de desarrollo (libmysqlcliente15-dev para Ubuntu). 3. Compilar con make. 4. Seguir la gu´ıa de configuraci´on en http://www.openwebspider.org/documentation/openwebspider-v06-v07-handbook/ a) Crear la base de datos necesaria para openwebspider con script en sql/sql struct.txt.

16 de enero de 2009, Pr´actica 4 de Computaci´on Cient´ıfica I-Proyecto: Algoritmo PageRank

3

b) Configurar openwebspider editando openwebspider.conf: usuario (root) y contrase˜ na (si se comenta la l´ınea, se asume que no tiene). 5. Ejecutar openwebspider evitando la sobrecarga (opciones -n -r 2 -e). 6. El resultado de la ejecuci´on de openwebspider se almacena en las bases de datos se hosts y se spiderdb.

2.3.

mysql

1. Para entrar en la base de datos se hosts: mysql -u root se hosts. 2. Se pueden ejectuar mandatos mysql usando pipes: echo ”show tables;”| mysql -u root se hosts. 3. Para generar el fichero con las relaciones entre p´aginas se ha de descargar la tabla rels de la base de datos se hosts: a) Usar el mandato select para leer los registros de la tabla. b) Las funciones concat y replace pueden ser u ´tiles para generar archivos como los suministrados, con una l´ınea por cada link, con el nombre de las p´aginas enlazadas separadas por un car´acter separador, por ejemplo ’|’.

2.4.

Generaci´ on del fichero de id’s de p´ aginas con awk y sort

1. ¿C´omo se cambia el separador de campo en awk? 2. ¿C´omo se imprime un campo en awk? 3. ¿C´omo se eliminan l´ıneas repetidas con sort? 4. ¿C´omo se obtiene el n´ umero de l´ınea en awk? Ejemplo de pseudoc´odigo: cat fichero_con_links | awk para imprimir cada url en una l´ ınea | sort para ordenar y eliminar l´ ıneas repetidas | awk para asignar n´ umero de l´ ınea a cada url >ids.txt

2.5.

Generaci´ on de la fichero de enlaces entre p´ aginas con awk, wc y sort

1. ¿C´omo se lee un fichero en awk? 2. ¿C´omo se carga, y se usa, una tabla asociativa (hash) en awk? 3. ¿C´omo se ejecuta c´odigo antes y despu´es del proceso de todas las l´ıneas en awk? 4. ¿C´omo se cuentan las l´ıneas de una archivo con wc? 5. ¿C´omo se pasan variables al invocar a awk? 6. ¿Cu´al es la cabecera de un fichero .m con una matriz sparse?

16 de enero de 2009, Pr´actica 4 de Computaci´on Cient´ıfica I-Proyecto: Algoritmo PageRank 7. ¿C´omo se han de ordenar las entradas de un fichero .m con una matriz sparse? 8. ¿C´omo se usa sort para ordenar por distintos campos? Ejemplo de pseudoc´odigo: cat fichero_con_links | wc para contar enlaces (guardar resultado en una variable) cat awk -

fichero_con_links | que realiza lo siguiente | lee al comenzar la tabla asociativa cambia en cada enlace la p´ agina por de un fichero .m sparse sort para ordenar como espera octave un awk que realiza lo siguiente >enlaces.m - recibe los datos necesarios para la - imprime cabecera .m al iniciarse - imprime l´ ınea a l´ ınea

3.

de p´ agina<->id su id y crea la entrada .m sparse | cabecera .m

Material de consulta http://en.wikipedia.org/wiki/Markov chain http://en.wikipedia.org/wiki/PageRank http://www.ams.org/featurecolumn/archive/pagerank.html http://www.rose-hulman.edu/˜bryan/googleFinalVersionFixed.pdf Datos de prueba: http://trec.nist.gov/ Spider http://www.openwebspider.org/ Documentaci´on de awk http://www.gnu.org/software/gawk/manual Reference Card de awk http://torvalds.cs.mtsu.edu/˜neal/awkcard.pdf Documentaci´on MySQL http://www.mysql.com/documentation Reference Card de MySQL http://www.digilife.be/quickreferences/QRC/MySQL-4.02a.pdf

4