Nota sobre la evaluación: deforma intercalada en el texto de este artículo encontrará el enunciado de diversas actividades. Para superar esta unidad didáctica deberá realizar estas actividades redactando un informe en el que se incluyan comentarios y una captura de pantalla de cada actividad para ilustrar su realización. Para entregar este informe deberá crear un documento (OpenOffice o Word) de un máximo de 500 Kb y usar el espacio de entrega y notificación perteneciente a este grupo de unidades didácticas. La realización de forma satisfactoria de este ejercicio implicará la obtención de 0,75 créditos.

1. Introducción

Como es sabido, la página de resultados de los motores de búsqueda lista los documentos encontrado por orden de relevancia (y no, por ejemplo, por orden cronológico o alfabético). Hasta los años 90 los buscadores aplicaron técnicas clásicas de Recuperación de Información para calcular la relevancia de cada página o documento, pero se vió que en el contexto de la Web estas técnicas eran inadecuadas por la gran cantidad de ruido (falsos positivos) que generaban. Google fue el primer motor que supo entender esta diferencia y que aplicó una técnica distinta para ordenar los documentos en su página de resultados: el análisis de enlaces. Esta técnica tiene nombre propio: PageRank. Google ha influenciado de manera duradera la forma en la cual los motores ordenan sus páginas de resultados, de modo que los demás motores (Yahoo, Live, Ask) utilizan principios necesariamente distintos (PageRank está patentado) pero inspirados en la misma idea: el mencionado análisis de enlaces.

2. Contexto

De acuerdo con la teoría clásica de la Recuperación de Información (RI) lo último que debería hacer un sistema documental (los motores de búsqueda son sistemas documentales, entre otras cosas) es entregar listas de resultados ordenadas de forma aleatoria.

Cualquier usuario puede constatar que ante un grupo de documentos sobre un tema determinado, algunos le parecerán más relevantes que otros. Si a este usuario se le presenta un conjunto pequeño de documentos, digamos no más de 50, posiblemente le sea indiferente en orden de los mismos: cronológico, al fabético por título, alfabético por autores, aleatorio, etc., dado que el tiempo para explorar 50 documentos es relativamente pequeño.

Volumen de información

Ahora bien, imaginemos que la respuesta a una petición de información, consiste en un conjunto de mil, diez mil o un millón de documentos. ¿Tiene el más mínimo sentido presentarlos en orden cronológico?; ¿y en orden alfabético?, ¿y en orden aleatorio? ¿Podemos esperar que el usuario disponga de la más mínima posibilidad de explorar el cien por cien de los documentos de un conjunto de miles o de cientos de miles de documentos recuperados?

Los motores de búsqueda dejarían de tener usuarios (y perderían sus contratos publicitarios) si los resultados no fueran entregados de acuerdo a algún principio de relevancia.

La ordenación por relevancia (suponiendo que sea mínimamente eficaz) hace que sea indiferente, a casi todos los efectos, que el número de documentos encontrados se cuente por decenas, por centenares, por miles o incluso por millones porque en todos los casos, al estar ordenados por relevancia, se supone que al usuario le bastará con revisar los primeros documentos; dicho de otro modo, en ningún caso deberá explorar el cien por cien de los documentos como en el caso que los más relevantes pudieran ocupar las últimas posiciones. Otra cosa es que el cálculo de ordenación de relevancia aplicado sea eficiente (o no). Lo que estamos considerando aquí es la filosofía misma de la operación, a saber, cuando se entregan grandes conjunto de documentos, o bien la ordenación por defecto es por relevancia o al menos se presenta como una de las opciones.

Relevancia

Pero, ¿qué es la relevancia? Se han dedicado ríos de tinta a discutir esta cuestión que incluye aspectos lógicos, matemáticos, psicológicos, etc. En sus términos más simples, y siempre en el contexto de los sistemas de información documentales se considera que la relevancia es la propiedad que tiene un documento de satisfacer una necesidad de información. Uno de los puntos más interesantes de la cuestión es que esta propiedad es, en realidad, una co-producción entre las propiedades del documento y las características del usuario (su nivel de formación, sus expectativas, conocimientos previos, tiempo disponible, etc.).

