PageRank

PageRank és l'algoritme 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. També indica la probabilitat que té un usuari, navegant de forma aleatòria amb enllaços, d'arribar a una pàgina concreta.

Descripció

Aquesta tecnologia realitza una mesura objectiva de la rellevància que tenen les pàgines web a la xarxa i es basa en 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 utilitzen 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

PageRank va ser desenvolupat a la Universitat Stanford per Larry Page. Més tard Sergey Brin es va afegir al projecte, ja que estava investigant 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 algoritme beu de l'anàlisi de citacions (desenvolupat per Eugene Garfield en la dècada dels 50) i per la primera tècnica d'anàlisi de xarxes als motors de cerca, Hyper Search, desenvolupada per Massimo Marchiori.

Algoritme

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". Una alternativa a l'algorisme PageRank propost per Jon Kleinberg, és l'algorisme HITS.

Algoritme simplificat

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 algoritme proposarem un exemple: suposem que només existeixen 4 pàgines web a la xarxa: A, B, C i D (vegeu figura 2).

1) Contribucions inicials:

En aquest cas sabem que la probabilitat inicial 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 hagués 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 dona un vot amb valor de 0.125 a la pàgina A i un vot valorat en 0.125 a C. Per acabar 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.

Algoritme amb factor d'amortiment

Pot donar-se el cas que l'usuari deixi de prémer enllaços al navegar per la xarxa i passi a escriure un 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"

En gener de 2005 es va implementar el nou atribut 'rel=nofollow' en els enllaços amb l'objectiu inicial 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

• 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".

• El nom de PageRank prové del seu creador, Larry Page (juntament amb Sergey Brin).

• Segons afirmen alguns experts, el valor de PageRank és inversament proporcional a com és de concreta 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.

Bibliografia

• Langville, Amy N.; Meyer, Carl D.. [0-691-12202 Google's PageRank and Beyond: The Science of Search Engine Rankings]. Princeton University Press, 2006. ISBN 0-691-12202-4. 
• Page, Lawrence; Brin, Sergey; Motwani, Rajeev y Winograd, Terry. The PageRank citation ranking: Bringing order to the Web, 1999. 
• Richardson, Matthew; Domingos, Pedro «The intelligent surfer: Probabilistic combination of link and content information in PageRank». Proceedings of Advances in Neural Information Processing Systems, 14, 2002.
• Cheng, Alice; Friedman, Eric J. «Manipulability of PageRank under Sybil Strategies». Proceedings of the First Workshop on the Economics of Networked Systems (NetEcon06).
• Altman, Alon; Tennenholtz, Moshe «Ranking Systems: The PageRank Axioms». Proceedings of the 6th ACM conference on Electronic commerce (EC-05). Arxivat 2008-05-30 a Wayback Machine.

Vegeu també

• Optimització per a motors de recerca
• Google bomb
• HITS

Enllaços externs

• The Anato
• my of a Large-Scale Hypertextual Web Search Engine: el prototip de Google.
• Tecnologia Google Arxivat 2012-05-09 a Wayback Machine. - Pàgina de Google on s'explica com s'utilitza aquesta tecnologia.
• Method for node ranking in a linked database Arxivat 2013-12-30 a Wayback Machine.: la patent originària de PageRank.