L'algoritmo del gossip

In pochi secondi nei pc di tutto il mondo.
La Sapienza studia la velocità del pettegolezzo

29 marzo 2010. - Quel titolo che in apparenza può sembrare frivolo, e che invece nasconde una ricerca scientifica serissima. Tanto seria da aver ottenuto importanti riconoscimenti a livello internazionale, a partire dalla prima presentazione nell'ambito del Soda 2010 (Symposium on Discrete Algorithms) appuntamento clou sulla ricerca informatica mondiale che si è svolto ad Austin, Texas, a gennaio. Ed eccolo, il curioso titolo dello studio: Rumours spreading and graph conductance, ovvero «Teorema della diffusione del gossip e conduttanza del grafo», complessa formula matematica grazie alla quale tre studiosi dell'università La Sapienza di Roma riescono ora a calcolare con esattezza la velocità di propagazione del pettegolezzo in ogni rete sociale tecnologica composta anche da milioni di «nodi».

Si tratti di Twitter, di Facebook o del Web in generale. Una velocità, quella del gossip, che in pochissimi secondi, in una rete tipo internet, può raggiungere anche l'intero Web. A firmare lo studio Alessandro Panconesi, professore ordinario e direttore del dipartimento di Informatica dell'ateneo romano, insieme con due suoi giovani dottorandi, Flavio Chierichetti e Silvio Lattanzi: «Ragazzi di primissimo livello che da tempo — spiega Panconesi — stanno ricevendo maxiofferte da mezzo mondo. Lattanzi andrà a Google. Chierichetti ha invece scelto l'ateneo di Cornell, top della ricerca mondiale nel settore».

IL TEOREMA DEL PETTEGOLEZZO - Teorema del pettegolezzo: del tipo io dico una cosa a te, tu la dici a un altro, che a sua volta lo dice a n-persone? «Beh, semplificando molto è così. Ma quel che noi abbiamo fatto non è inventare l'algoritmo del gossip, noto da tempo e assai banale. Quanto piuttosto determinare velocità e modalità con cui il pettegolezzo si diffonde in una rete sociale di qualsiasi dimensione. La materia è studiata da decenni anche dai sociologi, un qualcosa di vagamente imparentato alla nota teoria dei sei gradi di separazione di Stanley Milgram, ma ora estesa a reti di dimensioni impensabili negli anni Sessanta».

La ricerca ha anche importanti applicazioni industriali nei servizi web. «Va spiegato — precisa Panconesi — che l'informazione di cui parliamo, il pettegolezzo, è così definita perché quella è la modalità di diffusione sul web, o altra rete, di un'informazione qualsiasi inizialmente distribuita in maniera informale. Gossip a parte insomma, la formula concerne anche informazioni d'altro tipo. Utili, ad esempio un segnale d'allarme. O dannose tipo un virus, non solo digitale». Che la velocità di trasmissione del gossip interessi l'industria lo prova il fatto che lo studio è stato finanziato da privati: Yahoo Research e Ibm, che ha premiato Panconesi con il premio «Faculty Award Ibm». Ma è anche un altro il motivo per cui la formula ha fatto il giro del mondo, diffondendosi rapidamente con le stesse modalità studiate dal trio (twitter, facebook, blog...): si tratta degli inediti «s-ringraziamenti» (unacknowledgements) al Miur e pubblicati in calce al lavoro: «Questa ricerca in apparenza è finanziata dal ministero italiano per l'Università nell'ambito del programma Firb.

Ma il ministero non ha pagato quanto dovuto né si sa se lo farà mai». A giugno la versione migliorata del lavoro sarà presentata anche a «Stoc 2010» (Symposium on Theory of Computing), il più importante appuntamento al mondo per la teoria degli algoritmi, convegno per il quale sono stati selezionati anche altri due studi di atenei romani (di Paul Wollan, americano che insegna alla Sapienza, e di Fabrizio Grandoni, Tor Vergata, che si è già aggiudicato il premio miglior lavoro del congresso): «Non è un caso — dice Panconesi —. Nonostante una politica ministeriale per cui ci ridono dietro nel mondo, l'Italia, Roma in particolare, si esprimono ai vertici anche in altri settori della disciplina, tipo sicurezza informatica e Reti. Ora nel nostro dipartimento abbiamo progetti, uno di grande importanza sulla sicurezza dell'infrastruttura internet dell'Italia, finanziati con milioni di euro. Ma messi a disposizione da Ue o privati».

(Edoardo Sassi / corriere.it)

Share