Además, la relevancia no es solamente una cuestión de todo o nada, sino que oscila entre un mínimo (cero por cien relevante) y un máximo (cien por cien relevante). En la vida cotidiana todos tenemos la experiencia de haber visto que, sobre un mismo tema, y dado un grupo de documentos, pongamos una guía de viajes a Roma, que para nosotros algunos tendrán una relevancia cercana a cero (por ejemplo, por estar escritos en japonés o porque está muy desfasada) y otros serán tal vez casi cien por cien relevantes (nos gusta el estilo, el nivel de especialización, la actualización, la selección de temas, las ilustraciones, etc.).

No se detienen aquí los aspectos conflictivos de la relevancia. El orden en el cual los documentos son mostrados al usuario afecta a la relevancia de los mismos. En efecto, imaginemos que tenemos tres documentos: A, B, C. Supongamos que el documento A tiene un 25 por ciento de relevancia (o 0,25); el documento B un 0,50 y el documento C un 0,75. Imaginemos que enseñamos los documentos por ese mismo orden al usuario: encontrará que los tres son muy relevantes porque cada vez obtuvo informaciones nuevas de ellos.

Ahora imaginemos que, en cambio, los mostramos al usuario por este orden: C, B, A. Ahora, cuando llegue al documento B pensará que no es demasiado relevante (porque ya ha leído el C) y cuando llegue al A, le parecerá que es un documentos inútil.

Actividad 1: Haga la misma pregunta sobre un tema de su interés en Google, Yahoo, Live y Ask e intente comparar los diez primeros resultados de cada motor para determinar cuál de ellos le parece más relevante.

Heterogeneidad

La Web aportó, literalmente el espacio de búsqueda más heterogéno de la historia de la humanidad: compuesto por documentos de todos los temas imaginables, sobre aspectos y puntos de vista totalmente diversos, y publicados por parte de actores completamente diversos, con intereses distintos, idiomas y culturas diferentes, etc., e insistimos, todo ellos en un espacio de acceso unificado.

Recuperación con adversario

Por último, debemos señalar uno de los aspectos más característicos de la Web y para el cual la RI clásica no estava en absoluto preparada. Se trata de lo que se denomina recuperación de información “con adversario” (Baeza-Yates, 2007).

En la Web, los autores de páginas y los administradores de sitios están interesados en conseguir que sus sitios queden bien posicionados en las páginas de resultados de los motores. Una parte de esos autores y administradores carecen de escrúpulos a la hora de perseguir sus objetivos de posicionamiento. Con millones de sitios, aunque los administradores no éticos fueran una minoría, podríamos estar hablando de miles y miles de sitios y decenas de miles de páginas sin interés real copando los primeros puestos en las páginas de resultados de los motores de búsqueda si éstos siguieran usando técnicas tan ingenuas como la que aplicaron durante los años 90.

Por lo tanto, por primera vez, los sistema de información (motores de búsqueda en este caso) tuvieron que vérselas con una clase de documentos expresamente “trucados” para aparecer en posiciones de relevancia. Por tanto, a las anteriores razones a favor de un cálculo de relevancia eficiente, se une esta peculiar característica de la web. Dicho de otro modo: sea cual sea el algoritmo de posicionamiento que utilice un motor de búsqueda debe ser inmune (o al menos, relativamente inmune) a los intentos de manipulación de los propios autores de las páginas web y los administradores de documentos.

Actividad 2: Haga algunas búsquedas en Yahoo o en Google sobre términos muy comerciales, y por tanto, susceptible de recibir la presión de algunos expertos en posicionamiento poco (o nada) éticos. Haga pruebas con las siguientes palabras (sin las comillas): “juegos”, “música”, “películas”, “bajar música”, etc. Intente detectar casos de spam (posicionamiento no ético) que ha escapado al motor que usted esté utilizando para la prueba.

