Desvelando los secretos del PageRank
El buscador de Google es el motor de búsqueda más utilizado en la Web. El objetivo principal del buscador de Google es buscar texto en las páginas web, en lugar de otro tipo de datos. Fue desarrollado originalmente por dos estudiantes de la universidad de Stanford, Larry Page y Sergey Brin, en 1997.
En 2003, a 15 años de su creación, la compañía procesaba ya 100.000 millones de búsquedas por mes. Cada una de estas solicitudes viaja, en promedio, unos 2400 kilómetros en un cuarto de segundo, el tiempo que tarda en surgir la respuesta. Ese resultado emerge casi tan rápido como un parpadeo, de un total de 60 trillones de páginas web.
El término «gúgol» refiere a un número 1 seguido de 100 ceros, una forma matemática de expresar la misión del motor: «Organizar la información del mundo y hacerla universalmente accesible y útil».
El orden de los resultados de búsqueda (ghits, por Google hits) se basa en un rango de prioridad llamado «PageRank”. Veamos los todos los pasos previos hacia una búsqueda eficiente:
Rastreo: consta en localizar los contenidos de la Web y pasar el contenido a sistemas de indexado. Para ello se utiliza el software Googlebot que, recursivamente, lee una página web dada obteniendo los enlaces y planificando nuevas operaciones de rastreo.
Indexación, o indexado inverso: produce un índice de palabras que aparecen en páginas web y otros recursos textuales como documentos en varios formatos. No solo guarda la posición, también almacena otra información como el tamaño de fuente y capitalización. Utilizando este índice, se reduce el número de páginas candidatas de miles de millones a unas decenas de miles. La indexación también mantiene un índice de enlaces, llevando un seguimiento de qué páginas apuntan a una página web.
Clasificación, o algoritmo Page Rank: El algoritmo PageRank define el concepto de relevancia de la página web, y ayuda a clasificar las páginas que coincidan con una determinada cadena de búsqueda. Está basado en los sistemas de ranking de las publicaciones científicas, un artículo es importante si ha sido citado por otros colegas del área. El ranking en Google también tiene en cuenta factores relacionados con la proximidad de la búsqueda a las palabras clave de la página obtenidas en el indexado inverso.
“Formula time”: ¿Debemos? ¡Si, debemos!
El algoritmo calcula una puntuación recursiva de páginas, basado en la suma ponderada del PageRank de las páginas con enlaces a ellos. Entramos en los detalles matemáticos: si nombramos con xi el ranking de la página i, y la conectividad entre las paginas i y j con mij, de tal manera que mij=0 si no hay enlaces entre las paginas 1 si lo hay, entonces habrá que resolver, redoble de tambores…
Un problema de autovalores y autovectores
(sensación de misticismo religioso en l@s lector@s de letras, de terror y pura angustia entre ingenier@s, de interés puramente teórico entre matematic@s y fisic@s)
Tendremos pues que encontrar los autovectores x={x1,…,xn} y autovalores ‘lambda’, ese símbolo que multiplica las xi en la parte derecha de las ecuaciones.
Ahora a ver, al no ser que seas un matemático Indio aficionado al calculo mental, un estudiante occidental medio resuelve un problema a los autovalores con una matriz de orden 4 (eso es 4 filas y 4 columnas) como mucho, mientras aquí estamos hablando de una matriz de tamaño de orden decenas de miles: no podemos resolver el problema exactamente ni con algoritmos algebraicos aproximados, pues su complejidad computacional es muy elevada[1].
Entonces, ¿cómo abarcamos el problema? Entra en el escenario (otro redoble de tambores…
El surfista borracho, o aleatorio
Supongamos un surfista que navega por la red completamente al azar, porqué ese día volvió de juerga y se puso a tontear por el interné, de forma más elegante: en un cierto instante este individuo se encuentra en una página, entonces selecciona al azar alguna de las páginas que están conectadas desde donde está y salta a ella.
Matemáticamente, el individuo realiza lo que se llama un paseo aleatorio por la red. Ni es el número de veces que el surfista ha pasado por la pagina i, así que este se va incrementando durante su exploración. Después de unos cuantos pasos del surfista, el valor Ni dividido por el total de los pasos realizados en todas la red Ntot nos da una excelente aproximación de xi .
En la siguiente animación mostramos un ejemplo con 5 nodos: después de pocas decenas de iteraciones, ya obtendremos nuestro ranking bien aproximado:
El surfista borracho, aparte de ser rápido en proporcionarnos el ranking, tiene otras ventajas:
- Es robusto a cambios en las conexiones, porque la mayoría de las probabilidades se verán poco afectadas si los cambios son locales.
- Es fácilmente paralelizable, basta para ello tener varios surfistas moviéndose por la red de forma simultánea.
- Es fácil considerar casos en los que las probabilidades de visitar los vecinos desde un nodo no son uniformes, por lo que puede haber preferencia de visitas (si pensamos en páginas web, por ejemplo el tamaño y vistosidad de unos enlaces frente a otros).
- Se puede considerar la importancia de estructuras superiores a nodos simples, considerando las visitas provocadas por conjunto de nodos desde conjuntos de nodos.
El algoritmo actual
Además de PageRank, Google ha añadido muchos otros criterios no mencionados para determinar la clasificación de las páginas: hay más de 200 diferentes, cuyos detalles específicos se mantienen en secreto para permitirle a Google mantener una ventaja sobre sus competidores a nivel mundial, y entretanto PageRank juega un papel cada vez menor.
Como consecuencia ha surgido una gran industria de consultores informáticos para ayudar a los sitios web a aumentar su ranking en Google. Este campo, llamado optimización de motores de búsqueda (SEO en inglés), trata de discernir patrones en los listados de motores de búsqueda y luego desarrollar una metodología para mejorar la clasificación y atraer a más usuarios a los sitios de sus clientes.
Por ejemplo se puede afectar el algoritmo de relevancia de Google mediante la incorporación de las palabras claves en la página. Sin embargo, demasiadas repeticiones de la palabra clave causan que la página para buscar luzca sospechosa para el algoritmo de control Google que evita spam. Una lucha de estilo hacker entre muchos Davides frente al gran Gooooooliat que decidió, en 2016 no publicar ninguna información adicional con el fin de dificultar la creación de métodos artificiales de modificar los resultados.
[1] La Complejidad Computacional de un algoritmo es una estimación de los recursos requeridos, en términos de número de operaciones o tiempo computacionál, durante el cálculo para resolver un problema.