Metriche

15 minuti - per Miriana Somenzi

Metriche

Fig. 1. Betweenness (da Wikimedia Commons)

I sistemi complessi sono spesso caratterizzati da molti elementi che interagiscono in diversi modi sia tra di loro che, potenzialmente, con l’ambiente in cui si trovano. Gli elementi che costituiscono un sistema possono, a volte, essere loro stessi dei sistemi, in modo da creare sistemi di sistemi che dipendono gli uni dagli altri. La sfida principale della scienza dei sistemi complessi non è solo quella di identificare i vari elementi e le loro connessioni, ma anche quella di capire come queste connessioni diano vita al sistema in sé.

Uno dei contributi fondamentali dell’Analisi di Reti Sociali è l’aver prodotto coefficienti o statistiche di analisi, chiamate metriche, che permettono di evidenziare le caratteristiche delle reti, evidenziando alcuni tipi di relazione che si possono instaurare o mettendo in evidenza il ruolo di un determinato agente all’interno del gruppo a seconda della posizione che questo ha all’interno della rete. Queste metriche sono fondamentali per le analisi da effettuare tanto quanto le risorse grafiche fornite dai software di Analisi di Rete.

Esistono due tipi di metriche da tenere in considerazione: le metriche relative all’intera rete, e quelle relative ai singoli nodi. Le metriche di rete sono quelle che fanno riferimento alla rete nel suo insieme, permettendo di estrarre caratteristiche generali della struttura osservata, come la sua densità, le dimensioni, e i componenti connessi.

Le metriche dei nodi, invece, sono quelle relative agli agenti della rete, che caratterizzano i nodi in maniera individuale. Queste metriche calcolano la posizione del nodo, o agente, prendendo come punto di partenza aspetti differenti, come la sua posizione all’interno della rete, le relazioni e l’importanza di un dato nodo rispetto agli altri partecipanti. Procederemo ora ad illustrarvi meglio le varie metriche:

Metriche di rete

Densità

Una delle metriche di rete più semplici e frequentemente utilizzate è la densità, ossia il rapporto tra i collegamenti esistenti e collegamenti possibili (che è n2, con n numero di nodi). La densità di una rete può rendere un'idea di quanto sia efficiente l'interscambio relazionale tra i vari elementi della rete stessa. Se tutti gli elementi della rete instaurassero tra loro dei legami allora le densità della rete sarebbe pari ad uno, diversamente, nel caso in cui gli elementi della rete non comunicassero tra loro, la densità della rete sarebbe pari a zero. La maggior parte delle reti sociali reali non sono dense ma sparse.

Chiusura triadica

Assumendo che 2 individui abbiano un amico in comune, la proprietà della chiusura triadica afferma che c’è una maggiore probabilità che questi diventino amici anche se non si conoscono all’inizio.

Questa proprietà suggerisce che, al crescere del mio social network, sarà più probabile che nascano degli edge tra nodi che hanno già connessioni in comune. La chiusura triadica implica, a livello topologico, un alto coefficiente di clustering perché afferma che se sono connesso a 2 individui sarà molto probabile che in futuro questi si conosceranno e chiuderanno il triangolo.

Perché si chiudono i triangoli, sociologicamente parlando?

I motivi sono molteplici:

• Se B e C hanno un amico in comune che è A, B e C hanno più probabilità di incontrarsi perché condividono lo stesso ambiente sociale “grazie” ad A;
• B e C si fideranno l’uno dell’altro perché entrambi si fidano dell’amico in comune A;
• C’è l’incentivo di A di far conoscere B e C e farli diventare amici.

Esiste, inoltre, la proprietà della chiusura triadica forte (strong triadic closure): essa afferma che, se A ha collegamenti forti sia con B sia con C, allora il collegamento da B a C deve necessariamente esistere, sia esso debole o forte. Ogni volta in cui abbiamo uno scenario simile, ossia un nodo ha 2 collegamenti forti in uscita connessi a nodi indipendenti, la proprietà della chiusura triadica forte assicura anche l’esistenza del terzo collegamento e la chiusura, quindi, del triangolo.

Coefficiente di clustering

Il coefficiente di clustering misura quanto i nodi di un grafo tendono ad essere connessi fra loro. Si può misurare in modo globale o locale: Il coefficiente di clustering globale si basa su triple di nodi. Una tripla consiste di tre nodi connessi da due (tripla aperta) o tre (tripla chiusa) collegamenti. Ogni tripla è incentrata su un nodo. Un triangolo consiste di tre triple chiuse incentrate sui tre stessi nodi che le compongono. Il coefficiente di clustering globale è, dunque, il numero di triple chiuse (o 3 volte il numero di triangoli) fratto il numero totale di triple (somma di quelle aperte e chiuse). Il coefficiente di clustering locale di un nodo in un grafo, invece, è una misura di quanto i suoi vicini tendano a formare un grafo completo.

