Que es la patente Reasonable Surfer y como funciona matemáticamente

Buenas, en este artículo hablaremos de uno de los cambios de algoritmo de Google más importantes ya que es un cambio en el algoritmo que calcula el Pagerank y gracias al cuál no todos los enlaces valen lo mismo, así que vamos a empezar con la explicación de la patente Reasonable Surfer usando cadenas de Markov.

Algoritmo del Pagerank original

En el año 1999, Larry Page y Sergey Brin crearon el PageRank (El cual toma el nombre del apellido de uno de sus inventores) con el fin de ordenar los resultados de búsqueda que aparecían en su buscador (Google) de forma que las páginas web más relevantes ocuparan las primeras posiciones de los rankings.

El sistema del PageRank usado por Google está basado en el modelo Science Citation Index (SCI) elaborado por el Instituto para la Información Científica durante la década de 1950, el sistema servía para ordenar a los investigadores por relevancia según sus méritos, de forma que los investigadores con mayor relevancia recibieran mayores recursos y becas.

Lo que hace el algoritmo del PageRank es asignar autoridad a las webs en función de los enlaces que esta recibe, si recibe enlaces de webs con un alto PageRank es porque la web es importante y por tanto debe estar por encima de otras que reciben menos enlaces o los que reciben son de webs con poca autoridad, en definitiva, el PageRank mide la probabilidad de que un usuario acabe en una página web haciendo clic en enlaces de otras webs.

De forma matemática, eso lo podemos representar mediante una cadena de Markov, para explicarlo mejor lo haremos con un ejemplo usando el siguiente grafo:

Grafo Pagerank

Supongamos que cada nodo del grafo anterior representa una web, y los arcos entre ella representan enlaces, de forma que los arcos salientes son enlaces que apuntan a otra web y los arcos entrantes representan enlaces que llegan desde la otra web.

Según hemos definido el PageRank y aplicándolo a este ejemplo, podemos definir en una matriz las probabilidades de llegar a una web desde otra siguiendo los enlaces que aparecen en ella.

Matriz Pagerank

Para calcular el PageRank haremos uso de valores y vectores propios, ya que como sabemos que al realizar Axn=x siendo xn el vector resultado de realizar Ax (siendo x la matriz de transición) muchas veces, llegamos a que Ax=x

La teoría espectral de matrices dice que el vector x es un vector propio de P asociado al valor propio λ = 1, que es el mayor en valor absoluto.

Tras realizar los cálculos tenemos los siguientes valores de PageRank para cada una de las webs del ejemplo:

 

NodoPagerank Calculado
A0.14285711
B0.09523802
C0.19047627
D0.28571411
E0.28571449


 

El PageRank con la actualización “Reasonable Surfer”

En el año 2004 Google implementó una modificación en el algoritmo, por la cual no todos los enlaces tienen la misma importancia, si no que los enlaces “artificiales”, es decir los de perfiles sociales, firmas de foros y este tipo de enlaces tienen menos valor, en la siguiente imagen (extraída de la patente) vemos como lo primero que hace el algoritmo es determinar los aspectos positivos y negativos de los enlaces, a partir de ahí genera los vectores de probabilidad y determina el valor del enlace

Patente Reasonable Surfer

Para explicar esto un poco mejor vamos a usar el mismo grafo que en la demostración del Page Rank original, pero ahora tenemos dos tipos de enlaces, los de alta calidad (en azul) y los de baja calidad (en rojo)

Patente Reasonable Surfer Grafo

Cuya matriz asociada es:

Matriz Reasonable Surfer

Aplicando el mismo método que antes tenemos los siguientes valores de PageRank:

 

NodoPagerank Calculado
A0.16279070
B0.06976744
C0.20930233
D0.27906977
E0.27906977


Observamos diferencias entre los valores obtenidos y los del primer ejemplo, en el primer caso el PageRank de D y E eran iguales, y ahora lo siguen siendo, pero vemos que han disminuido un poco, vemos también que la web B ha perdido gran parte de su PageRank al aplicar este modelo y que la web que más beneficiada sale con este algoritmo es la A.

2 Comentarios
  1. septiembre 10, 2017
    • septiembre 12, 2017

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

¡Suscríbete!

Recibirás todas las novedades del blog y consejos exclusivos