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 r dagli altri come segue:

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:

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ì

qualunque 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):

La stessa espressione può essere interpretata (e anzi di solito è spiegata in questi termini) come la probabilità di trovare sulla pagina i 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.

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.

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

Reti parte 2: Gradi di separazione

Un modo molto sintetico di descrivere la differenza tra le due reti di linee aeree del post precedente è attraverso la dimensione di una rete. Non intendo dimensione nel senso di grandezza o estensione, ma un concetto più simile a quello di dimensioni dello spazio, una su una retta, due su un piano, e così via. Per le reti è rilevante una definizione di dimensione abbastanza esotica, che è lo stessa che si usa per i frattali. Questa non fa uso, come si fa di solito, del numero di variabili usate per descrivere un punto, e grazie a questo non è necessariamente un numero intero!

Cercherò di spiegare il senso di questo strano concetto. Partiamo da una rete fatta così:chiamiamo distanza tra due nodi della rete il numero minimo di passi che dobbiamo compiere per passare dall’uno all’altro. Inoltre si dice diametro D la distanza tra i due nodi più lontani. In questo caso è facile vedere che il diametro è lineare in n, in particolare è uguale a n-1. I due nodi più lontani sono, ovviamente, quelli agli estremi.

Se invece consideriamo un reticolo quadrato

i due nodi più lontani sono quelli negli angoli, che distano il doppio del lato del quadrato. D’altra parte, se il quadrato contiene n nodi, il lato ne contiene un numero dell’ordine della radice di n.

Potremmo andare avanti, ma dovrebbe cominciare a intuirsi un pattern: con un reticolo cubico il diametro scalerà come la radice cubica del numero di nodi, e così via. Dal momento che è intuitivo definire il primo esempio come rappresentativo di reti unidimensionali e il secondo come bidimensionale, chiamiamo dimensione della rete il numero d che dà la legge di potenza attesa:

In poche parole, il diametro indica quanto è ben connessa la rete, mentre il numero di nodi quanto è grande. Allora la dimensione è una misura di quanto è compatta. Più avanti vedremo degli esempi.

I reticoli non sono gli unici casi mono o bi-dimensionali: considerando un anello, come

si vede che questa volta il diametro è n/2, diverso dal reticolo rettilineo, ma con la stessa legge di potenza rispetto a n, che fa di lui ancora una volta una rete a una dimensione, come vuole l’intuito.

L’intuito però può rapidamente fallire quando esaminiamo casi più strani.

Questo è un Cayley tree. Potete divertirvi a far vedere che il diametro scala come il logaritmo del numero di nodi! Non esiste un d abbastanza grande da soddisfare la definizione! Per questo si dice che la rete ha dimensione infinita. Reti di questo tipo si chiamano small worlds, “mondi piccoli”.

Da quando il loro studio si è diffuso, negli anni Novanta, reti small world sono state trovate dappertutto. È molto nota l’ipotesi dei sei gradi di separazione, secondo cui ognuno di noi è collegato a chiunque altro nel mondo, da un contadino cinese al presidente Obama, attraverso non più di sei “passi” di conoscenza personale. Perché qualcosa del genere sia possibile, su sette miliardi di individui, il diametro non può scalare con una legge di potenza!

Un altro esempio, quello da cui eravamo partiti, è Internet: immaginate che sia, per esempio, una rete bidimensionale. Ogni volta che volete raggiungere un server in Nuova Zelanda, i dati che inviate e ricevete dovrebbero passare attraverso un numero di intermediari dell’ordine della radice di n, qualcosa come dieci, centomila computer o più. Non sarebbe di sicuro un metodo efficiente di costruire una “world wide web”. Ecco perché l’informazione sulla struttura della rete è cruciale per il suo funzionamento.

Con questo volevo spiegare perché tutte queste reti sono strutturate in modo da avere una dimensione infinita. Il problema è che spiegare il perché non è sufficiente. Il “perché” presuppone un fine; ma questo è in contraddizione con quello che dicevo nel post precedente, cioè che Internet, il WWW, e molte altre reti di rilevanza quotidiana si sono sviluppate (“evolute” è un bel modo di dirlo) per auto-organizzazione, senza che ci fosse un progettista o Creatore con la C maiuscola che vede dall’alto gli scopi della sua opera. Abbiamo quindi ancora una volta bisogno di trovare un modo per rendere conto di come hanno fatto a emergere una dimensione, e una degree distribution, che sono proprio quelle che ci servono. La rete deve essersi sviluppata secondo un criterio particolare che ha portato a questo risultato momento per momento, ognuno pensando per sé, senza sapere quale fosse l’obiettivo globale.

