Introduzione alla Network Science

I network (o reti) sono uno strumento potente ed efficace per rappresentare la realtà che ci circonda e sono infatti presenti in quasi ogni aspetto della nostra vita. Amici, parenti, il Web, le strade di una città… tutto può essere modellato sotto forma di network. Lo scopo di questa rappresentazione è quello di studiare un sistema cercando di catturarne la sua complessità e le relative cause. In generale, un network è la semplice descrizione di un insieme composto da entità interconnesse, che chiamiamo nodi, e le loro connessioni/relazioni, che chiamiamo link. I nodi possono rappresentare ogni genere di entità: persone, luoghi, siti web, cellule, etc. Le relazioni a loro volta possono esprimere ogni tipo di interazione/scambio/flusso che avviene fra due entità, quindi pagamenti, scambi di messaggi, like su Facebook, etc.

Nota: In questo articolo i social network vanno intesi come reti sociali e non come i siti di social networking come Facebook e Twitter.

I network sociali sono un particolare tipo di network dove i nodi sono persone interconnesse da un qualche tipo di relazione. Ci sono tantissimi tipi di social network, al punto che questa è la categoria di network più studiata in assoluto. Per esempio la sociologia, il ramo da cui è partito lo studio delle reti sociali, cerca di stabilire delle regole emergenti dal comportamento collettivo degli individui.  Nell’ambito della medicina si può studiare la propagazione di malattie attraverso una rete sociale, in economia si studia come il comportamento di un individuo influenza quello di un altro sulla base di meccanismi di incentivi ed aspettative degli altri. Nel campo della ricerca i social network vengono utilizzati per studiare gli autori più influenti e come hanno collaborato fra loro nello studio di un determinato argomento.

La complessità delle connessioni della società moderna, data da fenomeni come internet, crisi finanziarie o epidemie è data dal comportamento aggregato di gruppi di persone le cui azioni hanno conseguenze sul comportamento di tutti gli altri. Il crescente interesse verso lo studio di tale complessità ha reso la Social Network Analysis uno degli strumenti di visualizzazione e rappresentazione dei sistemi complessi più utilizzati.

Teoria dei Grafi

La Social Network Analysis ed in generale tutta la Network Science si basa sui concetti chiave della teoria dei grafi di nodo e legame, andando ad ampliare questa branca della matematica con una serie di termini e metriche propri, dati dallo sviluppo autonomo di questo campo di ricerca.

L’avvento della teoria dei grafi si riconduce a un aneddoto del 1736 della città Prussiana di Königsberg, città natale di Immanuel Kant e Leonhard Euler, per noi Eulero. Eulero si trovò ad affrontare un problema matematico legato alla città di Königsberg, la quale era divisa ai tempi in quattro settori dal fiume Pregel, connessi tra loro da sette ponti. Solo cinque di questi sono sopravvissuti ai bombardamenti della Seconda guerra mondiale e allo stesso modo molti edifici sono stati demoliti. Il problema con cui si cimentò Eulero, irrisolto fino a quel momento, era quello di collegare tutti e sette i ponti potendo passare solo una volta su ciascuno di questi.

Eulero formalizzò il problema ricorrendo a un grafo i cui nodi erano i quattro settori della città, e i collegamenti erano i ponti. Dimostrò così che un tale percorso esiste solo se tutti i nodi hanno grado (numero di link) pari, tranne la partenza e l’arrivo. Questo tipo di percorso, rinominato poi Eulerian path in suo onore, non è effettivamente possibile in questo sistema in quanto ognuno dei quattro nodi ha un numero dispari di connessioni. La vera novità di questo approccio fu l’aver formalizzato in forma topologica il problema, andando a definire questo tipo di percorso come una proprietà intrinseca del grafo.

La forza dei legami deboli e la Small-World property

La teoria della “forza dei legami deboli” nasce da uno studio di Mark Granovetter degli anni 60 diventato poi un classico della sociologia. Granovetter, attraverso una serie di interviste, andò a studiare come le persone che avevano recentemente cambiato mestiere a Boston fossero venute a conoscenza della nuova opportunità. La maggior parte di queste persone erano immigrati irlandesi, i quali erano soliti trascorrere una buona quantità di tempo nei pub. Il lavoro ed in particolare quello edilizio, settore principale di queste persone, era molto instabile portando a frequenti passaggi dallo stato di occupazione a quello di disoccupazione. L’obiettivo iniziale della ricerca era di capire il ruolo delle conversazioni nei pub nella ricerca del nuovo lavoro.  Scoprì che molte persone avevano trovato il nuovo lavoro attraverso i contatti personali e pertanto decise di soffermarsi proprio su questi. Emerse dalla sua ricerca che questi contatti erano perlopiù conoscenti piuttosto che amici stretti. Solo il 30% degli intervistati aveva trovato lavoro attraverso i contatti più stretti. 

