2.1. La teoria delle reti complesse
2.1.2. Graph theory e principali caratteristiche delle reti
La scienza delle reti utilizza un linguaggio di tipo matematico-statistico per descrivere le generali proprietà di un sistema complesso.
Per una immediata visualizzazione delle caratteristiche base di una rete, come la sussistenza o meno di un certo grado di regolarità nelle connessioni, la presenza di nodi con molti collegamenti, l’esistenza di cluster o di modularità39, si fa ricorso ad uno strumento grafico particolarmente efficace nello svolgere questa funzione: il grafo. Si tratta di una figura schematica che riproduce la struttura delle interazioni tra più elementi di un sistema e si compone di più punti, rappresentanti i nodi della rete, e di linee, ovvero i collegamenti che si instaurano tra di essi.
Il grafo è il prodotto di una speciale branca della matematica, conosciuta come graph
theory, dedicata appunto allo studio e alla descrizione formale dei network.
Il grafo consente di rappresentare un sistema complesso in modo intuitivo ed elementare, come un insieme di punti e linee variamente combinati. Nella realtà le connessioni che si instaurano tra elementi presentano peculiarità tali da distinguerle l’una dall’altra, ma questa eterogeneità spesso non viene resa graficamente. Esistono però modi alternativi per rappresentare i collegamenti che si instaurano tra nodi di un grafo, ideati per superare il limite appena descritto, così da realizzare figure più attinenti al reale (figura 1).
38
In natura il collegamento che si instaura tra due elementi può essere reciproco o no: talvolta informazioni o risorse viaggiano in una sola direzione da un punto ad un altro e non è possibile che percorrano la stessa strada nel senso contrario (si pensi ad una filiera produttiva tradizionale in cui le risorse vengono trasferite dal fornitore al cliente). In questo caso il legame tra due nodi viene rappresentato come una freccia orientata nel verso di percorrenza, e il grafo si dice orientato. Nel caso in cui invece i collegamenti tra nodi siano reciproci il collegamento è una semplice linea e il grafo si chiama non orientato. Qualora inoltre si instaurino relazioni di diversa intensità tra elementi del
network è possibile rappresentare l’eterogeneità tramite grafo pesato, associando cioè
un diverso peso a ciascuno dei collegamenti visibili.
Figura 1. Tipologie di grafo
Queste soluzioni consentono di cogliere immediatamente alcune peculiarità della rete che si ha di fronte. Un’approfondita conoscenza delle sue proprietà può essere poi acquisita proseguendo tramite l’utilizzo di strumenti matematico-statistici, applicando appositi algoritmi.
39
La teoria delle reti si avvale largamente della notazione algebrica e geometrica per definire una rete e descriverne configurazione e funzionamento in modo rigoroso e preciso.
Procediamo introducendo alcune importanti caratteristiche delle reti ricorrendo al linguaggio matematico quando può essere d’aiuto40.
Definizione e caratteristiche delle reti
Un network Γ = (N, L) è definito da un insieme finito di nodi N = {1, 2, …, n} e da un insieme di collegamenti L N × N (supponiamo che i collegamenti non siano pesati). Se una rete è diretta l’esistenza del collegamento (i, j) dal nodo i al nodo j non implica necessariamente l’esistenza del reciproco (j, i), ma, in questa introduzione, supponiamo che la rete non sia diretta.
Dato un generico nodo i si definisce l’insieme dei suoi vicini come
Ni {j N : ij L}, insieme dei nodi j uniti ad i tramite un collegamento.
La connettività tra elementi è una delle prime caratteristiche da studiare in una rete, in quanto grazie ad essa, si può intuire già ad un primo sguardo il grado di casualità intervenuto nella formazione del network.
Il numero di collegamenti che partono da un nodo i si dice grado del nodo, ed è espresso come zi Ni = {j N : ij L}, il numero dei vicini di quel nodo, supponendo che
ogni collegamento termini in un altro elemento. E’ possibile, ed estremamente utile, studiare la distribuzione del grado del network: si tratta della distribuzione di probabilità41 (o di frequenza) del grado dei nodi.
Data la variabile aleatoria z, si associa a ciascun valore che essa può assumere ( = 0, 1, …, n-1) la probabilità p(), espressa dalla formula
𝑝() = 1
𝑛{i N ∶ 𝑧
𝑖 = } .
40 Le formule utilizzate sono state tratte dal testo Complex Social Networks, di Fernando Vega-Redondo,
Cambridge University Press, 2007.
41 Data una variabile aleatoria (o variabile casuale) essa è caratterizzata da una distribuzione di
40
La p() è la probabilità che un nodo selezionato casualmente abbia grado . La distribuzione assume forme diverse in base al tipo di rete che si ha di fronte, come verrà specificato in seguito, da qui si desume come la stessa sia una misura associata a determinate proprietà del network.
Un altro elemento caratterizzante la rete è la distanza media tra i suoi punti. Si chiama
distanza geodetica tra due nodi i e j, d(i, j), il percorso più breve che unisce i e j tra i
diversi possibili (se ne esistono diversi), ovvero, il minimo numero di collegamenti necessari per unire i e j. Se questo percorso non esiste per convenzione verrà indicato 𝑑(𝑖, 𝑗) = +∞.
Supponendo per semplicità che per ogni coppia di nodi vi sia un percorso che li unisce (tutte le distanze tra coppie sono finite), si può costruire una distribuzione di frequenza anche per le distanze che separano i nodi, specificando per ciascuna distanza r la frazione di coppie di nodi separate proprio da un percorso di quella lunghezza. Ciascuna frazione può essere determinata con la seguente formula
𝜔(𝑟) = 1
𝑛(𝑛−1){(i, j) N × N ∶ d(i, j) = r}.
Una volta calcolata la distribuzione di frequenza della d è possibile determinare la
distanza media tra i nodi della rete come media ponderata delle distanze rilevate tra
ciascuna coppia di nodi costituenti il sistema, utilizzando i valori della omega come fattori di ponderazione:
𝛿 = ∑0<𝑟<∞𝑟 ∙ 𝜔(𝑟).
Un’altra misura largamente utilizzata nello studio delle reti e, in particolare nell’analisi delle reti sociali, è il coefficiente di clustering. Questa caratteristica ha delle forti implicazioni sulla circolazione dell’informazione in un network e sulle strategie di collaborazione.
Il coefficiente di clustering di un singolo nodo individua, in breve, il grado con cui i vicini di un nodo sono a loro volta vicini l’uno dell’altro, ovvero collegati tra loro. Per ogni nodo i con almeno due vicini il clustering è calcolato come rapporto tra il numero di coppie di vicini di i collegati tra loro e il numero di possibili coppie di vicini di i, in altre parole potrebbe essere espresso come la percentuale di coppie di vicini di i,
41
considerando tutte quelle possibili, unite da un collegamento. In simboli può essere espresso come 𝐶𝑖 ≡ 𝑧𝑖(𝑧𝑖−1)1 2 {jk ϵ L ∶ ij ϵ L ik ϵ L}, dove 𝑧 𝑖(𝑧𝑖−1)
2 rappresenta il numero di possibili coppie di vicini di i.
Il coefficiente di clustering della rete è ottenuto semplicemente come media del clustering di ogni singolo nodo appartenente ad essa. Dati n nodi avremo
𝐶 = 1
𝑛∑ 𝐶
𝑖 𝑛
𝑖=1 .
I punti di un network possono giocare un ruolo più o meno importante all’interno dello spazio in cui sono inseriti. La loro posizione può essere tale da consentir loro di controllare e condizionare i flussi che scorrono nella rete. Un modo per valutare l’importanza di un nodo è misurare la sua centralità di intermediazione.
Le implicazioni di questa caratteristica a livello informativo non sono trascurabili: la centralità di un nodo implica il suo coinvolgimento nei processi di comunicazione che si attivano tra altre coppie di punti del network.
La centralità di un nodo può essere calcolata ricorrendo ad un rapporto matematico. Ammettiamo che per ciascuna coppia di nodi della rete esista un percorso che li colleghi. Indichiamo con v(j, k) il numero dei cammini più brevi che collegano ogni coppia di nodi j e k, e consideriamo il numero di questi percorsi che passano per il nodo i vi(j, k).
Date queste premesse la centralità di intermediazione del nodo i può essere ottenuta come frazione dei percorsi più brevi tra coppie di nodi del network che attraversano il nodo i, ovvero
𝑏𝑖 ≡ ∑ 𝑣𝑖(𝑗,𝑘)
𝑣(𝑗,𝑘)
𝑗≠𝑘 .
Lo studio congiunto di queste caratteristiche su larga scala consente di apprendere come è strutturata una rete e quale è stato presumibilmente il suo percorso di formazione.
42
Regolarità e casualità
Quando si studia un fenomeno, a prescindere da quale sia la sua natura, si cerca sempre di scoprire un qualche grado di regolarità nella configurazione delle sue parti nonché nel comportamento. Nella realtà non è facile osservare sistemi dal grado assoluto di regolarità e prevedibilità ma neppure elementi governati quasi totalmente dal caso. Sistemi regolari e sistemi casuali sono costruzioni teoriche di casi estremi utili a conoscere quali proprietà e caratteristiche possono scaturire dall’estrema razionalità o dal caos.
Il modello del random network, la rete casuale, utilizza strumenti quantitativi per studiare le proprietà di sistemi governati dal caso. Questo framework ammette un alto livello di complessità strutturale e ben si presta all’analisi dei sistemi di elevate dimensioni. Per la descrizione di questi tipi di rete è stato applicato agli inizi degli anni ’60 il modello binomiale42.
Data una rete con punti N = {1, 2,…, n}, si ipotizza che ogni coppia di nodi abbia la stessa probabilità q > 0 di essere unita da un collegamento43, e che questa probabilità
non muti al verificarsi di altri eventi. Si attiva, in altre parole, un processo di collegamento casuale tra nodi.
Secondo quanto ipotizzato dal modello, la distribuzione del grado della rete è di tipo binomiale, questo significa che la variabile casuale “grado del nodo” ha una funzione di probabilità del tipo
𝑝(𝜅) = (𝑛 − 1
𝜅 ) 𝑞
𝜅(1 − 𝑞)𝑛−𝜅−1,
dove n-1 è il numero di osservazioni effettuate, è il numero di successi che si desidera avere e q è la probabilità di un successo, ovvero che esista un collegamento. La funzione
p() esprime la probabilità di osservare il grado in un nodo.
42 “A different approach was proposed by Gilbert (1959), and later by Erdös and Rényi (1960), to study
random networks: the binomial model. This alternative framework is essentially equivalent to the first one for large systems, but has proven to be more easily amenable to analysis”. Fernando Vega-Redondo, Complex Social Networks, Cambridge University Press, 2007, cit., p. 37.
43 q è la probabilità dell’evento “si crea un collegamento tra la coppia di nodi” ed è indipendente, ovvero
43
Nelle reti casuali di elevate dimensioni la distribuzione del grado assume una forma di tipo gaussiano, detta anche normale. Secondo questa legge, il grado dei nodi si distribuisce simmetricamente attorno ad un valor medio, e la probabilità di osservare un nodo con grado superiore o inferiore alla media diminuisce gradualmente allontanandosi dal centro (con quale velocità dipende anche dal valore dello scostamento medio). Grazie al metodo statistico anche in presenza di casualità la teoria delle reti è stata in grado di descrivere questa importante caratteristica del random network. Reti di questo tipo presentano una certa omogeneità nel grado, in altre parole i punti appartenenti ad essa tendono ad avere un numero di collegamenti abbastanza simile, come dimostrato dalla legge gaussiana. E’ raro in queste circostanze trovare degli hub, cioè nodi altamente connessi, dei crocevia, o come vengono anche chiamati, dei “superconnettori”. Per il numero di connessioni che da essi di diramano rappresentano delle eccezioni rispetto alla media, e in presenza di una distribuzione normale del grado la probabilità di incontrare valori della variabile casuale molto distanti dalla media è pressoché nulla.
Nel random network è casuale anche il meccanismo che governa la formazione dei cluster: i collegamenti tra vicini di un generico nodo i possono generarsi con la stessa probabilità, come vale per ogni altro link44. La probabilità che due nodi vengano uniti è infatti indipendente da qualsiasi altro evento, dunque non inciderà il fatto che una coppia di punti siano già legati ad uno stesso vicino. Il coefficiente di clustering di una rete casuale è dunque solitamente inferiore rispetto a quello dei network osservati nella realtà45.
L’omogeneità in una rete non è comunque la regola e l’evidenza empirica dimostra che incontrare degli hub non è poi così difficile.
La presenza di un certo grado di eterogeneità può riscontrarsi nei sistemi a invarianza di scala, reti in cui il grado dei nodi (la grandezza oggetto di studio) non presenta una scala caratteristica. Questo implica che il valore atteso della variabile casuale non è un predittore attendibile del valore che sarà osservato, in quanto è possibile che il grado di un nodo si discosti in maniera significativa dalla media.
44 Collegamento.
44
La legge di distribuzione delle connessioni può fornire una dimostrazione rigorosa di questa caratteristica. I network a invarianza di scala presentano infatti una tipica distribuzione del grado sbilanciata verso destra, ben approssimata da una legge di potenza.
La variabile casuale grado di un nodo si distribuisce dunque secondo una legge di probabilità del tipo
𝑝(𝜅) ∝ 𝜅−𝛾.
Il declino graduale della legge di potenza crea una lunga coda verso destra che associa una probabilità maggiore di zero anche a valori della nettamente superiori alla media. Questo significa essere in presenza di eterogeneità, situazione in cui i nodi possono avere grado molto diverso tra loro, e in cui, di conseguenza, è possibile identificare nodi altamente connessi o hub.
Ovviamente la distribuzione del grado non può coincidere alla perfezione con la legge di potenza in quanto quest’ultima al crescere di tende a zero ma non raggiungerà mai quel valore, per cui la pura legge matematica ammetterebbe l’esistenza di nodi dal grado infinito con probabilità maggiori di zero. Nella realtà non vi sono hub con un numero infinito di connessioni, per cui la scienza delle reti ipotizza l’esistenza di un grado massimo finito.
La regola secondo cui le connessioni si distribuiscono nello spazio condiziona dunque le caratteristiche strutturali delle reti, e consente inoltre di intuire l’intensità con cui la casualità interviene nel plasmare una rete.
La teoria delle reti si è anche occupata nel tempo di formulare modelli per derivare le proprietà dei sistemi regolari, anche detti reticoli. Si tratta di reti dalla struttura assimilabile a delle griglie m-dimensionali in cui i nodi si dispongono a formare figure regolari.
Data una serie di nodi, i collegamenti tra essi vengono generati in modo regolare senza oltrepassare una certa distanza r ℕ. Così se vale r = 2 ciascun nodo sarà legato ai nodi da lui distanti un collegamento e ai nodi da lui distanti due collegamenti. Secondo queste premesse l’insieme dei vicini di i è dato da Ni = {j N : (i, j) r}, ovvero l’insieme
45
dei nodi che si trovano nello spazio cartesiano ad una distanza da i minore o uguale ad
r.
Questa legge dà origine a strutture molto regolari e ordinate, facilmente prevedibili. Se consideriamo una rete regolare unidimensionale (m = 1) si può dimostrare che la distanza media tra punti del network è una funzione del numero di nodi n, tale per cui al crescere della dimensione della rete la distanza media cresce a sua volta in modo lineare46. In tal caso la crescita può rendere più lunghi e impegnativi i percorsi da intraprendere per raggiungere nodi lontani, e ciò potrebbe avere delle conseguenze spiacevoli sulla velocità di scambio di informazioni tra i nodi47. Questo accade in quanto
i reticoli non possiedono le caratteristiche dei “mondi piccoli”.
Il modello del mondo piccolo (in inglese small world) combina caso e regolarità, ed è stato formulato dal fisico Duncan Watts e dal matematico Steven Strogatz nel 1998, per comprendere quali potessero essere i meccanismi alla sua origine. Le reti che sono strutturate come mondi piccoli presentano una particolare peculiarità ed è proprio questa che ha acceso l’interesse della disciplina: le distanza media che separa le coppie nodi nella rete è molto breve.
Per capire a cosa potesse essere legata questa importante caratteristica gli scienziati hanno adottato un procedimento particolare: hanno progressivamente introdotto disordine in una rete regolare, studiando gli effetti strutturali di questa operazione. La struttura ipotizzata per il reticolo di partenza è semplice, unidimensionale (m = 1) con n nodi e grado z = 2r. E’ stato poi scelta una frequenza , compresa tra zero e uno, con cui selezionare nodi che sarebbero stati scollegati dai vicini più prossimi e ricollegati ad altri nodi scelti a caso, in modo da creare una sorta di turbamento della regolarità del reticolo e generare dei “ponti” tra punti appartenenti a zone remote. In generale con l’avvicinarsi di ad 1 è sempre più alta la percentuale di nodi “ricollegati” e la struttura del network assomiglia sempre più a quella di una rete casuale (figura 2).
46 Si confronti Fernando Vega-Redondo, Complex Social Networks, Cambridge University Press,
2007, p. 55.
47 “Se internet fosse un reticolo simile ad una scacchiera, la distanza media tra due router sarebbe
dell’ordine di mille salti e la rete sarebbe molto più lenta: niente navigazione veloce del Web, niente email istantanee”. Guido Caldarelli, Michele Catanzaro, Scienza delle reti, Egea, 2016, cit., p. 68.
46
Figura 2. Dalla rete regolare alla rete casuale attraverso i mondi piccoli.
Grazie a questo procedimento gli studiosi hanno osservato che l’inserimento di disordine in un sistema reticolare comporta una progressiva riduzione della distanza media tra nodi, e che, in aggiunta, al crescere della dimensione della rete la distanza media che separa i punti non aumenta di molto.
I mondi piccoli inoltre possiedono un’altra interessante peculiarità, ovvero manifestano un alto coefficiente di clustering a livello locale.
Secondo quanto fino ad ora illustrato circa le reti complesse sembra possibile attraverso lo studio statistico di caratteristiche come clustering, distribuzione del grado e distanza media derivare importanti informazioni sulla rete, come la conformazione della struttura (presenza o meno di hub, omogeneità e così via) e l’esistenza o meno di regolarità nelle connessioni e collegamenti a lungo raggio. Ammettiamo dunque di possedere gli strumenti per conoscere una rete a livello macroscopico.
Quando però il modello osservato si discosta da un random network, caso estremo governato dal caso, sorge spontanea una domanda: quali meccanismi guidano una rete verso una determinata configurazione?
47 Evoluzione delle reti
Lo studio delle dinamiche che agiscono in una rete coordinando la formazione di strutture complesse, è utile per scoprire quali fattori intervengano nel regolare l’evoluzione delle reti.
La ricostruzione dei processi di trasformazione dei network assume un grande rilievo in campo predittivo.
Esistono reti che mutano la struttura dei collegamenti ma mantengono nel tempo lo stesso numero di nodi, network in cui il numero di nodi cambia in continuazione a parità di collegamenti e reti che manifestano dinamiche più complicate con la contestuale aggiunta ed eliminazione sia di nodi che di connessioni.
E’ legittimo chiedersi perché un nodo decida di legarsi ad un punto piuttosto che ad un altro (qualora si possa escludere l’intervento del caso), o ancora, perché il grado di una rete manifesti un certo tipo di distribuzione.
Alla fine degli anni novanta i fisici Albert-Laszlo Barabasi e Réka Albert hanno elaborato un interessante modello matematico grazie al quale riuscirono a dimostrare l’esistenza di leggi razionali dietro all’eterogeneità di una rete.
Le due fondamentali ipotesi alla base del modello sono la crescita continua della rete, con progressiva aggiunta di nuovi nodi ad un nucleo originario in espansione, e l’esistenza di preferenze da parte dei nuovi entranti circa i nodi a cui collegarsi.
Il meccanismo del collegamento preferenziale prevede che i nuovi vertici della rete siano attratti da nodi già altamente connessi. Nessuno dei vecchi nodi è escluso dal meccanismo, nel senso che qualunque nodo tra quelli già dentro il network può legarsi ad un nuovo entrante, ma la probabilità di connettersi ad un altro nodo è tanto più alta quanto più è elevato il numero di collegamenti già instaurati: in altre parole tale probabilità è proporzionale al grado posseduto al momento dell’entrata del nuovo arrivato.
E’ possibile esprimere questa legge in termini matematici considerando una delle versioni più semplici del modello, quella in cui un solo nodo si aggiunge al nucleo
48
preesistente a ciascun istante successivo t48, instaurando un solo collegamento con un altro elemento del network. Chiamiamo ciascun nodo come l’istante di tempo in cui esso ha fatto la sua entrata nella rete, in modo tale che ad esempio il nodo s = 3 sia quello comparso al tempo t = 3. Al momento t (con 𝑡 ≥ 𝑠) la probabilità che un collegamento venga stabilito con un particolare nodo s è data da
𝜋𝑡𝑠 = 𝑧𝑡𝑠
∑𝑡−1𝑠′=0𝑧𝑡𝑠′,
risultando dunque proporzionale al grado del nodo s al tempo t, espresso da𝑧𝑡𝑠.
Questa particolare legge evolutiva può spiegare perché nel network è possibile osservare