PageRank: sulle spalle dei giganti

Massimo Franceschet
Dipartimento di Matematica e Informatica
Università di Udine
Via delle Scienze 206 -- 33100 Udine, Italia
Email: massimo.franceschet@dimi.uniud.it



Google, il più famoso dei motori di ricerca, al fine di ordinare i risultati (le pagine Web) a fronte di una ricerca fatta da un utente, combina due metodi: la rilevanza e l'importanza. Una pagina è rilevante quando parla dell'argomento cercato dall'utente, e Google assegna ad ogni pagina un punteggio di rilevanza che misura quanto la pagina è attinente rispetto ai termini inseriti dall'utente. Ma il vero punto di forza di Google, che gli ha consentito si surclassare gli altri motori di ricerca, è il metodo che assegna il giudizio di importanza alle pagine. Tale algoritmo prende il nome di PageRank.

Il PageRank assegna un giudizio di importanza ad ogni pagina indipendentemente dalle interrogazioni degli utenti, ma unicamente in funzione della rete dei collegamenti ipertestuali tra pagine Web, rete che forma il World Wide Web. Il PageRank usa la seguente tesi:

Una pagina è importante se viene citata da altre pagine importanti.

Nel contesto del Web, una citazione è un collegamento ipertestuale (link) da una pagina sorgente (la pagina che contiene il link) ad una pagina destinatario (la pagina verso cui il link è diretto). La definizione, apparentemente circolare, è in realtà risolvibile usando strumenti matematici profondi, quali il Teorema di Perron-Frobenius che garantisce l'esistenza e l'unicità di una soluzione al problema della determinazione del PageRank per ogni pagina Web e il Metodo delle Potenze che permette di calcolare in modo iterativo la soluzione.

PageRank

