Recuerdo que al principio de internet (parezco el abuelo cebolleta) uno navegaba a través de la búsqueda de enlaces. Conocías la dirección de una página, la tecleabas en el nabegador web e ibas a ella. En las páginas era habitual enlazar con otras páginas con temáticas similares y tener un apartado de “enlaces de interés”. Posteriomente aparecieron portales a modo de directorio, donde se mostraban las páginas web por temáticas y finalmente se desarrollaron los motores de búsqueda, que eran programas que iban recorriendo internet buscando y almacenando información y direcciones. Y aquí es donde Google se posicionó por encima de todos los demás.
Una de las mejoras que planteó el motor de búsqueda de Google era su algoritmo de priorización de páginas, conocido como Page Rank. Éste algoritmo fue diseñado por Larry Page como ejercicio de su postgrado en la Universidad de Stanford. La fórmula del algoritmo es:
Su fórmula es la siguiente:
PA (A) es el page rank de la página «A».
d es el factor de amortiguación con un valor entre 0 y 1.
PR (i) son los valores de pagerank de cada una de los sitios web que enlazan a «A».
#C (i) es igual al número de enlaces salientes de la página que ha enlazado.
Este algoritmo funciona así. Si suponemos una red como la siguiente formada por varias páginas, en nuestro caso 5 páginas. Cada página enlaza a las otras según el siguiente grafo. Las flechas indican que hay un link de una página a la otra.
El algoritmo se basa en que las páginas importantes tienen mucha relevancia y que por tanto, las paginas que son enlazadas por ellas serán también relevantes. Es como cuando un amigo que sabe mucho de un tema te recomienda a otro para que te solucione algo. Vas a creer que esa tercera persona tiene que ser relevante para cuando te lo ha recomendado tu amigo relevante.
Pues bien. Según eso, cada página reparte su relevancia a partes iguales entre las diferentes páginas a las que enlaza. Quedando el grafo de esta forma:
Así, si partimos que en un principio todas las páginas son igual de relevantes, démosles el valor de 1, al principio:
- La página A reparte 1/2 a las páginas A y B
- La página B reparte 1/3 a las páginas A C y E
- La página C reparte 1 a la página D
- La página D no reparte nada
- La página E reparte 1/4 a las páginas A B C D
Según esto, la nueva relevancia de las páginas será:
- A=1/3*B+1/4*E=7/12
- B=1/2*A+1/4*E=3/4
- C=1/3*B+1/4*E=7/12
- D=1/2*A+1*C+1/4*E=7/4
- E=1/3*B=1/3
Al cambiar la relevancia, tendríamos que volver a hacer la operación hasta que los resultados se fueran estabilizando.
Pero si nos damos cuenta, aquí tenemos un problema. La página D no enlaza con ninguna, por lo cual no reparte su relevancia. Debido a ello, en cada iteracción, la suma de las relevancias disminuye desde el valor 5 inicia (1 por cada página), por lo que no se estabilizaría. Para ello hay que hacer un pequeño ajuste como propone este artículo. Se trata de crear enlaces “virtuales” desde la página D a todas las demás (incluida ella misma) repartiendo 1/5 a cada una, quedando de la siguiente forma:
- A=1/3*B+1/5*D+1/4*E=47/60
- B=1/2*A+1/5*D+1/4*E=19/20
- C=1/3*B+1/5*D+1/4*E=47/60
- D=1/2*A+1*C+1/5*D+1/4*E=39/20
- E=1/3*B+1/5*D=8/15
Que sí que suma 5.
Para calcular el valor final del Page Rank se puede resolver de varias maneras, por medio de matrices, por medio de álgebra lineal, pero vamos a hacerlo a través de continuar las interacciones y lo vamos a hacer usando un programa en python que he creado para esto.
No soy programador profesional, así que supongo que habrá mejores maneras de resolver algunas de las cosas que he hecho, pero al menos funciona.
Os lo explico incluyendo también comentarios (#) en el código.
Primero defino las variables:
# En la variable links introduzco las parejas de inicio y final de un enlace.
links=[['A','B'],['A','D'],['B','A'],['B','C'],['B','E'],['C','D'],['E','A'],['E','B'],['E','C'],['E','D']]
#Luego defino las variables que voy a usar
nodo={} # defino esta variable como diccionario
intercambio=[] # defino esta variable como lista
pagerank={} # defino esta variable como diccionario
nuevo_pagerank={} # defino esta variable como diccionario
reparto={} # defino esta variable como diccionario
relevancia_inicial = 1.0 # Defino la relevancia inicial de cada nodo en 1
Luego creo una función que de la lista de enlaces (links) me lo reparte en dos variables, una que me guarda los repartos que recibe cada nodo y otra que me guarda el reparto que hace cada nodo.
def evaluanodosycalculareparto(): # Defino la función para poder llamarla en varias ocasiones.
for link in links:
nodo[link[1]]=[] # Defino las variables como listas
reparto[link[1]]=0 # Pongo a cero los repartos
# En este bucle voy ordenando para que al final tenga una variable en la que por cada nodo de destino, me señale cuáles son los nodos de origen
for link in links: # Para cada enlace dentro del conjunto de enlaces...
intercambio=nodo[link[1]] # ...rescato los nodo de origen que se han tomado hasta ese momento y lo meto en la variable intercambio
intercambio.append(link[0]) # ...añado el nuevo nodo de origen a los anteriores.
nodo[link[1]]=intercambio # ...y los incluyo.
reparto[link[0]]=reparto[link[0]]+1 # incremento el reparto del nodo de origen correspondiente y lo guardo en la variable reparto.
evaluanodosycalculareparto() # mando ejecutar la función.
En nuestro caso la variable nodo queda: {‘A’: [‘B’, ‘E’], ‘B’: [‘A’, ‘E’], ‘C’: [‘B’, ‘E’], ‘D’: [‘A’, ‘C’, ‘E’], ‘E’: [‘B’]}, es decir A recibe repartos de B y E. B recibe repartos de A y E …
Y la variable reparto queda: {‘A’: 2, ‘B’: 3, ‘C’: 1, ‘D’: 0, ‘E’: 4} es decir, A reparte a 2 nodos, B reparte a 3 nodos…
Como hemos indicado antes, el nodo D no da reparto, por lo que vamos a crear los enlaces virtuales con el siguiente código:
for nod in reparto: # Para cada nodo que hay en la variable reparto...
if reparto[nod]==0: # ...compruebo si su reparto es cero, y si eso pasa...
for todos in reparto: # ...hago un repaso por todos los nodos...
links.append([nod,todos]) # ...y creo un enlace entre el nodo elegido y todos los demás. Añadiéndolos a la lista de enlaces.
evaluanodosycalculareparto() # Y vuelvo a evaluar los nodos y calcular el reparto.
De esta nueva forma, tras este nuevo reparto en nuestro caso quedaría:
La variable nodos: {‘A’: [‘B’, ‘E’, ‘D’], ‘B’: [‘A’, ‘E’, ‘D’], ‘C’: [‘B’, ‘E’, ‘D’], ‘D’: [‘A’, ‘C’, ‘E’, ‘D’], ‘E’: [‘B’, ‘D’]}
La variable repartos: {‘A’: 2, ‘B’: 3, ‘C’: 1, ‘D’: 5, ‘E’: 4}
Seguimos. Las siguientes líneas me asignan a la variable pagerank (dónde se guarda la relevancia de cada nodo) el valor inicial de 1 que habíamos definido para cada uno,
for n in nodo:
pagerank[n]=relevancia_inicial # asigna la relevancia inicial fijada a cada nodo.
nuevo_pagerank[n]=0 # esta es una variable que usaremos para calcular el Page Rank en cada interacción.
Y ahora es donde hacemos las interacciones de cálculo, he definido que vaya repitiendo la secuencia hasta que la diferencia entre los Page Rank calculados sea menor de una tolerancia definida, en este caso de 0.00000001 (puedes modificarlo a la que desees):
iteraccion = 0 # pongo a cero el contador que me señalará las iteracciones que se hacen.
while True: # Bucle infinito
for n in nodo: # Para cada nodo...
for rep in nodo[n]: # ...tomo cada uno de los nodos que lo enlazan...
nuevo_pagerank[n]=nuevo_pagerank[n]+pagerank[rep]/reparto[rep] # .. y calculo el nuevo pagerank sumando su pagerank dividido entre su reparto.
# Una vez hecho el cálculo vuelvo a repasar todos los nodos y les asigno la nueva Page Rank calculada
for n in nodo:
tolerancia = pagerank[n]-nuevo_pagerank[n] # Primero calculo la diferencia entre la Page Rank anterior y la nueva.
pagerank[n]=nuevo_pagerank[n] # Asigno al nodo la nueva Page Rank como Pager Rank oficial
nuevo_pagerank[n]=0 # Pongo a cero la variable para una posterior iteracción.
iteraccion +=1 # pongo un contador para saber cuántas iteracciones ha hecho el algoritmo.
print ("iteracción: "+str(iteraccion)+str(sorted(pagerank.items()))) # Imprimo el Page Rank de cada nodo. Ordenado alfabeticamente.
if abs(tolerancia) <= 0.00000001: break # Si el valor absoluto de la tolerancia es menor que el señalado, salgo del bucle y del programa.
Al final del artículo tenéis el código completo.
Ejecutando el programa nos sale el siguiente valor de Page Rank realizado en 20 iteracciones:
(‘A’, 0.8264462826698602), (‘B’, 0.9297520643475995), (‘C’, 0.8264462826698602), (‘D’, 1.756198341290689), (‘E’, 0.6611570290219916)
La página D sería la más relevante, ya que es la que más visitas recibe, mientras que la E es la que menos, a pesar de enlazar a muchas.
Que si lo sumáis da un valor de 5, es decir, se mantiene la relevancia de todo el conjunto.
Podemos comparar el cálculo con el de otras personas que lo han resuelto de forma diferente, como en las siguientes páginas:
- Como el vídeo del canal Derivando de Eduardo Sáenz de Cabezón que utiliza álgebra lineal. En este caso habría que modificar la variable
GeSHi Error: GeSHi could not find the language text (using path /home/kyokanes/public_html/wp-content/plugins/igsyntax-hiliter/classes/geshi/) (code 2) - O en esta entrada de Arpa Sandan donde también propone el cálculo en excell y python de una manera diferente, usando un módulo para la gestión de nodos. En este caso, la variable Links sería:
y el reparto inicial que hace es de 0.2 en vez de 1, por lo que habría que cambiar la línea
GeSHi Error: GeSHi could not find the language text (using path /home/kyokanes/public_html/wp-content/plugins/igsyntax-hiliter/classes/geshi/) (code 2)
GeSHi Error: GeSHi could not find the language text (using path /home/kyokanes/public_html/wp-content/plugins/igsyntax-hiliter/classes/geshi/) (code 2)
Este es una aproximación al algoritmo de Google, que como supondrás tiene otras características para priorizar ciertas búsquedas, compensar desviaciones o evitar que personas se aprovechen al conocer la fórmula. Este algoritmo se completa con otros de análisis de los términos de búsqueda, para conocer qué es lo que se quiere buscar a través de análisis del lenguaje, otros de búsqueda de coincidencias, que señalan las páginas que contienen el texto que buscas, otros de personalización de los resultados, que se fijan en tí, para darte lo que necesitas y otros que hacen análisis de la calidad de los resultados evaluandolos para ofrecer datos menos redundantes.
Y aquí te dejo el código completo, para que lo puedas probar. Puedes hacerlo simplemente copiándolo y pegándolo en este compilador online, u otros que hay en internet.
Y si cambias la primera línea por las siguientes, el programa te irá pidiendo los nodos, para que puedas probar con otras distribuciones.
Que te diviertas 🖖🏼😃
# Código que genera la variale links a partir de entradas por el teclado. Sustituir este código por la primera línea del programa
links=[]
while True:
de=input("Inicio del nodo: ")
if de == "":break # Cuando se pulsa enter sin introducir nada, considera que has terminado.
hasta=input("Fin del nodo: ")
links.append([de,hasta])
Código completo:
links=[['A','B'],['A','D'],['B','A'],['B','C'],['B','E'],['C','D'],['E','A'],['E','B'],['E','C'],['E','D']]
#Luego defino las variables que voy a usar
nodo={} # defino esta variable como diccionario
intercambio=[] # defino esta variable como lista
pagerank={} # defino esta variable como diccionario
nuevo_pagerank={} # defino esta variable como diccionario
reparto={} # defino esta variable como diccionario
relevancia_inicial = 1.0 # Defino la relevancia inicial de cada nodo en 1
def evaluanodosycalculareparto(): # Defino la función para poder llamarla en varias ocasiones.
for link in links:
nodo[link[1]]=[] # Defino las variables como listas
reparto[link[1]]=0 # Pongo a cero los repartos
# En este bucle voy ordenando para que al final tenga una variable en la que por cada nodo de destino, me señale cuáles son los nodos de origen
for link in links: # Para cada enlace dentro del conjunto de enlaces...
intercambio=nodo[link[1]] # ...rescato los nodo de origen que se han tomado hasta ese momento y lo meto en la variable intercambio
intercambio.append(link[0]) # ...añado el nuevo nodo de origen a los anteriores.
nodo[link[1]]=intercambio # ...y los incluyo.
reparto[link[0]]=reparto[link[0]]+1 # incremento el reparto del nodo de origen correspondiente y lo guardo en la variable reparto.
evaluanodosycalculareparto() # mando ejecutar la función.
for nod in reparto: # Para cada nodo que hay en la variable reparto...
if reparto[nod]==0: # ...compruebo si su reparto es cero, y si eso pasa...
for todos in reparto: # ...hago un repaso por todos los nodos...
links.append([nod,todos]) # ...y creo un enlace entre el nodo elegido y todos los demás. Añadiéndolos a la lista de enlaces.
evaluanodosycalculareparto() # Y vuelvo a evaluar los nodos y calcular el reparto.
for n in nodo:
pagerank[n]=relevancia_inicial # asigna la relevancia inicial fijada a cada nodo.
nuevo_pagerank[n]=0 # esta es una variable que usaremos para calcular el Page Rank en cada interacción.
iteraccion = 0 # pongo a cero el contador que me señalará las iteracciones que se hacen.
while True: # Bucle infinito
for n in nodo: # Para cada nodo...
for rep in nodo[n]: # ...tomo cada uno de los nodos que lo enlazan...
nuevo_pagerank[n]=nuevo_pagerank[n]+pagerank[rep]/reparto[rep] # .. y calculo el nuevo pagerank sumando su pagerank dividido entre su reparto.
# Una vez hecho el cálculo vuelvo a repasar todos los nodos y les asigno la nueva Page Rank calculada
for n in nodo:
tolerancia = pagerank[n]-nuevo_pagerank[n] # Primero calculo la diferencia entre la Page Rank anterior y la nueva.
pagerank[n]=nuevo_pagerank[n] # Asigno al nodo la nueva Page Rank como Pager Rank oficial
nuevo_pagerank[n]=0 # Pongo a cero la variable para una posterior iteracción.
iteraccion +=1 # pongo un contador para saber cuántas iteracciones ha hecho el algoritmo.
print ("interacción: "+str(iteraccion)+str(sorted(pagerank.items()))) # Imprimo el Page Rank de cada nodo. Ordenado alfabeticamente.
if abs(tolerancia) <= 0.00000001: break # Si el valor absoluto de la tolerancia es menor que el señalado, salgo del bucle y del programa.
0 comentarios