Disgraziatamente, mi sono dilungato troppo.

Recensione: «Consciousness, confessions of a romantic reductionist»

Paul Gauguin’s haunting masterpiece, D’où venons nous? Que sommes nous? Où allons nous?, painted in Tahiti in the closing years of his life, perfectly encapsulates the three questions I am obsessed with: Where do we—humans, dogs, and other sentient beings—come from? Who are we? Where are we going? I’m a natural scientist. I have a deep-seated desire to find answers to these questions and to understand the physical universe, as well as consciousness.

Non c’è dubbio che le premesse di Christof Koch e del suo ultimo libro – tradotto in italiano da S. Ferraresi con il titolo Una coscienza: confessioni di uno scienziato romantico – sembrino ambiziose. Nonostante le apparenze, però, è subito evidente che l’autore non ha lo scopo di fornire una verità assoluta relativamente a quel problema che chiama addirittura hard problem per antonomasia, cioè come sia possibile che ognuno di noi esista, riceva delle sensazioni dal mondo esterno, provi emozioni e perfino abbia un’idea di sé, della sua mente, come di qualcosa di separato da tutto il resto dell’universo.

Koch sceglie di prenderla alla leggera. Inizia descrivendo la sua esperienza di studente, il lavoro e il rapporto umano – che lo ha segnato profondamente – con Francis Crick, che dopo la scoperta del DNA si è dedicato al problema della coscienza insieme a lui. Ma nonostante il punto di vista profondamente personale del libro, riesce anche a trasmettere, soprattutto nei capitoli centrali del libro, delle idee di grande interesse e soprattutto, fatto non scontato visto l’argomento, basate su fondamenti perfettamente scientifici. Si dilunga sul libero arbitrio, e fa sì che il lettore si renda conto di come abbia un ruolo molto più marginale nella nostra vita di quanto si creda: migliaia e migliaia di processi gestiti automaticamente dal nostro cervello, che chiama gli “zombie”, si occupano della grande maggioranza delle nostre azioni. Ho trovato poi particolarmente interessante una discussione sul perché la coscienza esiste, e se può essere spiegata in termini di evoluzione darwiniana. Naturalmente non si dimentica di dare una definizione di coscienza, e anche qui, i risultati non sono scontati.

Verso la fine forse si lascia andare a qualche speculazione di cui non sono evidenti, almeno dalle sue parole, le prove materiali; mi sembra però che questo gli si possa perdonare alla luce di un capitolo conclusivo che torna ad essere autobiografico anche per lo scopo di confessare le debolezze e incertezze del suo pensiero, e per discutere liberamente di quelli che chiama “temi conclusivi considerati fuori dai confini del discorso scientifico beneducato”, come la relazione tra scienza e religione. In questo confessa, alla fine, che il vero scopo del libro non era solo la divulgazione, ma descrivere il suo viaggio personale alla ricerca delle radici materiali della coscienza, i suoi fallimenti personali, e la sua visione dell’universo, messi su carta perché «I care about questions of free will. I know through encounters with students and colleagues that more than a few lie awake at night, wondering about these things.»

Penso che il messaggio del libro si possa riassumere in una frase, che secondo me non solo qualunque scienziato con una passione per il suo lavoro, ma da sempre più persone che condividono una visione laica del mondo:  «I wake up each morning to find myself in a world full of mystery and beauty. And I am profoundly thankful for the wonder of it all.»

(Forse non mi sono soffermato abbastanza sul fatto che sì, il libro ha anche dei contenuti seri, e a leggerlo si imparano un sacco di cose sia sulla mente che sul cervello. A questo punto non vi resta che controllare personalmente. Tra l’altro, l’incipit della traduzione italiana è stato pubblicato sul sito di Internazionale.)

A slower speed of light

Un po’ di tempo fa mi sono imbattuto, non mi ricordo come, in questo giochino del MIT, che ha l’obiettivo di insegnare quali sono gli effetti della relatività speciale su un viaggiatore che si muove a velocità prossime a quelle della luce. È un videogioco in prima persona, in cui il protagonista si muove in un piccolo ambiente raccogliendo sfere che hanno la proprietà di ridurre la velocità della luce quando entrano in suo possesso.

Perché questo dovrebbe permetterci di osservare effetti relativistici? Facendo un passo indietro, senza però voler annoiare chi sa già tutto, vi ricordo che, prima di Einstein e Lorentz, si pensava che per passare da un sistema di riferimento a un altro, in moto rettilineo e uniforme con velocità v rispetto al primo, valessero le trasformazioni