3. Análisis de enlaces

Históricamente, la primera respuesta verdaderamente eficiente a todos los desafíos señalados los aportó Google a finales de los noventa con un nuevo concepto: el análisis de enlaces (aunque entonces nadie lo llamaba todavía así).

En concreto, la nueva idea que aportó Google (mejor dicho, los fundadores de Google: Sergei Brin y Larry Page) es la siguiente: en lugar de calcular la relevancia exclusivamente por las características intrínsecas de la página, añadamos también características externas, en este caso, consideremos las características de los enlaces de entrada que recibe una página.

Con estos dos conjuntos de datos: propiedades del documento (p.e., número de veces que aparece la palabra clave en la página) más propiedades de los enlaces de entrada (p.e., cuantos enlaces de entrada tiene la página), Google comenzó a proporcionar una página de resultados mucho más eficiente. Tan eficiente, de hecho, que en cuestión de poco tiempo se hizo con el dominio casi absoluto del mercado de las búsquedas, arrasando no solamente a sus competidores, sino de paso a casi cualquier otra forma alternativa de buscar información en la Web (por ejemplo, los directorios).

Como decimos, la aplicación del análisis de enlaces se ha revelado tan eficiente que Google no volvió a tener auténtica competencia hasta que sus competidores adoptaron su cálculo de relevancia para que también tuviera en cuenta el análisis de enlaces.

Figura 1: La búsqueda avanzada de Google permite saber cuántos enlaces de entrada (base de su PageRank) tiene un sitio

Actividad 3 : Haga una búsqueda en su motor preferido por una tema de su interés. Observe la primera página de resultados. Utilizando la búsqueda avanzada (vea la Figura 1) compare los enlaces de entrada de los tres primeros resultados de la primera página de resultados y los tres primeros resultados de la segunda página de resultado.

¿En qué consiste el análisis de enlaces? A groso modo, se trata de algo muy simple: una página es más importante si recibe más enlaces de entrada. A partir de aquí, las dos principales dificultades son del siguiente tipo: (1) ¿valen lo mismo todos los enlaces de entrada?; (2) dado que la Web está compuesta por miles de millones de documentos y que además es dinámica, ¿cómo implementamos un sistema de análisis que no entre en un bucle sin fin (y que, por tanto, sea incapaz de arrojar resultados en un tiempo razonable)?

Históricamente, han existido dos intentos de respuesta a las preguntas anteriores que, además, se produjeron casi al mismo tiempo: HITS (1997) y PageRank (1998).

HITS es un algoritmo desarrollado por el matemático de la Universidad de Cornell Joan Kleinberg. Existe una gran unanimidad en admirar el acierto conceptual de su propuesta, pero en reconocer a la vez las dificultades prácticas para su implantación, dado que requiere un gran tiempo de cómputo. A grandes rasgos, HITS se basa en considerar dos grandes clases de sitios: hubs (ejes) y authorities . Un hub o eje es una página de la que salen numerosos enlaces hacia otras páginas (probablemente) relacionadas temáticamente. Una authority o autoridad es una página que recibe muchos enlaces de entrada. Las mejores página serán aquellas que sean o bien hubs o bien authorities y según lo que esté buscando el usuario (o bien respuestas directas o bien referencias) preferirá hubs o authorities, diferencia que la página de resultados del motor de búsqueda puede resaltar.

Actualmente, aunque se admite su gran influencia conceptual no se sabe de ningún motor de búsqueda que lo adopte, al menos tal como fué formulado originalmente.

La segunda respuesta, aparecida casi a la vez, fué la aportada por los fundadores de Google Sergei Brin y Larry Page y se denomina, como ya sabemos, PageRank. En un artículo seminal aparecido en 1998 presentaron la idea del algoritmo que, ante el desinterés comercial de los motores existentes en la época y a los cuales intentaron vender sin éxito, acabarían implantando por su propia cuenta en el año 2000 en su motor, Google.

