Come funziona Google PageRank?

Google Search, il motore di ricerca più famoso del mondo, è una macchina che funziona incredibilmente bene. Un paio di parole chiave accuratamente scelte ed ecco che compaiono migliaia di risultati. Sì, migliaia: in questo 2013 il web è talmente esteso che la maggior parte delle ricerche che possiamo fare quotidianamente riguardano argomenti già trattati ampiamente un po’ dappertutto. Eppure, se ci fate caso, in mezzo a migliaia di risultati, raramente è necessario spingersi molto avanti, anzi in genere non bisogna neppure disturbarsi a leggere la seconda pagina.

Vi siete mai chiesti come fa Google a dare la precedenza a Wikipedia o a un sito autorevole rispetto a qualche sconosciuto blog di autore ignoto? E soprattutto, a sapere già cosa avete in mente, come a volte dà l’impressione (con occasionali errori grossolani)? Gli stessi fondatori di Google, Brin e Page, presentando l’algoritmo che fu una soluzione di questo dilemma, scrivevano nel 1999:

L’importanza di una pagina Web è una questione in sé soggettiva, che dipende dagli interessi, dalle conoscenze e dalle attitudini dei lettori. Ma c’è comunque molto da dire oggettivamente sull’importanza relativa delle pagine Web. [PageRank è] un metodo per valutare le pagine Web oggettivamente e automaticamente, misurando di fatto l’interesse e l’attenzione umani a queste rivolti.

Il Web è una grande rete (web vuol dire “ragnatela”, come saprete) i cui nodi sono pagine e i cui collegamenti sono i link (da non confondere con Internet, che è una rete di computer). In particolare è una rete direzionale perché se la pagina A ha un link verso B, non necessariamente è vero il contrario. L’algoritmo assegna a ogni pagina un rango (rank appunto), una sorta di misura del suo prestigio, o della sua autorevolezza. Il punto è come determinarla. Un punto di partenza ragionevole e intuitivo è il seguente: una pagina è tanto più autorevole quanto più autorevoli sono le pagine che parlano di essa. In altre parole, se Wikipedia, che è un sito importante e famoso, mette un link al mio piccolo blog, il prestigio del mio sito aumenta. Mettendo giù una formuletta, mi aspetto una dipendenza del mio ranking dagli altri come segue:

r_i =\sum_{j:j\to i} \frac{r_j}{k_j}

dove la sommatoria è su tutte le pagine j che hanno un link che punta verso la mia, i. Il valore k al denominatore è il numero di link che escono dalla pagina j: se la stessa pagina di Wikipedia cita centinaia di altre fonti, io sono solo uno in mezzo a mille altri e questa influenza positiva ragionevolmente diminuisce.

Questa equazione è autoconsistente, nel senso che la sua soluzione dipende dai rank di tutte le altre pagine, che è determinato dalla stessa equazione. Questo gatto che si morde la coda ha comunque una soluzione, che si può, tra l’altro, ottenere numericamente scegliendo degli r di partenza casualmente e applicando più e più volte la formula fino a raggiungere un risultato stabile con la precisione desiderata. Nonostante questo, ha dei difetti: innanzitutto, ha sempre una soluzione in cui tutti i rank sono zero. Anche la soluzione non banale ha un problema di fronte a un loop come questo:Loop1

i tre nodi “acquisiscono prestigio” dall’esterno senza mai distribuirne. A ogni iterazione dell’algoritmo, il loro prestigio aumenta fino a divergere. Per un loop isolato così

Loop2qualunque numero, purché uguale sulle tre pagine, è soluzione. Inoltre, ogni nuova pagina, che non ha ancora nessun link in ingresso, otterrà sempre un punteggio nullo che la destina a restare per sempre inosservata.

Il problema è risolto aggiungendo al ranking un piccolo termine “in regalo” alle pagine per il solo fatto di esistere, la cui importanza è determinata da un parametro p (che Google ha fissato a 0.15):

r_i = \frac{p}{N} + (1-p)\sum_{j:j\to i}\frac{r_j}{k_j}

La stessa espressione può essere interpretata (e anzi di solito è spiegata in questi termini) come la probabilità di trovare sulla pagina un “surfer” che naviga casualmente su internet, prendendo link a caso e, con probabilità p, spostandosi su una pagina qualunque anziché cliccare un link.

Oggi, l’algoritmo di Google Search tiene in conto un grande numero di fattori, compresi la lingua, l’area geografica di origine di un sito, la sua data di aggiornamento. Ma il PageRank è ancora il modo usato per determinare l’autorevolezza di un sito, ed è fondamentalmente una misura del suo ruolo all’interno di una rete complessa.

Oltre a funzionare palesemente bene, ha un vantaggio indispensabile per un motore di ricerca importante come Google: è praticamente impossibile influenzarlo o manometterlo, perché non c’è altro modo di aumentare il proprio ranking che convincere un’altra pagina autorevole, o molte piccole, a citarti. In una parola, è profondamente democratico.

PageRank list

I 15 maggiori PageRank del Web a luglio 1996. Il Web delle origini era abbastanza autoreferenziale. A parte la pagina del CERN, che fu la prima. Dall’articolo citato.

ResearchBlogging.orgL Page, S Brin, R Motwani, & T Winograd (1999). The PageRank citation ranking: bringing order to the web. Technical Report. Stanford InfoLab.

Advertisements

2 thoughts on “Come funziona Google PageRank?

  1. Pingback: Carnevale della matematica #65, o 5512, o 1018, o 10014, o 10000012, o lxv, o 5×13, o 12+82, o 42+72, o o5, o anche 15+24+33+42+51.
  2. Pingback: Come funziona Google PageRank? | termueske - Angelo Stella

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s