Las matemáticas que hay detrás del algoritmo de Google

Pagerank es el algoritmo utilizado por Google para posicionar las páginas que muestra su motor de búsqueda. Esta es una prueba práctica de la utilidad de las matemáticas que se ven en el colegio o en el instituto, porque aquí hay mucho de matrices y de álgebra lineal.

Fue desarrollado en 1998 por Larry Page (de su apellido le viene el nombre) y por Sergey Brin en la universidad de Standford y lo que hace es medir cómo de importante es una página web a la hora de servirla en la búsqueda de un usuario.

Realmente lo que vamos a ver es la versión «sencilla» de cómo Google muestra ordenadas las páginas que nos presenta cuando hacemos una búsqueda, ya que tiene en cuenta muchas otras cosas como nuestra geolocalización, búsquedas nuestras anteriores, etc.  Google utiliza toda la información que de nosotros disponga.

Veamos «matemáticamente» en qué consiste el algoritmo a través de un ejemplo:

Tenemos varias páginas enlazadas unas con otras y lo que queremos saber es cuales son las más relevantes para mostrarlas las primeras.

Para darle un peso o una relevancia a cada página, el algoritmo tiene en cuenta dos cosas: el número de páginas que la enlazan y además cómo de relevantes son las páginas que la enlazan.

Cada página tiene su relevancia y lo que hace es repartirla entre las páginas a las que enlaza. Suponemos que al principio todas las páginas tienen la misma relevancia igual a 1.

Entre las matemáticas que hay detrás de este algoritmo, aparte de los sistemas de ecuaciones lineales que luego veremos, esta que se basa también en las Cadenas de Markov.


Definimos una cadena de Markov como un modelo matemático que describe un experimento que se realiza muchas veces consecutivas  de la misma manera y en donde el resultado de un experimento afecta al resultado del próximo experimento, e decir, el resultado de un experimento depende únicamente del resultado del experimento anterior.

Como hemos dicho, todas las páginas empiezan teniendo relevancia 1, es decir, siendo todas igual de relevantes y reparten su relevancia o autoridad entre las páginas a las que enlaza. La idea es que si repetimos sucesivamente este mismo proceso, al final  llegamos a un punto en el que la relevancia de las páginas se termina estabilizando, y este es el punto que nos da la relevancia o importancia de ellas.

Veámoslo con un ejemplo:

En este grafo que representa cuatro páginas web que se enlazan unas con otras, vemos como la página 1 entrega toda su relevancia a la página 2.

La página 2 entrega $\frac{1}{2}$ de su relevancia a la página 3 y otro $\frac{1}{2}$  a la página 4.

O dicho de otra forma utilizando matrices y fijándonos en el rectángulo azul:

La página 1 no recibe nada (0) de las páginas 1 (claro, es ella misma) y 2, pero recibe $\frac{1}{2}$  de relevancia de la página 3 y otro $\frac{1}{2}$ de la página 4.

La página 2 recibe 1 de relevancia de la página 1 y recibe $\frac{1}{2}$ de la página 4.

Así, al final tenemos que

Relevancia de la página 1:  $\frac{1}{2} + \frac{1}{2}=1$

Relevancia de la página 2:  $1+\frac{1}{2}=\frac{3}{2}$

Relevancia de la página 3: $\frac{1}{2}$

Relevancia de la página 4: $\frac{1}{2}+\frac{1}{2}=1$

Ahora el proceso habría que repetirlo, es decir, siguiendo el grafo, cada página volvería a ceder su relevancia (que ahora ya no es 1) entre las páginas a las que enlaza. Repitiendo y repitiendo esto al final el resultado acaba estabilizándose llegando  a un punto de equilibrio que marca la relevancia de cada página.

Pero es que esto también podemos verlo de otra forma, lo podemos ver como un Sistema de Ecuaciones Lineales.

La relevancia de la página 1 es el resultado de sumar $\frac{1}{2}$ de la relevancia de la página 3 + $\frac{1}{2}$  de  la relevancia de la página 4, es decir:

$x_1=\frac{1}{2}x_3 +\frac{1}{2} x_4$

análogamente

$x_2=x_1 + \frac{1}{2} x_4$

$x_3=\frac{1}{2} x_2$

$x_4=\frac{1}{2} x_2 + \frac{1}{2} x_3$

Tendríamos que resolver este sistema de ecuaciones para conocer la relevancia de cada página.

Aunque sabemos resolver sistemas de ecuaciones lineales, yo he utilizado la web matrixcalc obteniendo como resultado que esto es un sistema de ecuaciones compatible indeterminado -adminte un conjunto infinito de soluciones- pero todas de la forma:

$x_1= \frac{5}{6} x_4$

$x_2= \frac{4}{3} x_4$

$x_3= \frac{2}{3} x_4$

$x_4 = x_4$

dando $x_4=1$ obtenemos las siguientes relevancias para las páginas de nuestro ejemplo:

$ \text{página 2 } (\frac{4}{3}  ) >\text{página 4 } (1)> \text{página 1 } ( \frac{5}{6} )  > \text{página 3 } (\frac{2}{3} ) $

 

The following two tabs change content below.

Juanjo Bravo

Matemático. Entusiasta de las Matemáticas y de las TIC. Trabajo en el departamento de informática de un banco.