che si chiamano galileiane. Quando nell’ottocento si scoprì che le leggi dell’elettromagnetismo (che regolano, tra le altre cose, proprio la luce), erano incompatibili con queste trasformazioni, si dimostrò (sperimentalmente) che Galileo aveva scoperto solo un’approssimazione delle vere trasformazioni, che vale solo quando v è piccola. Piccola rispetto a cosa? Ma rispetto alla velocità della luce, naturalmente. E infatti se prendiamo le trasformazioni di Lorentz, salta fuori che si discostano da quelle di Galileo di un fattore

questo si avvicina sempre di più a 1, recuperando la fisica pre-relativistica, quanto più v/c è piccolo. Questo succede, nella realtà, quando la velocità in gioco è trascurabile rispetto a quella della luce. Ma è lo stesso se, al contrario, faccio finta che sia la velocità della luce ad aumentare: di fatto, se supponessi che la luce si muova a velocità infinita, non ci sarebbe nessun effetto relativistico (avrei problemi con l’elettromagnetismo, ma questa è un’altra storia). (Tra parentesi, lo stesso succede con la meccanica quantistica: in questo caso devo portare la costante di Planck a zero per ottenere un universo classico)

I creatori del gioco hanno deciso di fare il contrario, cioè di ridurre c in modo da far muovere la luce a velocità comparabile con quella del protagonista. Non solo: man mano che il gioco va avanti, c diminuisce sempre di più, in modo da permetterci di osservare effetti relativistici con diverse intensità. Il risultato si vede nel “trailer” pubblicato sul sito:

Cosa sta succedendo? Innanzitutto tutti gli effetti che si notano cambiano a seconda che il protagonista sia fermo o si muova. Finché non cammina, come ho spiegato sopra, v/c = 0 e quindi vive in un mondo perfettamente non-relativistico. Quando comincia a correre, la conseguenza che si nota subito è che cambia il colore dell’ambiente circostante. Questa è una conseguenza dell’effetto Doppler (quello delle ambulanze, che cambiano tono a seconda che si stiano avvicinando o allontanando, ma per la luce), per cui la luce cambia di lunghezza d’onda, e quindi di colore, quando vado incontro o mi allontano dall’oggetto che la emette (si arriva addirittura a vedere l’infrarosso e l’ultravioletto). Inoltre è considerato un effetto di aberrazione relativistica per cui risulta più intensa la luce che proviene dalla direzione verso cui mi muovo. Infine, si notano cambiamenti della geometria nelle zone più esterne del campo visivo.

A slower speed of light non è un vero gioco, nel senso che oltre a raccogliere sfere non c’è molto da fare, e dopo pochi minuti spesi ad osservare il mondo con gli occhi di una particella ad alta energia le novità scarseggiano. Tuttavia è stato progettato innanzitutto con uno scopo didattico, che assolve egregiamente e per cui consiglio a tutti di provarlo (si può scaricare gratuitamente per Win, Mac e Linux). E può interessarvi sapere che gli stessi autori hanno progettato una libreria open source per il futuro sviluppo di giochi fisicamente accurati.

Gerd Kortemeyer, Philip Tan, and Steven Schirra (2013). A Slower Speed of Light: Developing intuition about special relativity with games FDG 2013, FDG ‘13 Proceedings of the International Conference on the Foundations of Digital Games, 400-402

Reti parte 1 – degree distribution

Il cervello. Il world wide web. Internet. Le interazioni tra le proteine in una cellula. L’espressione dei geni. Le ferrovie europee. I miei amici su Facebook. Che cosa hanno in comune tutti questi sistemi, che provengono da aree completamente diverse tra loro? Una delle maggiori gioie dello scienziato che lavora con un punto di vista teorico è scoprire che uno stesso modello si adatta a realtà diverse: è una delle sorgenti della bellezza matematica.

L’oggetto matematico di cui stiamo parlando è la rete. Tutti gli esempi sopra hanno in comune la possibilità di essere descritti come un insieme di elementi collegati tra loro con una geometria particolare. Chiamiamo nodi questi elementi, proprio come nelle reti da pesca, ogni volta che trama e ordito si incrociano, si annodano tra loro. I neuroni, le pagine del web, i computer connessi a internet, gli snodi ferroviari, gli aeroporti, sono tutti esempi di cose che possono essere rappresentate come nodi di una rete. I nodi sono collegati tra loro da sinapsi, collegamenti ipertestuali, cavi in fibra ottica, strade ferrate, voli regolari o altre forme di interazione più o meno concrete. Per esempio, supponiamo che Edimburgo non sia collegata a Milano da un volo diretto, mentre lo sono Londra e Francoforte, aeroporti in cui posso fare scalo per andare in Scozia. Visto che Londra e Francoforte, incidentalmente, sono anche collegate tra loro, posso schematizzare il tutto così:Questo è quello che i matematici chiamano un grafo. Si comincia a parlare di reti quando si fa uno studio dei grafi dal punto di vista statistico. Pensate ad estendere uno schema del genere a un sistema enormemente grande, come i cento miliardi di neuroni di un cervello medio, ognuno connesso a una media stimata di mille altri. È chiaro che a questo punto non ci interessa – e se ci interessasse sarebbe comunque un’impresa impossibile – studiare ogni neurone come un’entità singola, con un’etichetta come “Milano” o “Londra” per ognuno. Possiamo invece raccogliere informazioni preziose su come è fatta la struttura su grande scala. Il numero di nodi e di archi che li collegano è la prima, fondamentale, informazione. Ma c’è molto altro: per esempio, c’è un piccolo numero di nodi che domina la rete, nel senso che su di essi sono concentrati la maggior parte dei collegamenti? O tutti hanno più o meno lo stesso ruolo? C’è un solo modo di passare da un punto all’altro, come per le ramificazioni di un albero, o sono possibili più percorsi e circoli chiusi?

Torniamo all’esempio di prima. Supponete che i collegamenti aerei tra alcune città europee siano disponibili solo secondo gli schemi seguenti:

Nonostante abbiano lo stesso numero di nodi e lo stesso numero di archi, sono due grafi molto diversi! Nel primo c’è uguaglianza tra tutte le città, nel secondo Londra ha un ruolo privilegiato. Mentre nel primo, per andare da Milano a Copenhagen, devo cambiare aereo tre volte (!), nel secondo è garantito che qualunque destinazione può essere raggiunta con al massimo uno scalo, e tuttavia, resta l’assurdità di dover passare da Londra per andare da Helsinki a Mosca. Questo illustra l’importanza che la struttura della rete ha sul suo funzionamento, qualunque esso sia.

Per poter fare affermazioni quantitative, i teorici delle reti (che sono matematici, fisici, biologi, informatici e altro, rendendo multidisciplinare questo campo) hanno definito delle quantità che misurano queste caratteristiche. La prima che ci interessa è la distribuzione dei gradi. Il grado q di un nodo è il numero di connessioni che forma con altri nodi. La distribuzione di questa quantità è una funzione P(q) che dice ci sono P(1) nodi con grado 1, P(2) nodi con grado 2, eccetera eccetera.

Se dovessi scegliere una distribuzione P, troverei naturale lavorare con funzioni con un picco, tali per cui tutti i nodi hanno all’incirca lo stesso numero di connessioni, come negli esempi disegnati sopra. Oppure con distribuzioni di Poisson, perché si presenterebbero spontaneamente quando la rete è stata prodotta con un processo casuale. Internet, anche se non tutti lo sanno, non è stato progettato, ma la sua struttura ha origine da gruppi di calcolatori che si collegavano alla rete preesistente nel modo che sembrava più conveniente; il WWW, che non è la stessa cosa, bensì l’insieme delle pagine web, a sua volta, ha subito un processo di crescita in cui nuovi siti si collegavano ai vecchi senza uin progetto, in modo autonomo. Ci si aspetterebbe che reti che non solo sono enormi e intricate, ma non hanno un progettista unico siano evolute in modo abbastanza casuale, no?

Le cose si cominciano a fare interessanti quando si scopre che una classe molto vasta di reti ben diverse tra loro hanno i gradi distribuiti allo stesso modo. E per giunta, non nel modo che ci si aspetta da una crescita a casaccio: sono dotate di una struttura particolare, che emerge dal modo in cui crescono.

La rete sociale degli attori, la rete elettrica degli Stati Uniti, le citazioni degli articoli scientifici, il WWW, sono stati tutti studiati e per tutti questi si è trovata la stessa distribuzione, che decade con una legge di potenza. Lo stesso risultato è stato più tardi confermato per altri esempi ancora, mostrando una sorprendente somiglianza tra sistemi che sono fisicamente realizzati in modo diverso, interagiscono in modo diverso, e soprattutto nascono ed evolvono in modo diverso.

Vi lascerò nel dubbio sul perché questo accada fino al prossimo post.

(Se volete stare aggiornati, non dimenticate di iscrivervi al feed.)