Numero di componenti

Una rete può essere analizzata anche tramite il numero di componenti da cui è formata. Un componente è un insieme di nodi all’interno di una rete in cui esiste un possibile percorso tra tutti i nodi di cui è composto l’insieme, ossia dove non esistono nodi, o gruppi di nodi, liberi, non connessi. Una rete, quindi, può essere formata da uno o più componenti, ognuno dei quali rappresenta un insieme di nodi connessi all’interno del grafo, che può essere a sua volta formato da un unico nodo, o da centinaia, o da migliaia di nodi a seconda dei casi. L’esistenza di componenti separati all’interno di una rete può indicare la presenza di diversi gruppi di interesse in una determinata area, che possono agire in maniera complementare tra loro ma possono anche essere in opposizione. Il fatto che la stessa rete possa essere costituita da gruppi diversi senza relazioni tra loro deve essere attentamente analizzato dal ricercatore, che avrà il compito di capire la motivazione di questa separazione: è dovuta a fattori settoriali? Professionali? Geografici? E qual è il suo impatto sui rapporti sociali analizzati? Queste sono solo alcune tra le domande che una rete costituita da componenti separati può sollevare.

Distanza geodetica

Nei grafi indiretti la distanza tra due nodi è definita come il numero di edge presenti nel percorso più corto che li collega entrambi. Se due nodi non sono connessi la distanza è infinita. Nei grafi diretti invece ogni percorso segue obbligatoriamente la direzione indicata dalla freccia, perciò la distanza tra un nodo A e un nodo B lungo un percorso AB sarà diversa dalla distanza tra il nodo B e il nodo A in un percorso BCA .

Il diametro è la distanza massima tra qualsiasi paio di nodi del grafo, ossia il percorso minore più lungo in un grafo (longest shortest path). Questa metrica ci permette di avere un’idea della dimensione della rete analizzata, dandoci anche indicazioni riguardo la densità delle relazioni al suo interno. Questo perché una rete può avere un diametro basso anche se composta da un elevato numero di nodi, se i nodi al suo interno sono molto densi.

Pertanto, un grafico con un diametro elevato indica una rete ampia e dispersa, mentre un grafico dal diametro bassi può indicare o una rete di piccole dimensioni o una rete più ampia ma densamente connessa.

Ego network

Un cosiddetto ego network è una rete focalizzata su un singolo nodo e che comprende, oltre al nodo stesso, i vicini a distanza 1 da quel nodo e le interazioni tra di loro. Più intendiamo “l’amicizia” in maniera generica più la nostra rete sociale sarà grande, tuttavia una rete sociale di ampie dimensioni spesso è sinonimo della presenza di molte connessioni, ma deboli, mentre una rete sociale di dimensioni ridotte spesso significa avere meno connessioni, ma più forti.

Resilienza

Se da una rete rimuoviamo nodi in maniera randomica, quanti ne dobbiamo togliere prima di distruggere il componente più densamente connesso al suo interno? Per capirlo è necessario prendere una rete, rimuovere un nodo alla volta e poi osservare come la grandezza del componente più densamente connesso cambi nel tempo. Possiamo dividere i tipi di rimozione dei nodi in due categorie:

1. fallimenti, solitamente randomici, quindi accadono indipendentemente dalla posizione del nodo all’interno della rete e la probabilità che ciò accada è la stessa per tutti i nodi;
2. attacchi, ossia qualcuno dall’esterno che tenta di capire quale sia il nodo migliore da rimuovere in modo da distruggere la connettività del grafo.

I nodi, inoltre, non sono gli unici a poter fallire/essere attaccati: identificare ponti locali e reali, infatti, può portare ad attacchi estremamente efficienti.

Queste strategie potrebbero essere riviste e riutilizzate per l’analisi di svariati campi, da quello bellico a quello epidemiologico.

Metriche individuali

Le metriche locali di un grafo, dette anche metriche individuali o di nodo, sono statistiche che vengono calcolate per ciascuno dei vertici di cui è composta la rete, e forniscono informazioni riguardo il loro posizionamento e la loro importanza nei confronti degli altri vertici. Vediamo, brevemente, le metriche principali e il loro funzionamento.

Centralità

