AMD Planet

di **Ibanez89** il 16 lug 2008, 21:08

sisi vediamo nel dettaglio

di **diegofio** il 02 ago 2008, 12:44

LEZIONE #9: PAGERANK

Pagerank è l'algoritmo utilizzato da Google per catalogare le pagine web secondo un punteggio (chiamato appunto pagerank) che ne identifica l'autorevolezza e la rilevanza. Ovviamente oltre al pagerank Google utilizza moltissimi altri (decine) indici, in modo tale da ridurre al minimo possibili "inquinamenti" volti ad aumentare il punteggio di una pagina rispetto ad altre in modo artificiale.

Come sappiamo la rete può essere vista come un grafo in cui i nodi rappresentano le singole pagine web e gli archi i collegamenti tra esse. Per vedere cos'è effettivamente 'sto Pagerank, facciamo un esempio considerando quattro pagine che chiameremo A B C D. Al passo iniziale in pagerank di ognuna è calcolabile come 1/4 ovvero si divide l'unità per il numero di pagine in questione, nel nostro caso quattro. Per ora abbiamo considerato un grafo con quattro nodi non collegati, ma adesso immaginiamo siano presenti i seguenti link:

B -> A
C -> A
D -> A

Il punteggio di A andrà ad aumentare visto che essendo linkata ora da tre pagine, essa viene ad acquistare quella autorevolezza (fornita da altri attraverso i link) che gli consentirà di scalare posizioni nella classifica: il pagerank di A quindi sarà dato dalla somma dei pagerank delle pagine che puntano ad essa, quindi PR(B) + PR(C) + PR (D).

Aumentiamo ora la complessità del grafo introducendo i seguenti link:

B -> C
D -> A
D -> B
D -> C

Ora il pagerank di B influisce meno su A perchè B oltre ad A punta anche a C. Allo stesso modo il pagerank di D influisce su A per un terzo del suo potenziale in quanto solo uno dei tre link di D punta ad A. Quindi PR(A) = PR(B)/2 + PR(C) + PR(D)/3.
La formula generale è molto semplice: per calcolare il pagerank di una generica pagina X basterà considerare tutte le pagine Yi che puntano ad X (possiedono un link verso X) e sommare il loro pagerank, che però andrà diviso di volta in volta per il numero totale di link contenuti nella singola pagina Yi considerata. Se conoscete le sommatorie:

PR(X) = sommatoria_(Yi -> X) [PR(Yi)/#LINK(Yi)]

Se riportate la formula all'esempio, vi accorgerete che è esattamente ciò che abbiamo fatto per calcolare il PR(A).

Il pagerank tuttavia considera nella sua formulazione un utente di internet che si trova in una pagina web: egli avrà una probabilità pari a d (valore detto "dumping factor") di seguire uno dei link presenti nella pagina e una probabilità pari a 1 - d (ricordo che d essendo una probabilità è un valore compreso tra 0 ed 1) di scrivere sulla barra degli indirizzi un url relativo ad una qualsiasi altra pagina del web potenzialmente del tutto scollegata dalla pagina che stava visualizzando in precedenza e di andarla a visitare. Questo fatto viene tenuto in considerazione mediante un fattore correttivo, nell'esempio precedente il pagerank di A diventa:

PR(A) = (1 - d)/N + d * (PR(B)/2 + PR(C) + PD(D)/3)

dove N è il numero totalre di pagine presenti nel grafo, quattro se ci riferiamo allo stesso esempio.
d nella realtà è un valore abbastanza vicino ad 1 percui il secondo addendo di PR(A) conta di più del primo: si tende perciò a dare maggiore importanza nel calcolo del punteggio di una pagina a quanto essa è puntata da altre pagine (dicasi autorevolezza) piuttosto che alla probabilità che essa venga scelta casualmente da un utente tra tutte le pagine del web.