Molte persone credono che la matematica sia una disciplina fine a se stessa molto astratta e praticamente inutile. I matematici vengono visti come esseri strani che vivono in un universo tutto loro e si occupano di cose che solo loro capiscono e che non servono nella vita di tutti i giorni.
E’ possibile che ci sia qualche cosa di vero in queste affermazioni. Ma di sicuro se non ci fossero stati gli sviluppi matematici fatti negli ultimi anni, molte delle funzionalità che oggi utilizziamo non sarebbero disponibili. La tecnologia avanza con l’avanzare della ricerca matematica e non solo. Anche se molti di noi non se ne accorgono, ogni giorno facciamo uso della matematica. Vogliamo fare un elenco delle applicazioni che vedono coinvolta la ricerca matematica? Proviamoci.
· Fotografia digitale
· Musica digitale
· Film e tv digitali
· Telefonia mobile
· Crittografia
· Navigatore satellitare
· TAC (tomografia assiale computerizzata)
· Previsioni meteo
· Analisi di rischio
· Analisi di economia
· Internet
e tante altre. In questo post, come si intuisce dal titolo ci occuperemo di Internet e in particolare del Page Ranking di Google cioe’ dell’algoritmo utilizzato da Google per assegnare un fattore di importanza alle pagine trovate dal motore di ricerca.
Due studenti dell’Università’ di Stanford, Sergey Brin e Larry Page, hanno fatto la loro fortuna inventando uno dei più potenti motori di ricerca del web “Google”.
Ma cosa deve fare esattamente un motore di ricerca?
Semplicemente ordinare le pagine presenti sul web in base alla loro importanza ogni qualvolta un utente effettua una ricerca. Ma come si può definire l’importanza (page rank) di una pagina?
L’idea dei due studenti e’ stata la seguente.
Ogni pagina web ha una sua propria importanza che deriva dalle connessioni (non direttamente dai contenuti). L’importanza di una pagina viene trasferita in parti uguali alle pagine che essa punta. Quindi l’importanza di una pagina e’ data dalla somma delle frazioni di importanza che gli derivano dalle pagine che ad essa puntano. Facendo ricorso ad una analogia nella vita di tutti i giorni: una persona importante da’ importanza alle persone che frequenta e allo stesso tempo una persona e’ importante se frequenta molte persone importanti.
Passiamo al modello matematico. Supponiamo di numerare le pagine del web da 1 a n. Definiamo la matrice di connettività nel seguente modo:
dove i vari elementi sono uguali a 1 se c’e’ un link tra la pagina i e la pagina j altrimenti sono uguali a zero. Facciamo un esempio con 4 pagine, cioè n=4 e supponiamo di avere la seguente matrice di connettività:
Schematizziamo le connessioni tra le varie pagine con delle frecce ottenendo il seguente grafo:
Sommando i valori della riga i si trova il numero di link che partono dalla pagina i. Indichiamo questo numero con Pi. Sommando, invece, i valori della colonna j si trova il numero di pagine che puntano alla pagina j che indicheremo con Aj. Se adesso indichiamo con xj l’importanza della pagina j risulta che:
per j che varia da 1 a n. Considerando il sistema di 4 pagine precedente, possiamo per esempio scrivere:
Si tratta, in generale, di un sistema lineare di n equazioni in n incognite. Le soluzioni xj danno il livello di importanza delle singole pagine, cioè il page rank.
Ad oggi, pensate che ci sono circa n=8500000000 pagine attive.
Comunque l’equazione da noi ricavata e’ una versione semplificata. In effetti quella usata da Google e’ data da:
dove d e’ un parametro compreso fra 0 e 1, che di solito viene messo a 0.85. I valori di xj sono compresi tra 0 (pagina non importante) e 1 (pagina importantissima.
Ma e’ possibile risolvere un sistema lineare con 8.5 miliardi di incognite? Se utilizzassimo il metodo di eliminazione questo richiederebbe circa 4*109 operazioni matematiche. Sic!
Il calcolatore più veloce esistente al mondo (il Blue Gene dell’IBM) richiederebbe più di 36 milioni di anni per risolvere un tale sistema. Un tempo da ere geologiche....
Eppure Page e Brin calcolano il page rank in continuazione. Come fanno?
Anche se la tecnologia fosse in grado di costruire un computer 1000 volte o anche un milione di volte più veloce sarebbe sempre impossibile risolvere il problema di Google in tempo reale. E allora?
La soluzione la si può ottenere solo sviluppando nuovi metodi matematici. E’ quello che hanno fatto i due sviluppatori di Google che utilizzano il seguente algoritmo.
Prima di tutto assegnano alle pagine dei valori di importanza xj qualsiasi. Inizialmente non importa quale sia il valore. Dopo di che si sostituiscono questi numeri nell’equazione riportata precedentemente ricavando dei nuovi valori di importanza in accordo alla matrice di connettività e ai valori di Pi. A questo punto si inseriscono sempre nella stessa equazione come valori di ingresso xj quelli appena ottenuti. E si ricavano nuovi valori e cosi via. In questo modo viene generata una successione di approssimazioni successive che converge alla soluzione del sistema qualunque siano i valori iniziali utilizzati. Nella figura qui sotto viene riportato l’andamento delle soluzioni del sistema per il caso di 4 pagine riportato sopra come esempio. Notiamo la rapida convergenza delle soluzioni.
Andamento delle soluzioni del sistema Page rank per il caso di 4 pagine
Per fare un passo dell’algoritmo qui descritto bisogna eseguire tante moltiplicazioni quanti sono gli elementi non nulli della matrice di connettività C e all’incirca altrettante addizioni. Su ogni riga della matrice C, comunque, mediamente ci sono pochi elementi diversi da zero. Se supponiamo che questo numero sia 50, un passo del metodo iterativo spiegato, su Blue Gene impiegherebbe solo 2 millesimi di secondo. Se anche fossero necessari 1000 passi iterativi basterebbero 2 secondi per approssimare la soluzione di Google.
Fin dalla sua introduzione l’equazione del PageRank ha ricevuto l’attenzione di moltissimi studiosi che hanno cercato di migliore in tutti i modi il metodo di soluzione del sistema lineare. Qualche anno fa ugruppo di studiosi, tra cui alcuni italiani dell’università’ di Roma e Cagliari, hanno usato un nuovo approccio molto più veloce di quelli esistenti oggi, ricorrendo ad un’analogia con la Fisica Quantistica. In particolare, hanno mostrato che e’ possibile riarrangiare l’equazione Page Rank in modo da ottenere un’equazione simile all’equazione di Schrödinger.
Vi ricordo che l'equazione di Schrödinger rappresenta una delle più importanti conquiste della fisica ed in particolare della meccanica quantistica. Quest'ultima, risalente alla metà degli anni venti e’ stata sviluppata soprattutto da de Broglie e Schrödinger e si basa sul cosiddetto approccio ondulatorio della materia. In questa ottica, si rappresentano le particelle con delle funzioni d'onda in quanto si e’ visto che in certi esperimenti le particelle elementari mostrano comportamenti ondulatori. La funzione d’onda va interpretata in termini probabilistici, cioè il suo modulo al quadrato altro non rappresenta che la probabilità di trovare la particella in un punto x al tempo t. L’equazione di Schrodinger e’ scritta come:
dove psi e’ la funzione d’onda, i e’ l’unita immaginaria, h tagliato una costante fisica, m la massa della particella, V(x) il potenziale in cui e’ immersa la particella e i simboli d/dt e d2/dx2 sono la derivata rispetto al tempo e la derivata seconda rispetto alla posizione rispettivamente. Si rimanda il lettore ad un qualsiasi testo di analisi matematica per la definizione di derivata. In parole molto semplici la derivata di una funzione f rispetto al tempo, df/dt , indica quanto rapidamente f cambia al variare del tempo.
Esprimere il PageRank in termini di una funzione d’onda che obbedisce ad un’equazione simil-Schrödinger permette, secondo questo studio, di localizzare velocemente le pagine con un rank più alto senza utilizzare procedure iterative, chiarendo nel contempo il ruolo della topologia nella diffusione delle informazioni nelle reti complesse.
Nell’equazione riarrangiata del PageRank, il potenziale V dell’equazione di Schrödinger corrisponde alla differenza tra il numero di links entranti Pj e il numero di links uscenti Aj da ogni pagina (i nodi della rete mostrata qui di seguito).
Rappresentazione dell’equazione PageRank e la sua controparte quantistica. Nelle immagini in basso vengono rappresentati il potenziale V e il corrispondente PageRank misurato lungo dei dischi concentrici intorno ad un vertice.
Quando il potenziale V e’ minore di zero (minima energia) la funzione d’onda dell’equazione PageRank e’ localizzata in questa buca di potenziale e il suo valore e’ massimo, indicando che quel nodo, cioè la pagina e’ importante.
Allo stesso modo, quando il potenziale V e’ positivo la funziona d’onda e’ localizzata in questo picco di potenziale e mostra il suo valore più basso, indicando che la pagina non e’ importante.
Questa analogia formale con la fisica quantistica mette a disposizione dello studio del PageRank una serie di strumenti teorici consolidati, sviluppati dai fisici, come la teoria perturbativa.
La differenza di scala tra il mondo delle particelle sub-atomiche ed il Web è enorme ma i ricercatori sono convinti che il loro lavoro potrà portare benefici a tutto quel campo di ricerca che si collega al PageRank e che comprende, per esempio, la propagazione della fiducia nei social network od una più efficiente classificazione delle pagine web.
Curve di livello del potenziale V e della funzione d’onda. Si può vedere come in prossimità del minimo del potenziale corrisponde il massimo della funzione d’onda e quindi dell’importanza della pagina web. Il calcolo e’ stato effettuato sempre considerando i dischi concentrici dell’immagine precedente
