Googleren PageRank eta matematikak

(OHARRA: sustatura bidali dut artikulu hau, ea publikatzen didaten.)

Atzo Pablo Fernández Gallardoren hitzaldi baten egon  nintzen. Saiatuko naiz ahalik eta ondoen esplikatzen han ikasi nuena... Hala pues!

Gaur egun internet erabiltzaile kopuru handia, gure artean behintzat, google erabiltzen du bere bilaketak egiteko.

Zergatik da google jaun eta jabe? Bi arrazoi nagusiki: azkarra delako (trufaz dino zenbat milisegundo kostatu zaion) eta nahi duguna
lehenengo emaitzetan ematen digulako. Portzentai handi batean, behintzat. Gutxitan pasatzen da bilatzen duguna lehenengo horrialdean ez dagoela. Horrez gain, "baietz lehenengoan!" botoia dauka. Batzutan Bilbokoa dirudi...

Arrakasta honen ardura galdera batean baino ez dago oinarritua:

Zein ordenetan erakutsi behar ditut bilaketaren emaitzak?

Eta galdera  hau galdera matematikoa baino ez da...

Hau erantzuteko antolakuntzarako irizpidea behar dugu. Horri webak P1, P2... Pn badira, bakoitzari bere garrantzia eman behar diogu. Demagun 0 eta 1 arteko baloreak direla.

Demagun Interneteko errolda eginten dugula, ta horri bakoitzari bere garrantzia emanez. Behin kontsulta bat eginda, garrantziari buruz
emango genituzke emaitzak. Erreza ezta? Garrantzi hori baino ez dugu kalkulatu behar. Goazen ba.

(OHARRA: beste kriterioak ere garrantzitsuak dira, hau da, bi hitz bilatzen baditugu ez da berdina elkarrekin egotea ala urruti, edo izenburuan egotea, edo horrialdearen azkenengo partean... Suposatuko dugu arazo hau konponduta daukagula)

Azken finean internet grafo bat bezala deskriba dezakegu. Horrialde web bakoitza erpin bat da, eta ertz bakoitza norabidedun esteka bat. Buruan irudia eginda daukazue, ezta?

Matematikoki egoera hau matrize bat bezala jarri dezakegu. Zutabe eta lerro bakoitza Pn bezala etiketatuko dugu, ta matrizearen kontenua honela: Pi-tik Pj-ra esteka badago 1 jarriko dugu, bestela 0 bat. Pj zutabea zenbatuko bagenu, Pj-tik irteten diren esteka guztien kopurua eukiko genuke. Ta lerro bakoitzeko baloreak bilatuz, zenbat esteka dauden gure webgunera apuntatzen.

Lehenengo hurbilketa baten esan dezakegu zenbat eta esteka gehiago gure gebgunera, orduan eta inportanteagoak garela. Ez dago gaizki, baina ez da berdina amazon.com-ek nire webgunera esteka eduki, edo www.blogak.com/zerobat.

Beraz, bigarren hurbilketa baten esango dugu gure garrantzia kalkulatzen dela webgune batean sartzen diren esteka guztien garrantzia gehituz. "The washington post"i baino ez diogu ziria sartu behar. ;-)

Hau idatzi daiteke ekuazio matematikoak bezala, eta azken finean, era matrizialean:


x garrantzien bektorea da, M garrantzien bektorea. Beraz garrantzien konponbidea ekuazio honen emaitza izango da:
Mx  = Lx
L proportzionalitate konstante bat izanda. Beraz arazo hau autobektore eta autobalioen arazoa da.

Bestalde, demagun surflari aleatorioa bat daukagula grafo hortatik surfeatzen, eta ertz bat edo beste hartuko du aleatorioki. Internet
osotik pasa dezan, gaitasun majiko bat ere emango diogu, batazbesteko nahi dugun ehunekoan teletrasportatu daiteke (isolatutako internet aldetan ere sar dezan).

Surflari honi esker, Mx=Lx-i esker eta Perron - Frobenius teoremari esker edukiko dugu gure emaitza. Azken finean, Ordenagailu bati eman behar dizkiogu metrize handi bat (milioika lerro eta zutabekin), nahi dugun bektore aleatorioa (beste hainbeste lerrokin), eta hamar aldiz!!!!! biderketa bat eginez edukiko dugu gure emaitza.

Gure Linux instalatuta daukan etxeko PlayStation 3arekin ezin izango dugu egin, baina zerbitzari pilo batekin eta ordu batzutan edukiko genuke gure garrantzia kalkulatuta.

Arazo konplexu, itzel, hartu ezina, azkenean ordu batzuetako arazo matematikoan bihurtu dugu.

Ta nitaz fidatzen ez bazarete (matematikoa ez naiz eta), hemen daukazue dokumentu originala:
http://www.uam.es/personal_pdi/ciencias/gallardo/fernandez1.pdf

Beste faktoreak ere badaude, ez pentsa, PageRank hori aldatzeko, baina arazoaren alderik handiena konponduta dago honela, gero afinatu baino ez da egin behar.