PageRank

De Viquipèdia
Dreceres ràpides: navegació, cerca

PageRank és l'algorisme que utilitza Google per determinar la posició d'una pàgina web a l'hora de fer una consulta mitjançant el seu motor de cerca. Aquest mètode mesura el seu grau d'importància de forma numèrica i permet situar els resultats més fiables en primer lloc. Alhora, reflecteix la probabilitat que hi ha de que un usuari que navega a través d'enllaços de forma aleatòria arribi a una pàgina web concreta.

Descripció[modifica | modifica el codi]

Aquesta tecnologia realitza una mesura objectiva de la rellevància que tenen les pàgines web dins la xarxa i es basa a assignar un valor a cada web en funció del nombre d'enllaços d'altres pàgines que l'apunten, interpretant un vincle de la pàgina A a la pàgina B com un vot que rep la pàgina B per part de la pàgina A. A més, PageRank també considera el prestigi de cada pàgina que emet un vot, ja que als vots que provenen de determinades pàgines se'ls atorga un valor major, incrementant així el valor de la pàgina vinculada. D'aquesta manera i juntament amb altres criteris no públics, les pàgines importants reben una valoració més alta i apareixen en la part superior dels resultats de cerca.

PageRank és la part més coneguda del gran sistema de classificació de Google i destaca entre models de llenguatge (que estudia com formular les frases, sinònims, errors ortogràfics, etc.), models de consulta (com els usuaris utilitzem aquest llenguatge actualment), models de temps (algunes consultes són millor respostes gràcies a una web creada fa dos dies que una molt més antiga) i models personalitzats (no tothom busca o vol el mateix), entre d'altres.

Història[modifica | modifica el codi]

PageRank va estar desenvolupat a la Universitat de Standford per Larry Page i més tard Sergey Brin va sumar-se al treball a l'estar realitzant un projecte d'investigació sobre els motors de cerca. El primer document que parla sobre PageRank i el prototip inicial del motor de cerca de Google va ser publicat el 1998. Poc després, Page i Brin van fundar Google Inc.

Aquest algorisme ha estat influenciat per l'anàlisi de citacions (desenvolupat per Eugene Garfield en la dècada dels 50) i per la primera tècnica que va permetre introduir l'anàlisi de xarxes als motors de cerca, anomenat Hyper Search i desenvolupada per Massimo Marchiori.

Algorisme[modifica | modifica el codi]

PageRank representa la probabilitat que una persona arribi a una pàgina en particular fent clic sobre enllaços de forma totalment aleatòria. Aquest procediment es podria entendre com una cadena de Markov en què els estats són les pàgines, i les transicions són igualment probables i són els vincles entre les pàgines. Aquesta probabilitat està expressada amb un valor numèric entre 0 i 1. Així que un PageRank de 0.5 significa que existeix un 50% de probabilitat que l'usuari sigui adreçat a una web en concret si navega clicant aleatòriament. L'algorisme inicial el podem trobar al document original on els seus creadors van presentar el prototip del que ara és Google: "The Anatomy of a Large-Scale Hypertextual Web Search Engine".[1] Una alternativa a l'algorisme PageRank propost per Jon Kleinberg, és l'algorisme HITS.

Algorisme simplificat[modifica | modifica el codi]

Figura 2: El PageRank d'una pàgina web s'obté en funció del nombre d'enllaços d'altres webs que l'apunten, el valor d'aquestes i altres criteris no revelats.

Per entendre el complex funcionament d'aquest algorisme proposarem un exemple suposant que tan sols existissin 4 pàgines web a la xarxa: A, B, C i D (veure figura 2).

1) Contribucions inicials:

En aquest cas sabem que la probabilitat inicial de que un usuari acabi visitant una de les 4 webs és 1/4=0.25 (PageRank(PR)=0.25).

2) Importància dels enllaços de sortida de cada pàgina:

Si només hi haguessin els enllaços de les pàgines B, C i D cap a la pàgina A, li atorgarien un valor de PageRank de 0.25 cada una d'elles.

PR(A)= PR(B) + PR(C) + PR(D) = 0.75\,


Veiem també que B té un enllaç cap a C i que D enllaça a totes les altres pàgines. Així, tenim que B dóna un vot amb valor de 0.125 a la pàgina A i un vot valorat en 0.125 a C. Per últim sabem que D aporta 0.083 al PageRank de A.

PR(A)=\frac{PR(B)}{2} + \frac{PR(C)}{1} + \frac{PR(D)}{3} = 0.125 + 0.25 + 0.083 = 45.83% \,


De la mateixa manera obtenim la resta de valors de PageRank:

PR(B)= 16.67%\,
PR(C)= 29.17%\,
PR(D)= 8.33%\,


Per tant, el valor d'una pàgina x qualsevol es pot expressar com:

PR(x) = \sum_{y \in E} \frac{PR(y)}{L(y)},

On:

  • PR(x) és el PageRank de la pàgina x
  • PR(y) són els valors de PageRank que tenen cadascuna de les pàgines y que enllacen a x,
  • L(y) és el nombre total d'enllaços de sortida de la pàgina y (siguin o no cap a x);


3) Interpretació dels valors obtinguts:

La web B té un valor més alt que C, encara que té menys enllaços que l'apunten; això és degut al fet que la importància d'aquest enllaç és major. Un altre detall important és saber que A, encara que no té cap vincle de sortida, equival a tenir enllaços a totes les webs de la xarxa, ja que obliga a l'usuari a obrir una pàgina nova voluntàriament i la probabilitat d'accedir-hi a una en concret és la mateixa per totes.

Algorisme amb factor d'amortiment[modifica | modifica el codi]

Pot donar-se el cas que l'usuari deixi de prémer enllaços al navegar per la xarxa i passi a escriure una URL directament en la barra d'adreces o prema un dels seus marcadors del navegador. Per aquest motiu s'afegeix aquest factor d'amortiment, que tindrà en compte aquesta possibilitat.

PR(x) = (1-d) + d * \sum_{y=1}^n {PR(y) \over L(y)}

On:

  • d és un factor d'amortiment que indica la probabilitat que l'usuari continuï navegant mitjançant els enllaços i que té un valor entre 0 i 1 (segons alguns experts sol valdre 0.85)
  • 1-d és la probabilitat que l'usuari deixi de prémer els enllaços

D'aquesta manera s'obtenen resultats més acurats i s'aconsegueix que les pàgines que no tenen enllaços a cap altra no surtin especialment beneficiades.

Opció rel="nofollow"[modifica | modifica el codi]

En gener de 2005 es va implementar el nou atribut 'rel=nofollow' en els enllaços amb l'objectiu inicial de que els enllaços no inserits voluntàriament pels propietaris de la web no fossin tinguts en compte pels cercadors i també per evitar l'spam en altres llocs web.

Curiositats[modifica | modifica el codi]

  • PageRank és una marca registrada i patentada per Google el 9 de gener de 1999 i el seu nom original és "Method for node ranking in a linked database".
  • Segons afirmen alguns experts, el valor de PageRank és inversament proporcional a com de concreta és una cerca. És a dir, segons aquesta teoria, mentre més concreta sigui la nostra consulta, menys valor de PageRank tindrà la pàgina que conté el que cerquem (menys probabilitat d'acabar visitant la web en qüestió).
  • El PageRank és un valor numèric que va del 0 al 10 en una escala logarítmica. Això vol dir que és molt més difícil pujar de 6 a 7 que de 2 a 3.
  • El text dels enllaços que ens posen cap a la nostra web té molta importància.

Referències[modifica | modifica el codi]

  1. "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (en anglès)

Vegeu també[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: PageRank