RICERCA ITALIANA     

7 Dicembre 2011

Facebook: amicizie più strette del previsto

Calcolato il grado di separazione tra tutte le coppie di individui su Facebook.
Il risultato è stato raggiunto grazie agli algoritmi sviluppati da un gruppo di ricercatori del Laboratorio di Algoritmica per il Web dell'Università di Milano.
La misurazione compiuta dai ricercatori della Statale, in collaborazione con Facebook, è il più grande esperimento di questo tipo mai eseguito per ordine di grandezza: 65 miliardi è infatti il numero corrente di rapporti di amicizia su Facebook.

Il grado di separazione tra due persone misura in quanti passaggi di conoscenza si può contattare una qualsiasi persona sulla terra. Tra due amici il grado di separazione è zero. Tra due persone che non si conoscono, ma hanno un amico in comune, il grado di separazione è uno, e così via.

L'esperimento dei nostri ricercatori - che ha preso in considerazione 250 milioni di miliardi di coppie possibili - ha stabilito che i gradi sono 3.74, molto meno di quanto facessero pensare i dati del primo esperimento condotto da Stanley Milgram alla fine degli anni Sessanta, ricavati però solo da un centinaio di coppie possibili.

I dati di Milgram avevano consolidato l'idea che sul pianeta ci fossero sei gradi di separazione, ossia che due persone fossero separate in media da non più di sei conoscenze intermedie, i dati dei ricercatori dimostrano oggi che ben il 92% delle coppie su Facebook è separato da non più di 4 gradi.

Per sapere di più abbiamo rivolto una breve intervista al dottor Vigna

Quando è iniziata e quando si è conclusa questa ricerca?
La collaborazione con Facebook è iniziata nel maggio 2011, e continua a tutt'oggi.

Quanti ricercatori ha coinvolto?
Dal nostro lato, tre affiliati al laboratorio di algoritmica per il web dell'Università degli Studi di Milano, e cioè Paolo Boldi, Marco Rosa, e me stesso. Dal lato di Facebook, Lars Backstrom e Johan Ugander. Lars è un dipendente di Facebook, mentre Johan è in visita. Entrambi sono svedesi.

Come è nata l'idea per questo studio?
L'anno scorso Boldi, Rosa e io abbiamo sviluppato un algoritmo per il calcolo della distribuzione delle distanze di un grafo (il nome dei matematici per una "rete") che permette di analizzare grafi di dimensioni enormi. In sostanza, applicato a una rete di amicizie come Facebook consente di stimare la distribuzione delle distanze, e cioè il numero di coppie di persone a una data distanza; qui per distanza intendiamo il minimo numero di rapporti di amicizia da attraversare per passare da una persona all'altra. Il calcolo esatto è fuori discussione per grafi di dimensioni enormi ci vorrebbe semplicemente troppo tempo (anni).

Come vi siete appassionati a questa ricerca?
Il nostro laboratorio sviluppa da anni algoritmi e software per l'analisi di grafi di dimensioni enormi. Applicare il nostro lavoro alla rete sociale più grande esistente (per non dire, poi, oggetto di un film!) era un obiettivo in qualche modo naturale, e una sfida interessante. Ad aprile 2011 si è svolto un importante convegno in India, dove abbiamo presentato un nuovo algoritmo per l'approssimazione della distribuzione delle distanze. Durante il nostro intervento, abbiamo detto che sarebbe stato interessante rispondere alla domanda "quanti sono i gradi di separazione di Facebook?". Lars, che lavora a Facebook, ci ha proposto di collaborare e di scoprire la risposta.

Ci può descrivere, in breve, come si è svolta la ricerca?
Ovviamente non potevamo accedere direttamente ai dati di Facebook. Quindi mandavamo dei programmi (tecnicamente, dei jar Java) che venivano eseguiti eseguiti presso i laboratori di ricerca di Facebook seguendo le nostre istruzioni. Mano a mano che emergevano i risultati, adattavamo gli algoritmi, scrivevamo delle nuove implementazioni in Java e inviavamo le nuove versioni. Nel frattempo dall'altra parte Lars e Johan avevano sezionato il grafo di Facebook in tempo e spazio: nel lavoro forniamo dati sul grafo di Facebook dal 2007 a oggi, e inoltre separatamente per l'Italia, la Svezia e gli Stati Uniti. Per esempio, in Italia i gradi di separazione sono solo tre, il che conferma l'ipotesi originale di Milgram che la co-localizzazione geografica abbia effetti importanti. In questa figura, potete vedere l'evoluzione della distanza media per anno a sui vari sottografi.

Durante la ricerca, è accaduto qualcosa di particolare/sorprendente?
Beh, vedere uscire il numero è stato un momento decisamente esaltante. Ci aspettavamo meno di sei ma non certamente quattro (in realtà, 3,74).

Ci può raccontare un episodio bizzarro avvenuto durante le fasi di ricerca?
La confusione generale sul numero di gradi. Il New York Times ha pubblicato la notizia dicendo che ci sono 4,74 gradi di separazione su Facebook. In realtà i gradi in media sono 3,74, e questo è il motivo per cui il nostro articolo si chiama "Four degrees of separation". 4,74 è la distanza, che è uno in più dei gradi di separazione. Sfortunatamente, i sociologi hanno deciso di contare gli "intermediari" (e quindi se siamo amici il nostro grado di separazione è zero), mentre i matematici e gli informatici contano i "salti" (e quindi se siamo amici la nostra distanza è uno). Questo fatto ha causato un bel po' di confusione. Ma, per essere chiari, non abbiamo arrotondato 4,74 a 4 per difetto; abbiamo arrotondato 3,74 a 4 per eccesso. Per ragioni che non conosco, gli inglesi (la BBC, o il Guardian) hanno riportato il dato corretto.

Questo genere di ricerca può essere applicato anche in altri ambiti?
Certo. Ovunque sia necessario analizzare grafi di dimensioni enormi (per valutarne la distribuzione delle distanze o altro) si possono utilizzare i nostri strumenti. In effetti ci sono dozzine di lavori scientifici pubblicati sugli atti dei convegni e sulle riviste più importanti che hanno utilizzato il nostro software e i nostri dati.

Che applicazioni può avere?
Certamente è utile a Facebook dal punto di vista pubblicitario. Possono sostenere che iniettando una notizia in un punto di Facebook allo scopo di farla spargere in maniera virale, con un numero di passaggi di informazione medio ridicolmente basso l'informazione arriverà a tutti.

Quale può essere una utilità pratica?
A parte questo risultato specifico, calcolare la distribuzione delle distanze è importante per analizzare qualunque grafo. La distribuzione permette di capire quanto velocemente è possibile raggiungere un numero elevato di nodi, e fornisce in modo molto compatto informazioni sul grado di connessione del grafo. È, in qualche senso, la prima cosa da calcolare per studiare un grafo di grandi dimensioni.

Dove si indirizzeranno adesso i vostri studi?
Vorremmo proseguire la collaborazione con Facebook, perché ci sono ancora molte domande interessanti a cui dare una risposta.

Vuole aggiungere qualcos'altro?
Un aspetto divertente è stata la povertà dello hardware con cui abbiamo lavorato: una macchina con 72G di RAM e 24 processori, del costo di poche migliaia di euro (ne abbiamo una più grande nel nostro laboratorio), e neppure un Terabyte di disco (ricordo che un disco da un Terabyte costa oggi un centinaio di euro). Questo ha richiesto non poche modifiche al software, che però lo hanno reso ancora più scalabile. A Facebook hanno puntato molto sui cluster di macchine di piccola dimensione, per cui sono a corto di macchine di una certa stazza.