Più precisamente, il metodo del PageRank usa i seguenti tre fattori per determinare l'importanza di una pagina Web:

  • il numero di link ricevuti dalla pagina;
  • l'importanza delle pagine sorgenti che contengono i link alla pagina;
  • il numero di link contenuti nelle pagine sorgenti.
  • Per capire l'importanza dei tre fattori, applichiamo il metodo del PageRank ad una ipotetica rete in cui i giornalisti sono tra loro collegati da giudizi di approvazione da parte di altri giornalisti. Supponiamo, per semplicità, che ogni giornalista possa esprimere un giudizio positivo, non meglio quantificato, detto approvazione, nei confronti di altri suoi colleghi che ritiene meritevoli, mentre non dica nulla se li ritiene neutri o poco meritevoli. Usando il metodo del PageRank per determinare il prestigio dei giornalisti, possiamo reinterpretare i tre fattori esposti sopra nel seguente modo:

    1. un giornalista è tanto più prestigioso quanto più elevato è il numero di approvazioni che ottiene da parte di colleghi (la quantità è importante);
    2. approvazioni ricevute da giornalisti importanti valgono più di giudizi ottenuti da giornalisti poco stimati (anche la qualità conta);
    3. infine, se un giornalista è prodigo di giudizi positivi (cioè ne distribuisce molti), i suoi giudizi sono inflazionati e valgono meno.

    Il metodo del PageRank è stato proposto da Sergey Brin e Larry Page nel 1998 durante il dottorato all'Università di Stanford ed è correntemente uno degli ingredienti principali del motore di ricerca Google. Il PageRank è un metodo sottoposto a brevetto. E' curioso come, in realtà, questo metodo fosse già noto ben prima del 1998 in contesti completamente diversi dalle ricerche sul Web. Nell'articolo PageRank: Stand on the shoulders of giants, l'autore Massimo Franceschet, ricercatore del Dipartimento di Matematica e Informatica dell'Università di Udine, traccia la storia di questi illustri predecessori, di seguito riassunta.

    1. Nel 1976, vale a dire 22 anni prima della nascita di Google, Gabriel Pinski e Francis Narin propongono un metodo bibliometrico per valutare l'importanza delle riviste accademiche. L'intuizione è sorprendentemente simile a quella del PageRank: una rivista è importante se viene citata da altre riviste importanti. In questo caso, per citazioni di intendono i riferimenti bibliografici contenuti nella bibliografia degli articoli pubblicati nelle riviste. Questo metodo è stato ripreso varie volte nel contesto della bibliometria, la quale si occupa di proporre metodi per valutare quantitativamente la qualità della ricerca accademica. Ad esempio, l'indicatore bibliometrico noto come Eigenfactor realizza l'idea proposta da Pinski e Narin, e, ad oggi, è considerato un serio competitore dell'Impact Factor proposto da Eugene Garfield.
    2. Nel 1965, cioè 11 anni prima del metodo bibliometrico di Pinski e Narin, il sociologo Charles H. Hubbell propone un metodo per valutare l'importanza delle persone in una rete sociale. Anche in questo caso, la tesi è la medesima: una persona è importante se viene riconosciuta da altre persone di valore. Vi è però una variante interessante: il giudizio di valore espresso dai soggetti può essere positivo, neutro o negativo. Naturalmente, ricevere giudizi positivi da persone importanti aumenta il nostro valore, mentre ricevere giudizi negativi da persone di valore fa decrescere il nostro prestigio. Al contrario, secondo l'algoritmo di Hubbell, ricevere riconoscimenti positivi da persone negative (ad esempio, da un mafioso) diminuisce il nostro valore, mentre essere osteggiati da persone negative aumenta il nostro prestigio (si pensi a Roberto Saviano).
    3. Ma la vera sorpresa sta nel fatto che il metodo usato dall'economista russo Wassily W. Leontief per determinare i prezzi dei beni nei sistemi economici, ideato nel lontano 1941 (a più di mezzo secolo dalla nascita di Google) e che gli è valso il Premio Nobel per l'Economia nel 1973, non è altro che il PageRank sotto mentite spoglie. Leontief interpreta l'economia come una rete di industrie o settori in cui ogni settore riceve beni da altre industrie e li usa per produrre beni che a sua volta vende ad altri settori. Per determinare i prezzi dei beni prodotti dai vari settori che mantengano la riproducibilità dell'economia, vale a dire il pareggio tra costi e ricavi in ogni settore, Leontief usa un algoritmo molto simile al PageRank: il prezzo dei beni prodotti e venduti da una industria (e quindi il suo ricavo) è tanto più alto quanto è elevato il prezzo dei beni acquistati dall'industria presso altri settori. Quindi industrie fortemente remunerative acquistano i loro prodotti da altre industrie remunerative, la stessa circolarità che ritroviamo nel PageRank. Curioso come proprio un economista russo sia, involontariamente, alla base del successo di uno dei più grossi colossi tecnologici americani.

    In realtà, il vero contributo di Sergey Brin e Larry Page è stato quello di partire da una idea non completamente sconosciuta e farne una idea di successo, costruendo qualcosa di enorme utilità per tutti, in particolare per i ricercatori. Il metodo del PageRank ha cambiato radicalmente i concetti di qualità e di verità dell'informazione che si trova sul Web, allontanandoli dal giudizio erudito degli esperti e associandoli al parere espresso dall'intera comunità. Pare appropriato terminare con un paragrafo di Alessandro Baricco tratto da I barbari. Saggio sulla mutazione (Fandango 2006):

    Il valore di un'informazione, nel Web, è dato dal numero di siti che vi indirizzano verso di lei: e quindi dalla velocità con cui, chi la cerca, la troverà. [...] La velocità è generata dalla qualità, non il contrario. I proverbi, diceva Benjamin con una bella espressione, sono geroglifici di un racconto: la pagina web che trovate in testa ai risultati di Google è il geroglifico di tutto un viaggio, fatto di link in link, attraverso l'intera rete.





    L'articolo originale: PageRank: Stand on the shoulders of giants

    Alcune recensioni: