Modelli di rete

L'attuale teoria delle reti descrive una varietà di sistemi fisici, chimici, biologici, sociali e tecnologici. Le comunità scientifiche stanno utilizzando le reti complesse per modellare questi sistemi studiando la loro topologia, l’evoluzione e la struttura. Tradizionalmente, lo studio delle reti complesse utilizza la teoria dei grafi (Clark & Holton, 1995). I principali modelli di rete attualmente disponibili sono quelli di Erdős & Rényi

38

(1959), Watts & Strogatz (1998) e Barabási & Albert (2000), e sono noti come modelli di grafi random,

piccolo mondo e scale-free.

A Partire dagli anni Cinquanta, due matematici ungheresi Erdős & Rényi (1959) hanno identificato grafici casuali, con nessuna organizzazione apparente. Questo modello, dominante per anni nella letteratura di settore, considera un grafo di nodi ed una probabilità che due coppie di nodi siano connessi fra loro. Questo porta ad una rete i cui archi H sono circa e questi collegamenti sono distribuiti in modo casuale. In Figura 2.6, sono riportati due grafi di 50 nodi e 100 archi, costruiti in modo casuale.

Figura 2.6. Due grafi random di 50 vertici e 100 archi, realizzati tramite il comando RandomGraph[{50, 100}]

di Mathematica. Sia la rete (a) che la rete (b) non sono connesse. La prima ha due punti isolati, connessi fra loro, mentre la seconda ha un solo punto isolato.

Ma l'interesse nella modellazione dei fenomeni biologici, tecnologici e fisici ha portato all'idea che i sistemi complessi abbiano principi organizzativi, incorporati nelle loro strutture. Se i modelli non sono casuali, forse altri strumenti quantitativi sono necessari per analizzare l'organizzazione strutturale di questi sistemi. Uno di questi concetti è il concetto di small-world (piccolo mondo), che sottolinea l’emergenza di sistemi organizzati e aggregati (cluster) all’interno delle reti. Il concetto di clustering o di aggregazione affonda le sue radici in sociologia (Wassermann & Faust, 1994). Milgram (1967) ha dimostrato che, nelle comunità

39

sociali, ogni individuo è separato da un altro in media da sei gradi di separazione. Oggi diremmo che, se ad ogni individuo corrisponde un nodo, un arco e una qualche forma di relazione tra individui, il diametro di questa rete è 6. La natura di questa rete non è casuale: nella sua struttura sono presenti molti cluster (ad esempio, gli amici di un amico sono quasi sempre anche amici tra loro, creando le clique, ovvero sotto-grafi con ogni nodo collegato all’altro). Insiemi di cluster formano le comunità o reti sociali, ovvero aggregazioni più vaste di gruppi di soggetti altamente connessi tra loro, mentre il diametro di questa rete non cambia in modo sostanziale, rispetto alle reti casuali. La presenza di cluster non va a discapito dell’efficienza della rete. Questo tipo di rete sembra caratterizzare diversi sistemi, in domini diversi, dalla rete di attori di Hollywood alle reti telefoniche, alle reti biologiche, etc. Il coefficiente di clustering fu introdotto da Watts & Strogatz nel 1998 per misurare l’aggregazione di un gruppo di nodi che compongono una rete. Un coefficiente di clustering vicino a 1 indica che il gruppo è molto compatto, ma se tende a 0, il gruppo è molto frammentato. Watts & Strogatz hanno quindi proposto un nuovo modello di reti che prevede l'esistenza di raggruppamenti, i cui nodi hanno molte strutture in comune, mentre i legami tra nodi appartenenti a differenti gruppi sono molto ridotti. In queste reti, i nodi non sono collegati né in maniera ordinata né casuale; queste reti stanno tra due estremi (ordinati- casuali) e sono dette di piccolo mondo. La Figura 2.7 presenta una rete di piccolo mondo, costruita sul modello di Watts & Strogatz.

Figura 2.7. Rete di piccolo mondo costruita sul modello di Watts & Strogatz costruita con 900 nodi e 1800 archi. Questa rete è stata generata con il software Mathematica.

Le reti di piccolo mondo possono essere create in modo semplice. Si parte da una rete ordinata composta da N nodi nella quale un nodo i è collegato ai suoi due vicini di destra i+1, i+2 e di sinistra i-1, i-2; a loro volta, solo i vicini prossimi sono collegati fra loro. Per questi reti si considera una condizione al contorno

40

periodica, nella quale il vicino di sinistra di 1 è il nodo N e il vicino di destra del nodo N è 1. In Figura 2.8, si riporta una rete di questo tipo, composta da 5, 10 e 20 nodi rispettivamente.

Figura 2.8. Una rete di 5, 10 e 20 nodi nella quale ogni nodo è collegato con i suoi vicini prossimi, che a loro volta sono collegati fra loro. Il numero di archi è 10, 20 e 40 rispettivamente.