Posteriormente, hacia el 2004, Yahoo anunció su propia variedad de análisis de enlaces, el llamado WebRank . Ahora bien, Yahoo nunca explicó de forma ni siquiera aproximada o conceptual en qué se basaba su algoritmo. Es más, una búsqueda realizada en octubre de este año (con motivo de la revisión de esta unidad) revela que en la propia web de Yahoo el concepto es inexistente. Es decir, a diferencia de HITS o de PageRank, WebRank está totalmente indocumentado, incluso por parte de su propia empresa (Yahoo).

Por lo tanto, si hacemos un balance rápido tenemos esta situación: todos los motores de búsqueda importantes actuales (Google, Yahoo, Live, Ask, etc.) aplican el análisis de enlaces. De los tres algoritmos más o menos conocidos, HITS no se ha llegado a implementar por sus dificultades técnicas (problemas de tiempo de cómputo) y el algortimo de Yahoo (WebRank) es virtualmente clandestino.

PageRank es el único algortimo bien documentado. Es por esta razón, en primer lugar, que vamos a ocuparnos a partir de ahora únicamente de PageRank. En segundo lugar, en realidad los algoritmos de todos los motores de búsqueda importantes están directamente influenciados por PageRank. De hecho lo que intentan los demás motores, por ingeniería inversa, y se supone que de una forma ética (es decir sin caer en el plagio o el espionaje industrial) es clonar PageRank.

Por último, cabe destacar que la razón por la cual PageRank ha acabado imponiéndose sobre HITS no es solamente porque ofrecía un modelo conceptual tan válido como el HITS o más (aunque diferente), sino porque ofrecía un algoritmo viable . La moraleja es que no bastan las buenas ideas, sino que debe ser posible llevarlas a la práctica.

4. PageRank

El PageRank (PR a partir de ahora) es, a la vez, un método de análisis de enlaces (un algortimo) y el resultado del mismo, a saber, una medida estadística, en concreto una medida de visibilidad o de popularidad de una página calculada a partir de (1) el número de enlaces de entrada de un sitio web y (2) la calidad de los enlaces, esto es, si los sitios de los que proceden los enlaces son a su vez son muy enlazados.

Por lo tanto, se trata de un rasgo recursivo: un sitio web enlazado por un sitio web muy popular tendrá un mayor PR que un sitio web enlazado por uno poco popular. A la vez, los sitios de los que salen mucho enlaces reparten su PR de manera proporcional entre cada uno de sus enlaces de salida. Por tanto, un sitio con un alto PR transmite menos PR a las páginas que enlaza que otro sitio con menor PR relativo pero que tiene menos enlaces de salida.

Como se ve, calcular el PR de todas y cada una de las página de la Web (o al menos de todas y cada una de las páginas en el índice de Google) requiere cálculos recursivos. El problema de los cálculos recursivos lo indica su nombre: no tienen una parada. El mérito de Brin y Page fué desarrollar una fórmula que hacía que el cálculo fuera eficiente con un número limitado y muy manejable de iteraciones (ocho en total, según explican en su artículo de 1998).

La cuestión es que, al final de tales cálculos, el PR de una página consiste en un número que será mas alto cuantos más enlaces reciba de páginas que, a su vez, tengan un alto PR. En su página para webmasters, Google indica lo siguiente:

“PageRank interpreta un enlace desde la página A a la página B como un voto para la página B por parte de la página A. PageRank determina entonces la importancia de una página por el número de votos que recibe. También considera la importancia de cada página que emite el voto, por lo que los votos de algunas páginas se consideran de mayor valor, dando así a la página enlazada mayor valor. Las páginas más importantes tienen un mayor PageRank y aparecen en la parte superior de los resultados de búsqueda.”