Fonte: https://www.nature.com/articles/srep05739/figures/2

Da qui la distinzione tra legami forti e deboli. I legami forti erano amici e parenti, mentre i legami deboli semplici conoscenti. Granovetter teorizzò quindi che i legami forti sono maggiormente disposti a fornire un supporto emotivo, ma appartenendo alla stessa cerchia di chi in questo caso sta cercando lavoro, hanno meno possibilità di fornire informazioni che non conosciamo. I legami deboli a differenza, appartenendo a cerchie da noi distanti sono in contatto con realtà a noi sconosciute ed hanno per questo accesso a informazioni nuove. Le implicazioni di questo studio sono vastissime e tuttora oggetto di studio. Il perché i social media siano diventati uno strumento così potente è riconducibile proprio al concetto di legame debole. Essenzialmente, i social media non fanno altro che mantenere ed amplificare i legami deboli, definiti in questo caso come legami sociali che non richiedono alcun attaccamento emotivo, necessità di comunicare o tempo da dedicare. Nonostante questo, risultano estremamente potenti in quanto fungono da canali per il passaggio di informazioni tra persone distanti sia in termini fisici che sociali (es reddito, cultura, etc). Quando due persone comunicano attraverso un legame debole, l'informazione che passa attraverso di esso è di solito nuova, e proviene da un diverso punto di vista.

Dal punto di vista dei network i legami forti (come quelli tra coniugi e amici intimi) tendono a riunire i nodi in cluster stretti e densamente interconnessi. All’interno di questi cluster si sviluppa una conoscenza specifica ma non si generano conoscenze “distanti” a livello di contenuti. Poiché diverse nicchie conservano diversi tipi di conoscenza, sono i collegamenti tra i questi sub-network a permettere la condivisione. Tali collegamenti sono chiamati ponti. Granovetter ha quindi capito che nelle reti sociali i legami che tengono insieme la rete stessa sono, paradossalmente, i legami "deboli".

La famosa Teoria dei sei gradi di separazione si basa proprio su questo concetto, ovvero che attraverso i semplici legami deboli due persone qualunque del globo sono in grado di entrare in contatto mediante un massimo di sei persone. L’esperimento fu condotto negli anni 60 da Stanley Milgram, data a cui risale la prima prova empirica dell’esistenza dei cosiddetti network small world. L’idea era quella di misurare la distanza sociale fra sconosciuti. Furono quindi selezionate 160 persone in Kansas e Nebraska per mandare una lettera a una persona selezionata in Massachussets. Ogni persona doveva mandare la lettera alla persona di sua conoscenza che reputava più adatta a raggiungere il destinatario. In questo caso solo il 26% di lettere arrivarono a destinazione correttamente, mostrando però che il numero medio di intermediari erano di poco superiori a 6. L’esperimento fu ripetuto nel 2003 usando però le email. Anche in questo caso si mise in luce il fatto che il path medio in termini di persone erano 5-7 individui. La maggior parte dei network del mondo reale hanno il percorso critico (il più veloce) medio molto breve, secondo quella che viene definita small word property. Questa proprietà rende le reti molto efficienti in termini di velocità di propagazione delle informazioni.

Fonte: https://mathspig.wordpress.com/tag/6-degrees-of-separation-explained/

Clustering

Una caratteristica che si osserva nelle reti sociali è che gli individui tendono ad aggregarsi in comunità, dette cluster. Questa proprietà, già nota nella sociologia come transitività, è stata poi ripresa nella network science con il nome di clustering. Come tale, questo coefficiente esprime la misura di quanti amici di un individuo sono a loro volta amici fra loro. A livello di rete si calcola come frazione di tutti i possibili triangoli (o triadi) che esistono nella rete, mentre a livello di singolo nodo corrisponde alla frazione di tutti i possibili triangoli che contengono il nodo in esame.

Una delle modalità per cui si formano cluster è quella della vicinanza a un altro nodo. Anche questo concetto è ampiamente trattato nella Social Network Analysis, e prende il nome di assortatività. Essa esprime la preferenza per un nodo ad interagire con un altro nodo avente caratteristiche simili. Nel caso delle reti sociali queste caratteristiche possono essere sesso, età, luogo, argomenti di interesse e così via. Alcuni ricercatori hanno visto che è possibile stabilire con una certa accuratezza l’orientamento politico di un individuo anche se non presente nel suo profilo guardando le caratteristiche della sua cerchia di amicizie. Una regola empirica è che se due persone sono simili in qualche modo, è più probabile che si selezionino a vicenda e diventino due nodi interconnessi. A questo aspetto si lega la teoria delle bolle di filtraggio di Eli Pariser che sarebbe interessante approfondire, ma questo esula dal tema dell’articolo.