I coefficienti di clustering delle tre reti di Figura 2.8 sono molto alti (1 per la prima rete e 0.5 per le altre due). In realtà questo valore si stabilizza su 0.5 perché nel vicinato solo il 50% dei triangoli possibili sono presenti. Il problema di queste reti è la loro scarsa efficienza; infatti, il diametro, così come la lunghezza media, crescono molto velocemente. Per la prima rete il diametro e la lunghezza media sono pari a 1; nella seconda rete valgono 3 e 1,667. Nella terza rete diventano 5 e 2,895. In una rete di 100 nodi i valori diventano addirittura 25 e 12,879. In una rete di 900 nodi questi valori sono diventati 225 e 112,875. Quindi, più grande è il numero di nodi, più i cluster intaccano l’efficienza della rete, con cammini troppo lunghi. Il problema si risolve prendendo alcuni degli H archi della rete e, invece di usarli per collegare nodi prossimi, si collegano a caso nodi anche distanti dal nodo dato. Ad esempio, la rete a 900 nodi di Figura 2.8 è ottenuta tramite una riscrittura con probabilità . In questo caso, il diametro della rete si è ridotto a 24, e la lunghezza media è pari a 11,664. Anche il coefficiente di cluster è diminuito a 0,438, perché alcuni archi sono stati utilizzati non per formare triangoli, ma per collegare nodi distanti. La Figura 2.9 presenta una rete di 50 nodi, i cui archi sono riscritti con probabilità 0,03, 0,07, 0,2 e 0,3 rispettivamente.

41

Se per la rete di 900 nodi si aumenta la probabilità di riscrittura a 0,2, si ottiene una ulteriore diminuzione del diametro, pari a 12 e una lunghezza media pari a 6,75. Il coefficiente di clustering diminuisce a 0,259. Riassumendo, una rete ordinata ha un alto coefficiente di clustering, ma una grande lunghezza media; una rete random ha un basso coefficiente di clustering, ma una bassa lunghezza media; ci si aspetta che una rete di piccolo mondo abbia un alto coefficiente di clustering, ma una lunghezza media non molto più bassa di una rete random corrispondente, cioè che consenta aggregazioni come nelle reti ordinate, ma mantenga un’efficienza paragonabile a quella di una rete random.

Come possiamo sapere se una rete può essere classificata di piccolo mondo? Possiamo rispondere a questa domanda calcolando tre nuovi parametri per la rete

(2.9)

(2.10)

(2.11)

dove sono i valori medi di una rete random che abbia lo stesso numero di nodi e lo stesso

numero di archi della rete sotto esame. Affinché una rete sia di piccolo mondo allora, in accordo con la definizione data da Watts & Strogatz, dovrà risultare: γ≫1 (cioè un numero di cluster più grandi rispetto a quello di una rete random), λ≈1 (cioè una lunghezza media paragonabile a quella di una rete random) e σ>1. rappresenta, in un certo senso, una misura di quanto la rete è di piccolo mondo.

Un anno dopo il lavoro di Watts & Strogatz, Barabási & Albert (1999) si accorsero che un grande numero di reti reali presentavano pochi nodi molto connessi e molti nodi poco connessi, cioè il valore di non seguiva una distribuzione gaussiana, come ci si sarebbe aspettato nelle reti random o nelle reti di piccolo mondo, ma la distribuzione di grado seguiva una legge di potenza, completamente diversa dalla distribuzione normale, che può essere espressa come:

(2.12)

Il significato di una legge di questo tipo individua un particolare modello di crescita della rete stessa: cioè un nodo che possiede un grado tenderà ad aumentare il suo grado man mano che la rete cresce in misura tanto maggiore quanto maggiore è il suo grado. Quindi i nodi più connessi diventeranno via via più connessi. Al contrario, i nodi con un minor numero di connessioni aumenteranno i legami assai lentamente. Questo vale ad esempio per il World Wide Web, (Albert et al., 1999), per Internet (Faloutsos et al., 1999), e per le reti metaboliche (Jeong et al.,2000). Barabási e collaboratori (Barabási et al., 1999) definirono queste reti scale free, in quanto presentano le tipiche invarianze di scala delle strutture frattali.

42 La (2.12) può essere scritta in forma logaritmica come (2.13)

e quindi su scala logaritmica otterremo una retta che lega il logaritmo della probabilità della sua distribuzione al logaritmo del grado.

In questo tipo di reti emergono naturalmente dei nodi con grado altissimo, che sono detti hub. Lo studio e la distribuzione degli hub è di grande interesse pratico perché è strettamente legato all’efficienza della rete. La rimozione di un hub da una rete non avrà lo stesso effetto della rimozione di un qualsiasi altro nodo dalla rete.

Queste reti possono essere create facilmente. Ad esempio, la rete di Figura 2.10 è stata creata a partire da un grafo di tre nodi connessi tra loro, aggiungendo un nodo con due archi ad ogni passo. I due archi sono attaccati a caso agli altri nodi, seguendo una distribuzione proporzionale al grado del nodo. Gli hub sono chiaramente visibili perché hanno le dimensioni più grandi rispetto agli altri nodi.

Figura 2.10. Una rete di 200 nodi generata tramite il modello di Barabási con un attaccamento preferenziale.

43

Nella Figura 2.11, si presenta come si distribuiscono i nodi in funzione del grado.

Figura 2.11. Distribuzione dei nodi in funzione del grado nella rete della Figura 2.10 seguendo il modello di distribuzione di Barabási.