La centralità è usata solitamente per dare un punteggio ai nodi presenti nel grafo per capirne l’importanza.

Esistono vari modi per misurare la centralità , essa va sempre associata a qualcosa. La centralità è importante per capire la relazione che ogni nodo ha con il resto del network, quali sono le caratteristiche che lo rendono centrale e diverso dagli altri nodi presenti (ad esempio, può essere utile per capire dove apparirà un nuovo collegamento per i compiti di link prediction). La degree centrality è un metodo molto semplice per classificare i nodi: più alto è il grado di un nodo più il nodo sarà centrale all’interno della rete. Ovviamente si tratta di una visione locale della centralità, in questo caso il nodo centrale è semplicemente un nodo con molti edge. In questa maniera catturiamo sì il grado in cui un nodo è connesso al resto del grafo, ma è un grado locale, stiamo parlando solo dei vicini del nodo considerato, ossia tutto ciò che c’è a 1 edge di distanza dallo stesso. Questa misura può essere sufficiente per analizzare alcune proprietà specifiche, come la connettività, ossia quanto il nodo è coinvolto in un tessuto sociale. Le misure di centralità possono essere calcolate anche su grafi diretti e, in questi casi, avremo 2 ranking differenti, uno per gli in-degree, ovvero i nodi entranti, e uno per gli out-degree, ovvero i nodi uscenti. Per calcolare l’importanza di un nodo bisogna calcolare l’importanza di tutti i nodi a cui è connesso quindi i nodi importanti sono quelli a cui sono collegati altri nodi importanti. A questo schema ricorsivo sono collegate misure diverse di centralità, che ora andremo ad illustrare.

Centralità PageRank

Si tratta di un algoritmo proposto da W.Page nel 1998.

Considerando un nodo questo sarà l’inizio di una random walk all’interno della rete in modo da calcolare il suo punteggio di centralità, chiamato appunto PageRank. Questa random walk è semplicemente un processo che naviga la rete spostandosi da un nodo sorgente ad un altro, ed è utilizzato per aggiornare il punteggio corrente del nodo di partenza ad ogni iterazione.

In questo modo quindi evitiamo di registrare i punteggi dei vicini di ogni nodo ma prendiamo il punteggio entrate da un sottoinsieme di nodi scelti in maniera casuale, che sono a una distanza crescente dal nostro punto di partenza.

Centralità di Katz

La centralità di Katz tenta di misurare esplicitamente il grado relativo di influenza di un nodo all’interno di un network.

Si inizia da un nodo e poi, per tutte le possibili distanze da quel nodo a qualsiasi altro nodo del grafo, si calcola la somma dei differenti percorsi. Questa modalità cattura quanto un nodo sia distante da altri nodi nel grafo attraverso un percorso di una data lunghezza stabilita. La centralità di Katz, quindi, calcola la somma completa per tutte le distanze possibili all’interno del grafo, e per tutti i possibili percorsi a quella data distanza iniziando da nodo. Questa doppia somma viene poi moltiplicata per un fattore di attenuazione, che è semplicemente qualcosa che fa pesare di meno i percorsi più lunghi. Esistono altri tipi di centralità che non si basano su uno schema ricorsivo come quelle appena presentate: si tratta di centralità geometriche.

Coefficiente di prossimità (closeness centrality)

Il coefficiente, o grado, di prossimità tenta di determinare quanto un nodo è vicino agli altri agenti della rete considerando l’insieme delle loro relazioni. Pertanto, un nodo avrà un indice di prossimità più elevato se può relazionarsi più strettamente e rapidamente con gli altri nodi, ossia non dovendo dipendere da intermediari.

Betweenness centrality

Cattura il numero di percorsi più corti che passano attraverso un determinato nodo, quindi, partendo da un nodo, per capire quanto è importante per la connettività del grafo è sufficiente contare il numero di percorsi più corti che passano per quel nodo. Secondo la definizione di Betweenness Centrality i nodi più importanti sono quindi quelli che accedono a ponti attraverso cui passano le informazioni.

La Betweenness Centrality può essere vista come il risultato di un processo di diffusione: quei nodi che sono centrali nella diffusione di informazione tra componenti altrimenti separati sono quelli che sono più importanti.

Bibliografia e sitografia

Citazione di questo articolo

Come citare: SOMENZI, Miriana . "Metriche". In: CLIOMATICA - Portale di Storia Digitale e ricerca. Disponibile in: http://lhs.unb.br/cliomatica/index.php/Metriche. il giorno: 27/06/2024.

Informare errori in questa pagina