Capitolo I Le reti complesse
2
Una maniera usuale di disegnare i grafi è quella di rappresentare i nodi
con dei punti, collegandoli con un tratto qualora esista un link fra
questi.
La Figura 1.1 mostra un esempio di rappresentazione di un grafo
orientato (a sinistra) e non orientato con sette nodi e otto connessioni.
Figura 1.1 - rappresentazione grafica di un grafo orientato (a sinistra) e non orientato (a
destra) composto da sette nodi e otto archi.
Poiché le reti che saranno oggetto della nostra analisi sono
modellabili tramite grafi non orientati, nel prosieguo della
trattazione ci riferiremo solo a tale tipologia di grafo.
Rappresenteremo una rete attraverso la sua matrice delle adiacenze
Α, una matrice quadrata di dimensione pari al numero N di nodi della
rete, il cui elemento generico aij (i, j = 1, ...., N) è pari a uno se il
collegamento lij esiste, e zero viceversa.
Capitolo I Le reti complesse
3
Nel nostro caso di studio, essendo il grafo non orientato, la matrice è
simmetrica rispetto alla diagonale principale.
1.2 GRADO DI UN NODO
Il grado ki di un nodo i è il numero di archi collegati a i, e si definisce
considerando la matrice delle adiacenze A come:
Dove aij è il generico elemento della matrice di adiacenze A ed N il
numero totale di nodi.
1.3 SHORTEST PATH
Un’importante proprietà di una rete è la raggiungibilità di due nodi
differenti. Due nodi non adiacenti, infatti, potrebbero non essere
raggiungibili l’uno dall’altro. Un cammino (walk) dal nodo i al nodo j è
una sequenza di nodi adiacenti che inizia in i e termina in j. Due nodi
non adiacenti, dunque, sono raggiungibili l’uno dall’altro se esiste un
∑
=
=
N
j
iji
ak
1
Capitolo I Le reti complesse
4
cammino che li unisce. La lunghezza del cammino è definita come il
numero d’archi attraversati partendo dal nodo i e arrivando al nodo j .
Un percorso (path) è un cammino in cui nessun nodo è visitato più di
una volta. Il percorso di lunghezza minima è detto percorso più breve
(shortest path).
I percorsi più brevi giocano un ruolo fondamentale per il trasporto
d’informazioni all’interno di una rete. Supponiamo che un utente debba
inviare un pacchetto da un computer ad un altro della rete Internet: se il
pacchetto giunge a destinazione tramite il percorso più breve tra i due
nodi, si garantisce un trasferimento più veloce e si minimizza lo
sfruttamento di risorse della rete.
Si usa rappresentare la lunghezza di tutti i percorsi più brevi di un
grafo G in un’unica matrice D, in cui ciascun elemento dij è la
lunghezza del percorso più breve tra il nodo i e j. Un’importante
proprietà della rete è la lunghezza media dei percorsi più brevi L (nota
anche come distanza media), definita come la media dei percorsi più
brevi, calcolata su tutte le coppie di nodi della rete:
∑
≠∈−
=
jiNji
ij
d
NN
N
L
,,
)1(
dove N è il numero totale di nodi.
Capitolo I Le reti complesse
5
E’ auspicabile che una rete abbia un valore di L che sia il più basso
possibile, poiché ciò implica che ciascuna coppia di nodi è in grado di
comunicare con un minor numero di passi.
1.4 COEFFICIENTE DI CLUSTERING
La proprietà di clustering, o transitività, di un grafo misura il grado di
conoscenza di una rete, ossia la tendenza di due nodi adiacenti ad un
nodo comune di essere connessi l’uno con l’altro. In altre parole, il
coefficiente di clustering misura l’importanza di un nodo, infatti, si
basa sulla valutazione del numero d’archi del grafo qualora il nodo in
esame fosse estratto dalla rete.
Prima di tutto occorre definire la quantità ci, il coefficiente di
clustering relativo ad un nodo i. Quest’ultimo quantifica la probabilità
che ajm = 1 per i nodi j e m che sono entrambi adiacenti al nodo i.
Il coefficiente di clustering del nodo i-esimo si definisce come:
2/)1( −
=
ii
i
i
kk
e
c
Capitolo I Le reti complesse
6
Dove ki è il numero di nodi adiacenti al nodo i, mentre ei rappresenta il
numero di archi che connettono direttamente i nodi adiacenti a i che al
massimo sono 2/)1( −
ii
kk .
Si definisce il coefficiente di clustering C dell’intera rete come la
media di tutti i ci :
∑=
i
i
c
N
C 1
Per costruzione, 0 ≤ ci ≤ 1, e 0 ≤ C ≤ 1. Un alto valore del coefficiente
C indica che sono presenti molte connessioni tra nodi vicini. Al limite,
per una rete totalmente connessa C è pari a uno.
1.5 CENNI STORICI E TOPOLOGIE DI RETI
Negli ultimi anni la ricerca ha prodotto nuovi strumenti per la
valutazione della struttura di reti che hanno portati a risultati
sorprendenti; molte analogie tra diversi sistemi permettono un
approccio più semplice e generale nell'analisi delle cosiddette
“networks”. Questi risultati consentono di riconoscere, sotto
l‘apparente disordine dei sistemi organizzati (internet, reti biologiche e
sociali, reti di trasporto), i segni di un ordine nascosto.
Lo studio di una grande varietà di sistemi ha permesso di definire delle
proprietà comuni a diverse networks, quale per esempio quella di
Capitolo I Le reti complesse
7
essere caratterizzati da una struttura fondata su pochi nodi connettori
(tipica dei sistemi di trasporto metropolitano) e cosiddetta Scale-free
(Barabàsi e Albert, 1999) oppure dall’estrema vicinanza dei
collegamenti tra i nodi (Watts e Strogatz, 1998), nonostante le
dimensioni dell’intera rete (reti Small World). Tali strutture e le
relative misure matematiche consentono l'individuazione delle criticità
d’ogni parte del sistema, in relazione al comportamento globale
della rete, in caso di avarie e/o attacchi esterni.
Di seguito saranno presentate le caratteristiche generali dei più comuni
tipi di rete esistenti.
1.6 RETICOLI REGOLARI
Nella topologia a reticolo regolare i nodi della rete sono posizionati in
modo regolare, formando una struttura cristallina, e ognuno di essi è
caratterizzato dallo stesso numero di archi, e dunque dallo stesso grado
k. La Figura 1.5 mostra un esempio di grafo a struttura regolare con
venti nodi e quattro connessioni per nodo.
Essendo le connessioni solo locali, la comunicazione tra nodi distanti
può avvenire solo tramite un numero piuttosto alto di nodi intermedi.
Ragion per cui la distanza media L risulta essere elevata, tanto più
elevata quanto più grande è il numero dei nodi della rete, evidenziando
quindi delle pessime caratteristiche globali.
Capitolo I Le reti complesse
8
Al contrario l’alto numero di connessioni locali fa sì che tale topologia
abbia ottime qualità locali, essendo caratterizzata da un valore elevato
del coefficiente di clustering C.
Figura 1.6(a) – Rappresentazione grafica di un reticolo regolare
1.7 LE RETI SCALE-FREE E SMALL-WORLD
I sistemi biologici e chimici, le interazioni ed i rapporti sociali, Internet
e il World Wide Web sono soltanto alcuni esempi dei cosiddetti sistemi
complessi Small World e Scale-free; essi sono particolari strutture di
rete composte da un gran numero di unità interconnesse tra loro che
scambiano informazioni dinamicamente ed evolvendosi nel tempo.
Capitolo I Le reti complesse
9
Figura 1.7(a) – Esempio di costruzione di una rete Small World: lo spostamento di
alcune connessioni rende le distanze tra i nodi comparabili a quelle di una rete random. Il
grado di interconnessione locale inoltre aumenta a livello di quello di una rete regolare
(Watts D.J., Strogatz S.H. (1998) “Collective dynamics of ‘Small World’ networks”,
Nature, 393, pp. 440-442).
In particolare le reti Scale-free,di cui viene riportato un esempio in
Figura 1.7(b), sono caratterizzate da pochi nodi aventi un numero di
connessioni molto elevato (Hubs) e molti nodi aventi un numero
ridotto di connessioni (nodi secondari) come, per esempio, le reti
aeroportuali, internet e le reti di trasporto metropolitano.
Capitolo I Le reti complesse
10
Figura 1.7(b) – Grafo di una rete scale-free con 130 nodi
Per questo motivo è possibile identificare tali sistemi dalla curva
γ−= kkP )( che rappresenta la probabilità che un nodo abbia grado
di connessione k: essa segue un andamento proporzionale ad un
esponente γ che varia tra 1 e 2 per la maggior parte di reti Scale-free
reali, come è possibile osservare in Figura 1.7(c).
Tali sistemi sono quindi molto stabili in caso di avarie ma molto
vulnerabili ad attacchi mirati verso i nodi più connessi.
Capitolo I Le reti complesse
11
Figura 1.7(c) – Distribuzione a legge di Potenza (Power-Law), caratteristica delle reti
scale-free
Le reti Small World sono caratterizzate invece da due misure princi
pali: L (‘Characteristic Path Length’) che definisce la distanza media
tra due nodi qualsiasi del sistema e C (‘Clustering Coefficient’) che
misura quanto i nodi siano localmente interconnessi. Le reti Small
World sono definite per bassi valori di L ed elevati valori di C in una
dimensione a metà tra reti completamente ordinate e reti random.
Negli ultimi dieci anni, questi particolari sistemi fisici sono stati
oggetto di numerosi studi tesi a determinare le proprietà comuni a
diversi tipi di rete e le loro dinamiche. Le reti Small World e Scale-
free, grazie alle loro proprietà, consentono di modellizzare diversi tipi
Capitolo I Le reti complesse
12
di reti reali al fine di determinare gli elementi chiave necessari a
garantire la più completa efficienza nelle comunicazioni tra i nodi.
1.8 LE RETI RANDOM
Lo studio dei grafi di tipo random fu introdotto da Erdos e Renyi nel
1959. La costruzione di un grafo random, con N nodi e K archi, parte
dalla condizione iniziale di N nodi privi di connessioni. Il grafo è,
dunque, generato inserendo un arco tra coppie di nodi scelti in maniera
casuale, come in Figura 1.8(a), impedendo connessioni multiple tra la
stessa coppia di nodi, ripetendo l’operazione fino a quando il numero
d’archi raggiunge la quantità prestabilita K.
Figura 1.8(a) – Rappresentazione grafica di un grafo casuale (random)
Capitolo I Le reti complesse
13
Per come è costruito il grafo, i nodi, a differenza del reticolo regolare,
non presenteranno il medesimo grado k. Ciò nonostante l’insieme dei
valori assunti dal parametro k è limitato e circoscritto ad un piccolo
intervallo di valori. Pur differendo tra loro, i nodi hanno comunque un
valore del grado pressochè comparabile, e nessuno di essi prevale
nettamente sugli altri.
Per alti valori di N, la distribuzione dei gradi dei nodi è ben
approssimata da una distribuzione di Poisson avente valore massimo in
corrispondenza del grado medio < k > come è possibile osservare in
Figura 1.8(b).
Figura 1.8(b) – Distribuzione di Poisson, tipica delle reti casuali (random)
Capitolo I Le reti complesse
14
I grafi random sono caratterizzati da buone qualità globali, infatti, la
distanza media L aumenta lentamente all’aumentare di N, e risulta
abbastanza piccola anche in reti con un elevato numero di nodi. Di
contro, questa topologia di grafo presenta qualità locali non buone,
essendo caratterizzato, infatti, da un basso valore del coefficiente di
Clustering .
In questo lavoro di tesi sono stati sviluppati nuovi modelli di reti basati
sul coefficiente di clustering. Inoltre, in funzione di una soglia
prestabilita, porteranno a delle connessioni basate sul preferential
attachment oppure di tipo random (casuali).
Per ogni valore della soglia saranno commentati i risultati ottenuti ed
esposti i grafici dei parametri caratteristici della rete ottenuta al variare
della suddetta soglia.
Capitolo II Il modello base
15
CAPITOLO 2
IL MODELLO BASE
In questo modello la configurazione di partenza della rete è costituita
da tre nodi completamente connessi tra loro.
Ad ogni step dell’algoritmo si aggiunge un nuovo nodo che verrà
connesso ai nodi presenti nella rete secondo due criteri specifici.
Il primo criterio si basa sul “preferential attachment”, ovvero sulla
probabilità che il nodo si connetta preferenzialmente ad uno o più nodi
della rete con specifiche caratteristiche, trascurandone altri.
Il secondo criterio invece impone che le connessioni vengano effettuate
in modo completamente casuale e quindi senza alcuna preferenza di un
nodo rispetto ad un altro.
Per ogni simulazione del modello sono settati a priori il numero
massimo di nodi ed una soglia compresa tra 0 e 1, in funzione della
quale verrà selezionato uno dei due criteri di connessione.
Ogni volta che un nuovo nodo è aggiunto alla rete, viene generato un
numero casuale che viene successivamente confrontato con il valore di
soglia prefissato.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
