Graphs and NetworksGraphs in Everyday Life

Durante questo corso, abbiamo visto molte applicazioni della teoria dei grafi, anche se alcune di esse erano un po’ artificiali. Si scopre, tuttavia, che i grafi sono al centro di molti oggetti e concetti quotidiani.

Internet, per esempio, è un vasto grafo virtuale. Ogni vertice è una pagina web individuale, e ogni bordo significa che c’è un collegamento ipertestuale tra due pagine. Notate che i link vanno solo in una direzione. Quindi questo grafo è diretto a più linee ed è molto, molto grande.

Alcuni siti web, come Wikipedia o Facebook, contengono molti link in entrata, mentre molti siti più piccoli possono contenere pochi link in entrata. Questo è il concetto di base utilizzato da Google per ordinare i risultati di ricerca.

I siti web con più link in entrata tendono ad essere di qualità superiore e dovrebbero apparire in cima ai risultati di ricerca. Per esempio, quando si cerca “Londra”, i siti ufficiali di informazioni turistiche vengono mostrati prima dei piccoli negozi londinesi o dei blog di persone che vivono a Londra. Questa semplice idea di teoria dei grafi, l’algoritmo Page Rank, ha reso Google significativamente migliore di altri motori di ricerca.

Internet è la più grande rete mai creata dall’umanità. Questa immagine mostra una piccolissima parte di tutti i server connessi a Internet:

© LyonLabs, LLC e Barrett Lyon, 2014

Mentre i siti web e gli hyperlink formano un grafico virtuale, c’è anche la rete fisica, che comprende computer, server, router, linee telefoniche e cavi.

Ogni volta che si fa una chiamata o si carica un sito web, gli operatori di rete devono trovare un modo per collegare il mittente e il destinatario, senza superare la capacità di ogni cavo o connessione. La teoria dei grafici e la probabilità aiutano a garantire un servizio affidabile, per esempio trovando deviazioni quando una particolare connessione è occupata.

I grafici hanno anche un ruolo importante nei trasporti e nella navigazione. Tutte le reti di voli, treni e metropolitane formano grafici che possono essere usati per creare orari efficaci. Uno dei grafici più riconoscibili è la mappa della metropolitana di Londra:

Tutte le strade e le autostrade formano anche una vasta rete, che viene utilizzata da servizi di navigazione come Google Maps per elaborare il percorso più breve tra due punti dati.

In futuro, i sistemi di trasporto intelligenti ridurranno la congestione e gli incidenti instradando le auto in modo più efficiente, utilizzando i dati di localizzazione raccolti da smartphone e auto autonome. Questo permetterebbe di risparmiare milioni di ore perse sulla strada ogni anno, di ridurre significativamente l’inquinamento e di permettere ai servizi di emergenza di viaggiare più velocemente.

Questa immagine mostra la rete di volo delle compagnie aeree commerciali nel nord Europa.

Ci sono innumerevoli altri grafici nella scienza, nell’ingegneria o nella vita quotidiana:

I collegamenti tra gli atomi delle molecole e i reticoli di cristallo formano un grafico.

La diffusione di malattie ed epidemie può essere modellata utilizzando una rete.

In biologia, gli alberi evolutivi che mostrano l’ascendenza delle specie formano un grafico.

I vari componenti dei circuiti elettrici e dei chip dei computer formano una rete.

La struttura grammaticale delle lingue può essere modellata usando grafi, per esempio per creare algoritmi di traduzione.

I grafi hanno anche molte applicazioni nella probabilità, nella teoria dei giochi e nella matematica finanziaria.

Reti sociali

Finalmente, pensiamo a un esempio particolarmente interessante di grafi esistenti nella vita quotidiana: i social media. Qui, i vertici rappresentano le reti di persone e i bordi rappresentano le amicizie, i like, le sottoscrizioni o i followers.

Quando iniziamo a disegnare grafici sui social media, possiamo chiaramente vedere certi gruppi di amici comuni, che possono essere andati alla stessa scuola o vivere nella stessa città. Possiamo anche determinare la centralità di una persona, che dipende da quanto è connesso un top e può essere un indicatore della popolarità di una persona sui social network.

Al 2014, Facebook aveva 1,4 miliardi di utenti attivi e oltre 200 miliardi di amicizie. La metà degli utenti di Facebook ha più di 200 amici, e dato che la maggior parte dei nostri amici ha lo stesso numero di amici, potremmo facilmente avere decine di migliaia di amici di amici.

Ora una domanda eccitante sarebbe: se scegli due utenti di Facebook a caso, quanti “link di amicizia” devi seguire per andare da uno all’altro? Per esempio, la distanza tra amici è , la distanza tra amici di amici è , ecc.

Secondo uno studio condotto da Facebook nel 2016, si è in media connessi a chiunque su Facebook attraverso al massimo 3,57 persone: si dice che ci sono 3,57 gradi di separazione.

In altre parole, se scegliete uno qualsiasi dei miliardi di utenti di Facebook nel mondo, essi avranno un amico di un amico che conosce un amico di un vostro amico. E questo include celebrità, politici o reali…

Visualizzazione geografica di tutte le amicizie su Facebook nel 2010.

Nel 1929, quando lo scrittore ungherese Frigyes Karinthy propose per la prima volta l’idea dei “sei gradi di separazione”, Internet e i social media non esistevano, ma il mondo aveva già iniziato a diventare più interconnesso.

Nel 1967, Stanley Milgram condusse un primo esperimento empirico in cui fu chiesto a 296 partecipanti del Nebraska e del Kansas di consegnare una lettera a qualcuno che viveva a Boston, Massachusetts. Tutti dovevano scegliere un amico a cui inviare la lettera, che poi sceglieva un altro amico. Ad ogni passo, la lettera si avvicinava a Boston. Milgram trovò che c’erano in media solo 5,2 amici intermedi – 5,2 gradi di separazione.

Oggi, ognuno di noi è parte di innumerevoli grafi invisibili, che sono alla base delle nostre interazioni sociali, dei viaggi, di Internet e della tecnologia, della scienza e di molto altro ancora.

Lascia un commento

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