Watts–Strogatz Model

Per studiare come emergono le caratteristiche di un network, come la small world property o il clustering, si utilizzano degli algoritmi di simulazione che generano dei modelli. Questi modelli vengono poi comparati con i dati reali per capirne le differenze e studiarne i meccanismi.

Il modello Watts–Strogatz (1998) è un network avente proprietà small world che allo stesso tempo possiede un buon coefficiente di clustering. Può essere generato in modo sperimentale risultando in un network dove la maggior parte dei nodi sono collegati a un numero relativamente ristretto di vicini in maniera piuttosto regolare, con alcune eccezioni dati da legami deboli con nodi distanti. Watts e Strogatz notarono che nel mondo reale non si riscontravano pressoché in nessuna situazione né network regolari, dove tutti i nodi sono strettamente legati ai propri vicini, né network completamente randomici, dove invece i collegamenti fra nodi non seguono nessuna logica particolare. Osservarono infatti che la realtà circostante era sempre una via di mezzo fra questi due tipi di network, ovvero una forte aggregazione in cluster tipica di un network regolare e allo stesso tempo una forte propensione alla propagazione di informazioni secondo la small world property, tipica invece di un random network. La soluzione che proposero è quindi l’interpolazione di questi due estremi.

L’algoritmo di generazione di un modello Watts–Strogatz parte da un network regolare dove tutti i nodi sono connessi ai propri vicini, e in modo randomico elimina alcuni di questi collegamenti andandoli a sostituire con collegamenti a nodi più distanti. In questo modo le proprietà topologiche locali fra nodi vicini rimangono intatte, ma si permette ai legami deboli di fungere da collegamento con nodi anche molto distanti.

. 

Fonte: https://www.nature.com/articles/30918

Il problema delle reti Watts-Strogatz è dato dall’inaccuratezza nella distribuzione dei gradi (il numero di collegamenti di ciascun nodo).  Il numero di vicini di un nodo è infatti circa lo stesso per tutti i nodi, e differisce leggermente dal valore medio, seguendo così una distribuzione di Poisson. Risulta così un network molto omogeneo, che non rispecchia però la distribuzione delle reti reali. Nel mondo reale si assiste infatti a una fortissima disuguaglianza fra il grado dei nodi, secondo quella che viene definita “legge di potenza”, ovvero ci sono molti nodi con poche connessioni e pochi nodi con molte connessioni. Barabasi e Albert hanno considerato questo aspetto andando a creare un modello che si basa sulla legge di potenza.  Una distribuzione che segue la legge di potenza è denominata power law distribution, distribuzione a invarianza di scala (scale-free distribution) o anche distribuzione di Pareto. La peculiarità di questo tipo di distribuzioni sta proprio nell'assenza di una scala caratteristica dei fenomeni. 

Fonte: http://networksciencebook.com/chapter/4#hubs

Scale free and Barabasi-Albert Model

Il modello Barabasi-Albert (1999) si discosta dal modello Watts-Strogatz aggiungendo realismo nel meccanismo di clustering dei nuovi nodi. Mentre il modello Watts-Strogatz parte da un set di nodi dall’inizio alla fine, il Barabasi-Albert aggiunge i nodi uno per volta rendendo il modello dinamico.

L’idea alla base è di generare una rete secondo una progressiva aggregazione di nodi seguendo una logica di preferenza verso i nodi più grandi, chiamata attaccamento preferenziale. In altre parole, quando si aggiungono nuovi nodi, questi andranno a connettersi tendenzialmente a nodi già largamente interconnessi, che vengono definiti hub.

Fonte: https://makeagif.com/i/0Ccn3L

Questo principio viene anche definito come “rich get richer”, ovvero i nodi più grandi tendono a diventare ancora più grandi. La probabilità che un nuovo nodo si colleghi a uno vecchio è proporzionale al grado del vecchio nodo. Per esempio un nodo con grado 10 è 10 volte più probabile che venga raggiunto da un nuovo nodo rispetto a un altro nodo avente grado 1. La proprietà di small world viene in questo caso garantita proprio dagli hub, che fungono da ponte principale fra coppie di nodi non collegati.

Fonte: https://en.wikipedia.org/wiki/Mediation-driven_attachment_model

Questo tipo di modello trova un ampissimo riscontro nel mondo reale, come per esempio le pagine Web. Numerosi studi hanno dimostrato che più un sito è citato, ossia possiede più hyperlink, e più è probabile che verrà citato nuovamente e viceversa. La causa sottostante a questo fenomeno è spiegata dal fatto che più hyperlink ha un sito web e più è visibile, di conseguenza è più probabile che il sito riceva altri hyperlink.  Questo stesso meccanismo si manifesta allo stesso modo nella legge di Pareto, per cui la ricchezza tende a concentrarsi nelle mani di pochi individui molto ricchi mentre è molto scarsa nel resto della popolazione (il 20% della popolazione possiede l’80% delle risorse, oppure il 20% delle parole di una lingua compongono l’80% del parlato).

Misure di centralità

Spostando l’analisi a livello di singolo nodo all’interno della rete, la SNA permette di studiare le relazioni di ogni attore nella rete mostrandone le gerarchie e fornendo un quadro per spiegare la struttura e l'evoluzione dei singoli nodi e dei gruppi di nodi. Le reti sociali sono sistemi complessi e come tali necessitano di una moltitudine di metriche e strumenti di analisi. Le principali sono le centralità, ma vi sono anche la distribuzione dei gradi, la topologia della rete locale, la struttura della comunità e l'evoluzione della rete.

La prima domanda che potrebbe sorgere analizzando una rete è: chi è il più importante?

Ovviamente la risposta è dipende, e qui andremo a spiegare brevemente perché.

Generalmente sono le misure di centralità a rispondere a questa domanda. Le misure di centralità sono usate per calcolare l’importanza di un individuo all’interno del network, tuttavia sono vari i criteri di importanza: potere, l'influenza, o altre caratteristiche individuali delle persone. Per questo motivo ci sono diverse misure di centralità della rete. Analizzeremo le 4 principali.

Degree centrality

Se si vuole misurare il numero di connessioni che ha un individuo allora la degree centrality fa al caso nostro. Su Facebook per esempio corrisponderebbe al numero dei nostri amici. E’ logico pensare che più una persona abbia collegamenti e più abbia influenza sulle altre persone. Ma non è necessariamente così.  Scott Adams, il creatore del fumetto Dilbert, sostiene che il potere di una persona è inversamente proporzionale al numero di chiavi nel suo portachiavi. Un custode ha le chiavi di tutti gli uffici e nessun potere. L'amministratore delegato non ha bisogno di una chiave, c’è sempre qualcuno ad aprirgli la porta. Effettivamente sono molti i casi in cui una persona di potere ha relativamente pochi contatti e per questo sono necessarie altre metriche di centralità.

Una breve digressione può essere fatta riguardo le due sottomisure della degree-centrality date dal numero di link in entrata o in uscita di un nodo, ovvero centralità in-degree e out-degree. Questo aspetto è interessante perché viene usato per misurare il livello di fiducia verso un individuo della rete. Semplificando molto (in quanto bisognerebbe tenere conto di molti altri aspetti), un attore con un basso valore di fiducia può essere identificato da un alto valore di centralità out-degree a cui corrispondono bassi valori di centralità out-degree degli attori con cui comunica. Ciò può essere spiegato dal fatto che questo attore si sente sicuro nel diffondere informazioni, ma gli altri attori non diffondono queste informazioni perché non reputano affidabile tale informazione.

Fonte: https://cambridge-intelligence.com/social-network-analysis/

Closeness centrality

Un altro modo di misurare la centralità è quello di guardare quanto un nodo è “vicino” agli altri nodi. La closeness centrality è usata per misurare la lunghezza media del percorso più breve da un nodo verso un qualunque altro nodo. Maksim Tsvetovat e Alexander Kouznetsov la definiscono la misura dei gossippari poiché rappresenta l’abilità di un attore di trasmettere o condividere informazioni da un lato del network all’altro. Minore è la distanza totale nella rete e più la closeness centrality sarà alta. In altre parole, rappresenta la velocità con cui l'informazione può raggiungere altri nodi da un dato nodo di partenza: i gossippari fanno arrivare le informazioni molto più velocemente degli altri.

Betweeness Centrality

La betweeness centrality è una misura che viene usata per studiare il ruolo di un nodo nella propagazione di una informazione. Se un nodo è l’unico collegamento ponte fra altri due nodi si può dire che abbia una posizione in qualche modo privilegiata o strategica. La Betweeness Centrality va a misurare proprio questo valore. Viene infatti spesso usata per misurare il traffico nei network di trasporti. Si calcola andando a contare quante volte un nodo è attraversato da un percorso critico (il percorso più breve, o anche Eulerian path) rispetto al totale dei percorsi critici.

