L’Avvento dei Social Media: La Teoria dei Tre Gradi e Mezzo di Separazione

Articolo Originale di: Smriti Bhagat , Moira Burke , Carlos Diuk , Ismail Onur Filiz , Sergey Edunov




Fonte: Research Facebook

“Ho letto da qualche parte che tutti su questo pianeta sono separati solo da altre sei persone. Sei gradi di separazione. Tra noi e tutti gli altri su questo pianeta. Il presidente degli Stati Uniti. Un gondoliere a Venezia. Inserisci i nomi. . . . Come ogni persona è una nuova porta, che si apre in altri mondi. Sei gradi di separazione tra me e tutti gli altri su questo pianeta. Ma per trovare le giuste sei persone. . . “ – John Guare, Six Degrees of Separation (1990)

Quanto è connesso il mondo? I drammaturghi [1], i poeti [2] e gli scienziati [3] hanno proposto che tutti gli abitanti del pianeta siano collegati a tutti da altre sei persone. In onore del Friends Day, abbiamo scricchiolato il grafico degli amici di Facebook e abbiamo stabilito che il numero è 3.57. Ogni persona nel mondo (almeno tra 1,59 miliardi di persone attive su Facebook) è collegata a ogni altra persona da una media di tre persone e mezzo. La distanza media che osserviamo è 4,57, corrispondente a 3,57 intermediari o “gradi di separazione”. Negli Stati Uniti, le persone sono collegate tra loro in media di 3,46 gradi.

I nostri “gradi di separazione” collettivi si sono ridotti negli ultimi cinque anni. Nel 2011, i ricercatori della Cornell, l’Università degli Studi di Milano e Facebook hanno calcolato la media tra i 721 milioni di persone che utilizzavano il sito, e hanno scoperto che era 3,74 [4,5]. Ora, con il doppio delle persone che utilizzano il sito, siamo diventati più interconnessi, riducendo così la distanza tra due persone nel mondo.




Calcolare questo numero su miliardi di persone e centinaia di miliardi di connessioni di amicizia è impegnativo; utilizziamo le tecniche statistiche descritte di seguito per stimare con precisione la distanza in base a dati aggregati e deidentificati.

Alcuni dipendenti di Facebook

post00006_image0002

Mark Zuckerberg 
3.17 gradi di separazione




post00006_image0003

Sheryl Sandberg 
2.92 gradi di separazione

La maggior parte delle persone su Facebook ha una media tra 2,9 e 4,2 gradi di separazione. La Figura 1 (sotto) mostra la distribuzione delle medie per ogni persona.




post00006_image0004

Figura 1. Stima media dei gradi di separazione tra tutte le persone su Facebook. La persona media è collegata a ogni altra persona in media di 3,57 passi. La maggior parte delle persone ha una media tra 3 e 4 passi.

Calcolo dei gradi di separazione in scala

Calcolare i gradi di separazione in una rete con centinaia di miliardi di spigoli è un compito monumentale, perché il numero di persone raggiunte cresce molto rapidamente con il grado di separazione.

Immagina una persona con 100 amici. Se ciascuno dei suoi amici ha anche 100 amici, il numero di amici di amici sarà di 10.000. Se ciascuno di questi amici-amici ha anche 100 amici, il numero di amici-amici-amici sarà di 1.000.000. Alcuni di questi amici potrebbero sovrapporsi, quindi è necessario filtrare le connessioni univoche. Siamo solo a due hop di distanza e il numero è già grande. In realtà questo numero cresce ancora più velocemente poiché la maggior parte delle persone su Facebook ha più di 100 amici. Abbiamo anche bisogno di fare questo calcolo 1,6 miliardi di volte; cioè, per ogni persona su Facebook.




Invece di calcolarlo esattamente, ci siamo basati su algoritmi statistici sviluppati da Kang e altri [6-8] per stimare le distanze con grande precisione, trovando fondamentalmente il numero approssimativo di persone all’interno di 1, 2, 3 (e così via) di luppolo lontano da un fonte.

Più precisamente, per ogni numero di hop stimiamo il numero di persone distinte che puoi raggiungere da ogni fonte. Questa stima può essere eseguita in modo efficiente utilizzando l’algoritmo Flajolet-Martin [9]. Come funziona? Immagina di avere un gruppo di persone e vuoi contare quante sono uniche. Per prima cosa assegni a ogni persona un intero casuale; chiamiamolo hash . Circa 1/2 delle persone avrà un hash pari: la rappresentazione binaria dell’hash terminerà con 0. Circa 1/4 delle persone avrà un hash divisibile per 4; cioè, la rappresentazione binaria termina con 00. In generale, 1/2 nle persone avranno la rappresentazione binaria del loro hash finale con n zeri. Ora, possiamo invertire questo e cercare di contare quante persone diverse abbiamo leggendo i loro valori hash uno per uno. Per fare ciò, monitoriamo il maggior numero di zeri che abbiamo visto. Intuitivamente, se ci fossero n zeri, possiamo aspettarci che il set abbia c * 2 n numeri univoci, dove c è un po ‘costante. Per una migliore precisione possiamo fare questo calcolo più volte con diversi valori hash.

Questo algoritmo si adatta bene al nostro problema: trovi il maggior numero di zeri tra gli hash di tutti gli amici. Utilizzando un’operazione OR bit a bit sull’hash, questo processo può essere ripetuto in modo ricorsivo per stimare il numero di amici-amici unici e quindi amici-amici-amici. Abbiamo usato Apache Giraph [10] per eseguire questo calcolo sull’intero grafico di amicizia di Facebook. Nella nostra implementazione, ad ogni passaggio ogni persona invia un valore hash bit a bit per tutti i suoi amici. Lo facciamo in modo ricorsivo e usiamo la matematica di Flajolet-Martin per stimare il numero di amici unici per ogni grado di separazione.




In sintesi, scopriamo che il mondo è più strettamente connesso di quanto si possa pensare.

Di Sergey Edunov (3.46), Carlos Greg Diuk (3.16), Ismail Onur Filiz (3.33), Smriti Bhagat (3.32) e Moira Burke (3.35)

Immagine di copertina di Diana MacLean (3.26)

Riferimenti

[1] Sei gradi di separazione (gioco) – Wikipedia
[2] Frigyes Karinthy – Wikipedia
[3] Esperimento di piccolo mondo – Wikipedia
[4] Backstrom, L., Boldi, P., Rosa, M., Ugander, J. , & Vigna, S. (2012). Quattro gradi di separazione . Atti del 4 ° Convegno annuale ACM Web Science , 33-42.
[5] Ugander, J., Karrer, B., Backstrom, L., & Marlow, C. (2011). L’anatomia del grafico sociale di Facebook .
[6] Kang, U., Papadimitriou, S., Sun, J., Tong H. (2011). Centralità nelle grandi reti: algoritmi e osservazioni . Atti della conferenza internazionale SIAM sul data mining .
[7] Palmer, C., Gibbons, P., & Faloutsos, C. (2002). ANF: uno strumento veloce e scalabile per il data mining in enormi grafici . Atti dell’ottava conferenza internazionale ACM SIGKDD sulla scoperta della conoscenza e il data mining . 81-90.
[8] Cohen, E. (1997) Quadro di stima delle dimensioni con applicazioni alla chiusura transitiva e alla raggiungibilità . Journal of Computer and System Sciences 55 (3): 441-453.
[9] Algoritmo Flajolet-Martin
[10] http://giraph.apache.org/

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *