GOOGLERANK / ITA / COVER / pagerank-descrizione.html

PAGERANK™ DI GOOGLE

UN MODO FACILE DI COMPRENDERE IL FUNZIONAMENTO DEL PAGERANK™ E UNO PIU' COMPLESSO ED EMPIRICO.
INOLTRE UN'INTRODUZIONE AL TRUSTRANK COME ALGORITMO CAPACE DI ARGINARE IL WEBSPAM

Di seguito, la traduzione dell'intestazione del brevetto originale dell'algoritmo Pagerank depositato da Brin e Lawrence nel 1998

U.s Patent file # 6,285,999 ;
September 4, 2001

METHOD FOR NODE RANKING IN A LINKED DATABASE

Descrizione : Un metodo che assegna una classificazione di importanza a documenti contenuti in un archivio, come ad esempio ogni archivio che contenga citazioni e rimandi, il Web o tutti gli altri database ipermediali (intesi come archivi che possono rimandare a documenti collegati ad altri archivi o altre fonti. n.d.A) . Il valore assegnato ad un documento è calcolato partendo dal valore dei documenti che lo richiamano. Inoltre, la classificazione di un documento è calcolata prendendo in riferimento una costante che rappresenta la probabilità che un ricercatore all'interno del database salterà in maniera casuale da un documento all'altro. Il metodo è assai utile per implementare la qualità dei risultati di un motore di ricerca per archivi ipermediali come ad esempio il Web, all'interno del quale la qualità dei documenti è molto variabile.

Inventori:
Page; Lawrence (Stanford, CA)

Assegnatario:
The Board of Trustees of the Leland Stanford Junior University (Stanford, CA)

Appl. No.: 004827 ; Filed: January 9, 1998

PAGERANK™ : UN MODO FACILE DI COMPRENDERLO.

Google è attualmente tra i più avanzati spider di internet. Esso fa molto più che cercare e indicizzare pagine web. Google analizza la struttura dei collegamenti ipertestuali tra le pagine, utilizzando una tecnologia proprietaria denominata PAGERANK™ che sfrutta la struttura dei link all'interno di Internet come mappa stradale e strumento di organizzazione. Più pagine si collegano ad una data pagina, migliore sarà la classificazione (importanza) di questa pagina. Il Pagerank™ guarda inoltre un sito nella sua globalità; la classificazione delle sue pagine è proporzionata al numero di pagine che linkano ad esso.
Google quindi, non assegna una classificazione unicamente in base a quante volte una data parola chiave compare nel testo o nel codice del documento, ma anche in base alle caratteristiche uniche del documento stesso (le "variabili-di-pagina").

La presenza di una pagina tra i risultati delle ricerche sarà possibile solo se la pagina soddisfa totalmente la query dell'utente, sia

1) dal punto di vista dei contenuti della pagina
2) dal punto di vista della qualità dei link entranti della pagina (in inglese: inbound links N.d.A.).

IL CERCHIO DI RILEVANZA

La pagine dei R.E.M. (quella nel centro della grafica) riceve link in entrata da diverse -ma accomunate dallo stesso tema, o topic- pagine web. La pagina inoltre contiene collegamenti ad ulteriori fonti esterne.
Le pagine web che si trovano al centro di un cerchio di rilevanza sono decisamente preferite quando Google valuta e assegna un ranking ai documenti. Cfr. ALGORITMO HILLTOP

THE TOPIC SENSITIVE PAGERANK™

Teorizzato da Taher H. Haveliwala dell'Università di Stanford, è fondamentalmente una tecnologia che permette il raggruppamento di molte parole e frasi all'interno di aree tematiche (topics) . Applicata agli algoritmi dei motori di ricerca, sarebbe in grado di fornire all'utente risultati altamente dettagliati e coerenti.
Questa tecnologia non è implementata in Google.

PAGERANK™ : METODOLOGIA EMPIRICA ACCADEMICA

L'algoritmo originale denominato Pagerank™ è stato descritto da Lawrence Page e Sergey Brin (creatori di Google) in svariate pubblicazioni largamente disponibili e facimente reperibili su internet.

E' dato da:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

dove

· PR(A) è il PageRank della pagina A,
· PR(Ti) è il PageRank delle pagine Ti che linkano alla pagina A,
· C(Ti) è il numero di link verso altri siti (outbound) contenuti dalle pagine Ti e
· d è una costante matematica, qui utilizzata come "fattore di aggiustamento", che può essere fissata tra 0 e 1.

Per prima cosa , vediamo che il PageRank non classifica i siti internet nel loro insieme, ma viene determinato singolarmente per ogni singola pagina. Inoltre, il valore PageRank della pagina A è calcolato partendo dal valore Pagerank delle pagine che contengono collegamenti ipertestuali ad A.