Se c'è un buco strutturale (una forma di discontinuità nel flusso di informazioni) in una rete, la persona che detiene la posizione di intermediazione può assumere una posizione strategica per collegare o scollegare i nodi in un gruppo, e quindi gode di un vantaggio competitivo rispetto agli altri nodi. Gli attori con un alto valore di betweeness centrality sono come dei guardiani che controllano il flusso di informazioni tra gli altri. 

Generalmente i nodi aventi alta betweeness sono quelli aventi anche alta degree centrality, in quanto sono i cosiddetti hub che abbiamo descritto sopra. Questo non è però il caso in cui un nodo va a collegare due regioni del network diverse e semplicemente scollegate. In questo caso il nodo può avere pochi collegamenti con altri nodi, ma fungere da ponte tra due regioni molto distanti della rete.

Cercando di mettere insieme i pezzi, si può dire che un nodo avente una alta betweeness centrality può corrispondere a uno dei due estremi di un legame debole di Granovetter, che a sua volta garantisce a un network la proprietà di small world vista sopra.

Eigenvector Centrality

Il detto “dimmi chi sono i tuoi amici e ti dirò chi sei” si traduce nella social network analysis nella centralità dell’autovettore. Questa misura ci dà informazioni su un attore sulla base delle relazioni che ha con i suoi vicini, cioè i suoi contatti più stretti. Di nuovo Maksim Tsvetovat e Alexander Kouznetsov hanno trovato l’analogia perfetta, ovvero Don Vito Corleone. Egli infatti con le misure di centralità precedenti non si sarebbe potuto riconoscere come il boss, poiché non ha molti collegamenti diretti e non scambia molte parole in giro. Ecco quindi l’utilità dell’eigenvector centrality. Sostanzialmente si basa sull’algoritmo di Bonacich, che iterativamente calcola un peso per ciascuno dei link di un nodo basandosi su quello degli attori vicini. Può essere definita come un'estensione della degree-centrality poiché va a guardare proprio questa metrica nei vicini, ed infatti un attore con alta eigenvector centrality è connesso a nodi aventi molte connessioni a loro volta.

Pagerank

Simile alla Eigenvector Centrality in quanto si basa sullo stesso principio di calcolo dei pesi ricorsivo è il pagerank, l’algoritmo sviluppato da Larry Page come parte essenziale delle prime versioni di Google per indicizzare le pagine Web. Il PageRank è una misura di centralità che calcola il prestigio di un nodo, inteso come pagina Web. Le pagine Web sono i nodi di un grafo orientato dove i link fra nodi sono gli  hyperlink alla pagina stessa (link alla pagina presenti su altre pagine web). Il grado di un nodo è calcolato come la probabilità che una persona capiti casualmente su quella pagina cliccando un link. 

Questo processo è conosciuto come random walk, ed è una semplice simulazione di come l’utente naviga nel web. La pagina con il più alto indice di ranking è quindi la destinazione più probabile. Si potrebbe pensare perché non usare direttamente la in-degree centrality allora? Il PageRank è in questo caso molto più efficiente perché tiene conto dell’importanza della pagina da cui proviene l’hyperlink. Ovvero se la pagina target viene citata dal Wall Street Journal sarà molto più alta in ranking rispetto a una pagina citata da un sito di spam. 

Conclusione 

Come abbiamo visto in questo articolo la SNA è uno strumento di analisi estremamente potente ed affascinante che può essere utilizzato in concomitanza con molti altri modelli nel contesto della data science. Uno di questi è la teoria dei giochi, con la quale è possibile applicare alcune delle analisi di cui abbiamo parlato, come vedremo nei prossimi articoli. 

Fonti

• Albert, and Barabasi. Network Science. Cambridge University Press, 2016.
• Easley, David, and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010.
• Menczer, Filippo, et al. A First Course in Network Science. Cambridge University Press, 2020.
• Tsvetovat, Maksim, and Alexander Kouznetsov. Social Network Analysis for Startups. O'Reilly, 2011.
• Zinoviev, Dimitry. Complex Network Analysis in Python. Adaobi Obi Tulton, 2018.
• https://www.networkworld.com/article/2878394/mit-researchers-show-you-can-be-identified-by-a-just-few-data-points.html

Articolo a cura di Giovanni Ceccaroni, Data Scientist in Orbyta Tech, 22.06.2021