WWW: la fisica accelera anche il pagerank

Fri, 10/12/2012 - 20:13 -- admin

È stato pubblicato sul numero di novembre 2009 di Europhysics Letters "PageRank equation and localization in the WWW", paper risultato dallo studio congiunto di Linkalab e altri importanti istituti di ricerca che apre interessanti prospettive sullo studio della "forma del web". I risultati della ricerca dimostrano che in un network il PageRank (l'algoritmo di Google che classifica l'autorevolezza di ogni pagina in base a quantità e tipo dei link che portano ad essa) può essere rappresentato come la soluzione di un'equazione differenziale discretizzata su un grafo orientato, proprio come quello che rappresenta il world wide web. Sfruttando la relazione formale tra questa rappresentazione e l'equazione di Schrödinger, si possono interpretare la formazione di hub e altri fenomeni collegati come si studierebbe un fenomeno di localizzazione di una funzione d'onda in presenza di disordine.

Nel caso del web il disordine è dato dalla differenza tra i link da e verso le diverse pagine. Questa struttura disegna una funzione d'onda e crea un potenziale: ciò consente di localizzare direttamente le pagine con alto PageRank come minimi del potenziale.

A partire dalla natura ondulatoria delle particelle, l’equazione di Schrödinger può descrivere un sistema fisico e la sua evoluzione nel tempo grazie alla funzione d’onda ψ. Secondo lo studio appena pubblicato, esprimere il PageRank secondo una funzione d’onda che obbedisce a un’equazione simile a quella di Schrödinger permette di localizzare più velocemente le pagine con un ranking più alto, perchè si evita di adottare procedure iterative.

L'equazione di Schrödinger è uno strumento analitico molto diffuso, per il quale esiste un apparato teorico e operativo molto ampio: sembrerebbe dunque possibile applicare strumenti più potenti alla fisica delle reti e ipotizzare connessioni interdisciplinari inedite. Tra le possibili applicazioni, basterà citare il web, il traffico, le reti sociali e quelle biologiche.

Gli autori dello studio sono: Nicola Perra e Alessandro Chessa per il Dipartimento di Fisica dell'Università di Cagliari e Linkalab, Vinko Zlatic per il Centre SMC CNR-INFM e la Theoretical Physics Division del Rudjer Boskovic Institute di Zagabria, Claudio Conti per il Centre SOFT INFM-CNR e l'Istitute for Complex Systems ISC-CNR, Debora Donato (Yahoo! Research a Barcellona) e Guido Caldarelli (del Centre SMC CNR-INFM, Istitute for Complex Systems ISC-CNR e per Linkalab). La pubblicazione sarà interamente disponibile online sul sito della rivista ancora per qualche giorno.

Guido Caldarelli è chief scientist di Linkalab. Ecco come commenta la ricerca appena pubblicata.

Può spiegarci cosa significa che il risultato della ricerca "chiarisce il ruolo della topologia nella diffusione delle informazioni nelle reti complesse"?

In un grafo possiamo decidere quali vertici sono connessi fra loro e come sono disposte queste connessioni: questa informazione costituisce la "topologia" del grafo. Nell'articolo mettiamo in relazione il successo di una pagina (il PageRank) con la sua topologia, cioè la "forma" delle sue connessioni. In passato è stato evidenziato euristicamente che il grado entrante di una pagina e il suo PageRank sono correlati: qui forniamo una spiegazione analitica di questo fenomeno.

Può illustrarci brevemente alcuni esempi pratici di applicazioni di questa scoperta a diverse discipline di studio e ricerca?

Tramite il nostro formalismo, in alcuni "casi particolari" si può calcolare il PageRank più velocemente. Inoltre possiamo identificare delle comunità all'interno del sistema: questa è la linea di ricerca attualmente presente in Linkalab grazie ad Alessandro Chessa, Vincenzo De Leo e Nicola Perra. Crediamo che il PageRank abbia un ruolo anche nell'individuazione dei vertici più importanti nei sistemi biologici.

La "somiglianza" tra il funzionamento del web e della materia va considerato come una semplice esemplificazione o testimonia una affinità più concreta?

Si tratta di due fenomeni che hanno una rappresentazione matematica simile: possiamo quindi estendere i risultati già noti nel campo della fisica quantistica al campo delle reti complesse.

 

Riferimenti

epljournal.edpsciences.org (vol. 88/4) 
L'infografica di Sabrina Loi che illustra lo studio sul PageRank [file .pdf]

Article images: 
physics accelerating pagerank