Actividad 4: Acceda a esta dirección: http://infolab.stanford.edu/~backrub/google.html

y podrá descargar una de las primeras versiones publicadas del algoritmo PageRank (“The Anatomy of a Large-Scale Hypertextual Web Search Engine”), alma y corazón de Google. Revise aunque solamente sea el resumen ( Abstract ) del mismo. Si el enlace no estuviera activo, repita la búsqueda usando el título del artículo.

Ahora bien, existen al parecer dos índices de PR: uno de uso interno, que Google no da a conocer y al que denominaremos PR Auténtico (PRA), y otro que se presenta a través de una barra de herramientas del propio Google (Google Toolbar).

Este PR al que denominaremos PR Externo (PRE) consiste en una escala de 0 a 10, de manera que un sitio con una puntuación de 0 indica que se trata de un sitio que no recibe ningún enlace, mientras que en el otro extremos, un sitio con una puntuación de 10 recibe miles o decenas de miles de enlaces y centenares de ellos proceden de sitios que a su vez poseen índices de PR muy altos.

Figura 2: El PageRank (en su modalidad externa) de una página se puede ver con la Toolbar de Google instalada en el navegador. Si pasamos el cursor sobre la barra indicará el valor numérico (p.e. 7/10).

A efectos prácticos parece que Google considera que una página comienza a ser importante solamente a partir de un PRE de 4. Para empresas pequeñas o medias, tener un sitio con un PRE de 5 o de 6 es un buen objetivo. Muchas páginas de sitios relativamente importantes como páginas de universidades, museos, o grandes corporaciones pueden llegar a tener un PRE de entre 6 y 8. Por último, muy pocas webs en todo el mundo pueden tener un PRE de 9 y aún menos (la propia Google entre ellas) un PRE de 10.

Actividad 5: Si no lo había hecho ya, descargue la Toolbar de Google (toolbar.google.com) y una vez instalada con la opción de PageRank habilitada compare los PageRanks de los sitios web de tres museos, de tres universidades o de su empresa y de dos empresas más de la competencia. Intente determinar si los PR de cada sitio se justifican por la calidad y el volumen de contenidos de cada sitio (recuerde que el PR es una medida automática y que no es infalible).

5. Conclusiones

El PageRank y otros algoritmos de posicionamiento no hacen más que confirmar una idea conceptualmente muy simple: una página quedará bien posicionada en función de la calidad (y volumen) su contenido. Lo único que ocurre es que los motores no pueden establecer una medida directa, de modo que lo hacen de forma indirecta: si una página es muy enlazada, es probable que tenga contenidos de calidad.

La moraleja por parte de los responsables de páginas web es la siguiente: si hemos realizado el esfuerzo continuado que requiere aportar contenidos de calidad a nuestro sitio, debemos verificar si tenemos un número de enlaces de entrada que permita visualizar este esfuerzo. De no ser así, deberemos tomar las medidas que se apuntan en otras unidades de este Máster vinculadas con el objetivo de conseguir enlaces de entrada a través, típicamente, de buenas campañas de posicionamiento.

6. Bibliografía

Baeza-Yates, R. “Minería web para mejorar sitios web” (conferencia). Barcelona: Usid 2007 Acceso: http://www.cobdc.org/usid/2007/pdf/ricardobaeza.pdf

Brin, S.; Page, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Stanford Univ., 2000. Acceso: http://infolab.stanford.edu/~backrub/google.html

Google. Tecnología de Google , 2007. Acceso: http://www.google.com/intl/es/corporate/tech.html

Kleinberg, J. “Authoritative sources in a hyperlinked environment”. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms , 1998 (versión extendida en: Journal of the ACM 46(1999).

Thelwall, M. Link Analysis: An Information Science Approach. Academic Press, 2004

Ties, D.; Davies, D. “Link Analysis” En: The Search Engine Marketing Kit. Melbourne: Sitepoint, 2007