Desde hace unos años, Google se ha con­ver­ti­do en el busca­dor están­dar en la red. Uno de sus secre­tos es el algo­rit­mo PageRank,que com­bi­na la teoría espec­tral de gra­fos con álge­bra line­al.

Un poco de historia

Google fue cre­a­do en 1998 por Sergei Brin y Lawrence Page en la Universidad de Stanford. El nom­b­re es una vari­a­ción sob­re el tér­mi­no goo­gol, es decir, el núme­ro 10100, haci­en­do refe­ren­cia al gran volu­men de datos con el que el pro­grama tie­ne que tra­ba­jar. Según la pági­na de Google, ati­en­de a más de 250 mil­lo­nes de con­sul­tas dia­ri­as. El pro­ble­ma con todos estos datos es el sigu­i­en­te: ¿en qué orden mostra­mos estos datos? ¿Cúales son los resul­ta­dos más inte­re­san­tes para el públi­co? Necesitamos cier­to orden de asig­na­ción de bús­que­da.

Hoy por hoy, Google uti­li­za dos cri­te­ri­os de bús­que­da bási­cos. El for­ma­to de la palab­ra busca­da en las distin­tas webs, depen­di­en­do de como de impor­tan­cia se le de a esta palab­ra. Si se buscan vari­as palabras, se da pri­o­ri­dad a las ent­ra­das en las que las palabras apa­rezcan más cer­ca.

Modelo de ordenación de Google

Sean Pi las pági­nas web y Xi la impor­tan­cia:

Paso 1:

Primer paso. Con un gra­fo ori­en­ta­do o diri­gi­do G. Cada sitio de la red es un vér­tice, y hay una aris­ta ent­re P_i y P_j si des­de la pági­na Pi hay un enla­ce a la pági­na Pj . Construimos la traspues­ta de la matriz de ady­a­cen­cia, es decir, la matriz M = (mij) don­de mij es el núme­ro de enla­ces que van de Pj a Pi (si no hay enla­ces de Pj a Pi enton­ces mij = 0 y supondre­mos que una pági­na siem­p­re se enla­za a sí mis­ma, por lo que los ele­men­tos dia­go­na­les valen 1).

Paso 2:
La importancia de una página Pi será mayor en función de dos factores: que sea probable llegar a Pi desde otras páginas (como enlaces externos) y que las citas a Pi sean de páginas con gran importancia. El modelo asigna un valor de importancia xi a una página (vértice) Pi en función de lo probable que sea llegar a ella. Se considera que una parte de esta probabilidad es uniforme (todas las páginas tendrían la misma probabilidad de ser visitadas aleatoriamente).  Esta sería 1/N, siendo N el número de páginas en Internet. La otra parte de esta probabilidad se considera proporcional a la suma de las importancias de los vértices de los que salen aristas confluyentes en Pi o, lo que es lo mismo, de las páginas que enlazan con Pi. La proporcionalidad vendrá dada en función de los enlaces que salgan de cada página. La importancia de la página Pi se expresará mediante ∑(mij/kj)*xj; donde kj es el número de enlaces que salen de la página Pj . Esta expresión es la coordenada i–ésima del vector M’x , donde M’ es la matriz que tiene por elementos mij’=mij/kj. Al dividir por kj estamos ponderando el hecho de que no es lo mismo estar enlazado desde una página selectiva que solo tiene un enlace que estarlo desde una página promiscua que tiene muchos. Cabe destacar que todos los mij/kj suman 1. La importancia de una página Pi se define como Xi = (1-d)/N + d*∑(mij/kj)*xj, para algún d entre 0 y 1.
Conclusión

Vectorialmente, tene­mos la igu­al­dad x = (((1-d)//N)*1N +d*M’)*x, don­de 1N es una matriz de NxN don­de todos sus ele­men­tos son 1.

Resumiendo, el algo­rit­mo PageRank busca un vector xi en la matriz   A= ((1-d)/N)*1N d*M’.


Deja un comentario

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

Esta página web utiliza cookies para mejorar la experiencia de uso. El uso continuado de la página implica la aceptación de la política de cookies.
ACEPTAR

Aviso de cookies