Il PageRank delle pagine Ti che linkano la pagina A non influenzano il Pagerank della pagina A uniformemente. All'interno dell'algoritmo, il PageRank di una pagina T è sempre commisurato ai link verso l'esterno C(T) posti sulla pagina T. Questo significa che più collegamenti verso altri siti possiede T , meno la pagina A beneficerà di un link ad essa posto sulla pagina T. Il valore, ridotto, del Pagerank delle pagine Ti è aggiunto successivamente. La conseguenza di ciò è che un link verso A incrementerà sempre il pagerank di A.
Infine, la somma dei valori Pagerank (come visto, ridotti proporzionalmente al numero di link verso l'esterno) delle pagine Ti è moltiplicato per un fattore di aggiustamento d che può essere fissato tra 0 e 1. Conseguentemente, l'incremento del valore Pagerank di una pagina A, dovuto al fatto che A è linkata dalle pagine Ti viene ridotto.

RANDOM SURFER MODEL - IL MODELLO DEL NAVIGATORE CASUALE

Nelle loro pubblicazioni, Lawrence Page e Sergey Brin forniscono un'interpretazione molto semplice ed intuitiva del Pagerank. Essi considerano l'algoritmo in questione come un modello di comportamento di un utente, il quale segue i link presenti in una pagina senza seguire una logica o verificarne in contenuti. C'è una determinata probabilità che il navigatore casuale visiti una pagina web, e questa probabilità è data dal valore Pagerank. La probabilità che lo stesso navigatore segua un link è data unicamente dal numero di collegamenti presenti su quella pagina. Questo spiega perchè il Pagerank di una pagina T non è completamente passato alla pagina A che questa linka, ma viene calcolato anche in base al numero di link presenti su T (in poche parole, essendo un calcolo di probabilità, se T possiede un solo link, e questo link è verso A, c'è il 100% di possibilità che il navigatore casuale finisca su A; se T possiede 100 link, e uno solo è verso A, ci sarà l'1% di possibilità che giunga a A).

Quindi, la probabilità che un navigatore casuale raggiunga una pagina è data dalla somma delle probabilità che il navigatore casuale segua i link verso di essa. Ora, questa probabilità è ridotta tramite il fattore di aggiustamento d. La giustificazione di questa costante, all'interno del modello del navigatore casuale, quindi, è che l'utente non segue all'infinito i collegamenti presenti su una pagina, ma a volte si annoia e salta ad un'altra pagina casualmente.

Le probabilità che l'utente non smetta di cliccare sui collegamenti è data dal fattore di aggiustamento d, che è, a seconda del grado di probabilità spiegato prima, fissato tra 0 e 1. Più alto è d, più facilmente e a lungo il navigatore continuerà a seguire i link. Siccome l'utente salta ad un'altra pagina a caso dopo che ha terminato di seguire i collegamenti, la probabilità è quindi assunta come costante (1-d) all'interno dell'algoritmo. Senza contare i link verso la pagina, le probabilità che un navigatore raggiunga la pagina sono sempre fissate a (1-d), così che la pagina ottenga un valore minimo di Pagerank.

UNA DIFFERENTE INTERPRETAZIONE DEL PAGERANK™

Lawrence Page e Sergey Brin hanno pubblicato due formule diverse del Pagerank in diversi documenti. Nella seconda versione, il valore pagerank della pagina A è dato da:

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

dove N è il numero totale delle pagine web all'interno di Internet. La seconda versione dell'algoritmo tuttavia non differisce di molto dalla prima (vedi sopra). riguardo il modello di navigatore casuale la seconda versione del Pagerank rappresenta l'attuale probabilità che il navigatore raggiunga la pagina A dopo aver cliccato un gran numero di collegamenti ipertestuali. I valori pagerank sono distribuiti tra tutte le pagine del web, in modo tale che la somma di tutti i valori pagerank di tutte le pagine all'interno di internet sia pari a 1.

Contrariamente alla prima versione, la probabilità che un navigatore raggiunga una data pagina è inversamente proporzionale al numero delle pagine presenti sul web. Quindi, in questa versione, il PageRank è un valore stimato sulla base delle volte che il navigatore casuale raggiungerà la pagina, nel caso egli riparta con la navigazione un numero di volte pari al numero di pagine pubblicate su internet.

esempio: se il web avesse 100 pagine e una data pagina avesse valore pagerank=2 , il navigatore casuale raggiungerebbe la pagina mediamente 2 volte se partisse con la sua navigazione casuale 100 volte.

Nella sostanza, le due versioni dell'algoritmo non differiscono l'una dall'altra. Il PageRank calcolato utilizzando la seconda formula deve essere moltiplicato per il numero totale delle pagine di internet per ottenere lo stesso valore che si otterrebbe usando la prima formula. Persino Brin e Page hanno unito le due formule nella loro più famosa pubblicazione "The Anatomy of a Large-Scale Hypertextual Web Search Engine", in cui dichiarano che la prima versione dell'algoritmo è atta a formare una distribuzione di probabilità tra tutte le pagine web presenti su internet assumendo 1 come somma totale dei pagerank di tutte le pagine web.

Di seguito faremo un esempio chiarificatore, utilizzando la prima versione dell'algoritmo, poichè i calcoli saranno più semplici e perchè possiamo ignorare il numero totale delle pagine internet (l'obiettivo è dimostrare il principio di funzionamento dell'algoritmo).

LE CARATTERISTICHE DEL PAGERANK™

Le caratteristiche del Pagerank possono essere facilmente illustrate utilizzando un semplice esempio.

Prendiamo in considerazione un piccolo sistema composto da tre pagine A, B e C, in cui la pagina A contiene collegamenti verso B e C, pagina B collega a C e la pagina C collega a pagina A. In accordo con i dettami di Page e Brin dovremmo fissare il fattore di aggiustamento d a 0,85, ma per mantener semplice il calcolo lo fisseremo a 0.5. L'esatto valore di d ha effetti significativi sul valore finale del Pagerank, ma non influenza il principio fondamentale del Pagerank, che è ciò che ci proponiamo di capire con l'esempio che segue.

Quindi, otteniamo le seguenti equazioni ai fini del calcolo del valore Pr:

PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

Queste equazioni sono facilmente risolvibili, ottenendo per ogni singola pagina i seguenti risultati:

PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615

Ovviamente la somma dei singoli valori Pagerank è 3 e quindi uguale al numero delle pagine. Come spiegato prima questo risultato non è assoluto ma ha valore solo ai fini del nostro esempio, il quale è un semplice sistema di tre pagine web i cui valori pagerank sono facilmente ottenibili. Il web, tuttavia, è composto da miliardi di documenti e non è di fatto possibile calcolare i valori pagerank tramite questa metodologia.

IL CALCOLO ITERATO DEL PAGERANK™

A causa dell'elevata dimensione del Web attuale, Google utilizza una metodologia approssimativa e ciclica per il calcolo del pagerank di ogni singola pagina web. Questo significa che ad ogni pagina viene assegnato un valore prefissato iniziale e i valori pagerank delle pagine sono determinati in successivi cicli di calcolo basati sulle equazioni definite dall'algoritmo di base. Il calcolo ripetuto verrà illustrato utilizzando l'esempio del web idealmente composto da tre pagine, in cui ad ogni pagina verrà assegnato un valore pagerank=1.

Ciclo di calcolo

PR(A)
PR(B)
PR(C)

0
1
1
1

1
1
0.75
1.125

2
1.0625
0.765625
1.1484375

3
1.07421875
0.76855469
1.15283203

4
1.07641602
0.76910400
1.15365601

5
1.07682800
0.76920700
1.15381050

6
1.07690525
0.76922631
1.15383947

7
1.07691973
0.76922993
1.15384490

8
1.07692245
0.76923061
1.15384592

9
1.07692296
0.76923074
1.15384611

10
1.07692305
0.76923076
1.15384615

11
1.07692307
0.76923077
1.15384615

12
1.07692308
0.76923077
1.15384615

Possiamo constatare che otteniamo l'effettivo (o maggiormente verosimile) valore pagerank dopo poche iterazioni. In accordo con le pubblicazioni di Lawrence Page e Sergey Brin, sono necessari all'incirca 100 iterazioni per ottenere i valori pagerank dell'intero Web. Inoltre, come dimostrato dal calcolo sopra effettuato, la somma del totale del pagerank di tutte le pagine si convergerà verso il numero totale dei documenti presenti su internet.

Quindi il valore medio del pagerank di una pagina è 1. Il pagerank minimo di una pagina è dato da (1-d). Conseguentemente, c'è anche un massimo valore pagerank raggiungibile che è dato da dN+(1-d), dove N è il numero totale delle pagine web. Questo valore massimo è teoricamente raggiungibile solo nel caso in cui tutte le pagine web si colleghino ad una pagina, e questa pagina si colleghi solo a se stessa.

TRUSTRANK

"Nel 2004 alcuni ricercatori del dipartimento di Computer Science della Stanford University hanno pubblicato uno studio dal titolo “COMBATING WEBSPAM WITH TRUSTRANK ” (Combattere lo spam con il TrustRank) ed il 16 marzo 2005 la tecnologia TrustRank è stata ufficialmente brevettata da Google [...]
Il TrustRank è un algoritmo in parte basato sulla valutazione dei siti effettuata da esseri umani, progettato per risolvere il grosso problema dello spam presente negli indici dei motori di ricerca.[...]"

Continua la lettura sull'algoritmo TRUSTRANK sul sito POSIZIONAMENTO-WEB.COM , da cui è stato estratto il paragrafo sopra riportato.

RISORSE ESTERNE - REFERENCE

BREVETTO ORIGINALE DEL PAGERANK™

TOPIC SENSITIVE PAGERANK™ - STANFORD UNIVERSITY