Matemáticas aplicadas

Buscar en Google

Des­de hace unos años, Goo­gle se ha con­ver­ti­do en el bus­ca­dor están­dar en la red. Uno de sus secre­tos es el algo­rit­mo Page­Rank, que com­bi­na la teo­ría espec­tral de gra­fos con álge­bra lineal.

Un poco de historia

Goo­gle fue crea­do en 1998 por Ser­gei Brin y Law­ren­ce Page en la Uni­ver­si­dad de Stan­ford. El nom­bre es una varia­ción sobre el tér­mino goo­gol, es decir, el núme­ro 10100, hacien­do refe­ren­cia al gran volu­men de datos con el que el pro­gra­ma tie­ne que tra­ba­jar. Según la pági­na de Goo­gle, atien­de a más de 250 millo­nes de con­sul­tas dia­rias. El pro­ble­ma con todos estos datos es el siguien­te: ¿en qué orden mos­tra­mos estos datos? ¿Cúa­les son los resul­ta­dos más intere­san­tes para el públi­co? Nece­si­ta­mos cier­to orden de asig­na­ción de bús­que­da.

Hoy por hoy, Goo­gle uti­li­za dos cri­te­rios de bús­que­da bási­cos. El for­ma­to de la pala­bra bus­ca­da en las dis­tin­tas webs, depen­dien­do de como de impor­tan­cia se le de a esta pala­bra. Si se bus­can varias pala­bras, se da prio­ri­dad a las entra­das en las que las pala­bras apa­rez­can 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:

Pri­mer paso. Con un gra­fo orien­ta­do o diri­gi­do G. Cada sitio de la red es un vér­ti­ce, y hay una aris­ta entre P_i y P_j si des­de la pági­na Pi hay un enla­ce a la pági­na Pj . Cons­trui­mos la tras­pues­ta de la matriz de adya­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 supon­dre­mos que una pági­na siem­pre 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

Vec­to­rial­men­te, tene­mos la igual­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.

Resu­mien­do, el algo­rit­mo Page­Rank bus­ca un vec­tor xi en la matriz   A= ((1‑d)/N)*1N d*M’.