POLITECNICO DI BARI
FACOLTA’ DI INGEGNERIA INFORMATICA
IL PARADIGMA DELLE RETI
DINAMICHE PER LA
CARATTERIZZAZIONE DI MODELLI DI
MOTO COLLETTIVO
RELATORE
CANDIDATO
ING. ALESSANDRO RIZZO
GIUSEPPE MARZIALE
1
SOMMARIO





OBIETTIVO DELLA TESI
CONCETTI GENERALI SULLE RETI:
PARAMETRI CARATTERISTICI E
TOPOLOGIE
IL MODELLO DI VICSEK
PARALLELISMI TRA MODELLO DI
VICSEK E RETE DINAMICA
CONCLUSIONI E PROSPETTIVE FUTURE
2
OBIETTIVO DELLA TESI
ANALISI DEL MODELLO DI MOTO
COLLETTIVO DI VICSEK ATTRAVERSO
IL PARADIGMA DELLE RETI
DINAMICHE
3
CONCETTO DI RETE COMPLESSA
Una rete è un sistema costituito da molte entità,dette nodi, legate tra
loro e interagenti mediante connessioni.
Una rete dinamica è una particolare categoria di rete in cui la
topologia delle connessioni è soggetta ad evolversi ed adattarsi nel
tempo
Molti sistemi del mondo reale possono essere considerati reti
complesse e dinamiche ( es. Internet, la rete ferroviaria, la rete
telefonica ).
4
PARAMETRI CARATTERISTICI
DELLE RETI
Grado di un nodo (k): il numero di collegamenti
che insistono su un nodo
Distanza media (shortest path length) : la media dei
percorsi più previ che collegono ciascuna coppia di nodi
della rete
Coefficiente di clustering di un nodo: quantifica
l’importanza di un nodo valutando il numero di connessioni
della rete che permangono, qualora il nodo fosse eliminato
5
TOPOLOGIE DI RETE
RETICOLO REGOLARE




I nodi sono posizionati in maniera
regolare a formare una struttura
cristallina
Ciascun nodo è caratterizzato dallo
stesso numero di archi , e quindi dallo
stesso grado.
Buone caratteristiche locali: alto
coefficiente di clustering
Qualità globali non buone: alto valore
della distanza media
6
TOPOLOGIE DI RETE
RETI RANDOM
.



Ogni nodo è collegato
casualmente con altri nodi (con
grado fisso o casuale)
Ottime qualità globali: bassa
distanza media tra i nodi
Pessime qualità locali: coefficiente
di clustering basso
7
TOPOLOGIE DI RETE
RETE SMALL WORD



Fu introdotta da Watts & Strogatz (1998)
allo scopo di modellare la struttura di
alcune reti reali come le reti sociali,
internet, le catene alimentari, aeroporti,
etc....
Nasce da una topologia regolare in cui
alcuni link vengono spostati (a distanza più
lunga) con probabilità bassa.
Fonde buone qualità locali e globali,
essendo caratterizzata da un basso valore
della distanza media e da un alto
coefficiente di clustering
8
MODELLO DI VISECK
CARATTERISTICHE




Il modello trae ispirazione dallo studio dei movimenti di
gruppo di animali (es. stormi di uccelli ) e può essere
utilizzato per il controllo di un gruppo di robot
Il modello si applica ad un numero prefissato N di
particelle che si muovono in uno spazio tridimensionale
di lato L
Le particelle si muovono con velocità costante in
modulo (ν )
La posizione e la direzione iniziale delle particelle nello
spazio sono estratte casualmente
9
EQUAZIONI DEL MODELLO
Le particelle assumono, ad ogni passo della
simulazione, la direzione media delle particelle che
si trovano a una distanza inferiore del raggio di
interazione (τ )
xi (t+1) = xi (t) + ν*Δt
θi (t+1) = ‹θ(t)› τ + Δθ
 (t)

 sin(  (t ))
 arctan 
 cos( (t ))




 
10
MODELLO DI VISECK
Parametro d’ordine:
velocità media normalizzata delle particelle
Un valore del parametro pari a zero indica che le particelle
non sono coordinate e si muovono disordinatamente ,
mentre un valore pari ad uno indica che tutte le particelle
hanno assunto la stessa direzione
11
CONNESSIONI DI LUNGO
RAGGIO
Per migliorare le prestazioni del modello di Vicsek
si introducono connessioni di lungo raggio.
Ad un determinato numero di particelle è
concesso, ad ogni passo della simulazione , di
creare collegamenti a lunga distanza con particelle
situate al di fuori del loro raggio d’interazione
12
EFFETTO DELLE
CONNESSIONI
l’introduzione delle connessioni di lunga distanza porta ad un incremento
della velocità media normalizzata (curva rossa)
L’introduzione dei collegamenti a distanza velocizza la
sincronizzazione degli agenti, permettendo di raggiungere in un tempo
inferiore il valore di regime del parametro d’ordine
13
MODELLO DI VICSEK E RETI DINAMICHE




Il modello di Vicsek può essere reinterpretato
attraverso il paradigma delle reti dinamiche
Le particelle possono essere viste come nodi di una rete
Ciascun nodo della rete è connesso con i nodi che sono
a distanza inferiore del raggio di interazione
La topologia della rete è soggetta a modificarsi
dinamicamente in funzione della posizione assunta dalle
particelle nello spazio
14
RISULTATI SPERIMENTALI
Possiamo quindi valutare l’andamento dei parametri
caratteristici delle reti ( coefficiente di clustering, distanza
media, grado medio) in relazione all’evoluzione del
modello di Vicsek.
15
RISULTATI SPERIMENTALI
L’introduzione delle connessioni di lungo raggio porta ad un
aumento delle prestazioni. La distanza media diminuisce con l’
aumentare del numero di connessioni di lungo raggio (grafico a
sinistra); il coefficiente di clustering aumenta in maniera
sensibile (grafico a destra)
16
CONCLUSIONI




Analisi del modello di collettivo di Vicsek attraverso il
paradigma delle reti dinamiche
Realizzazione di un software per la simulazione del
modello di Vicsek e integrazione con il pajek per la
valutazione dei parametri delle reti
Intorduzione delle connessioni di lungo raggio
La rete in esame è risultata caratterizzata in tutte le
prove da buone qualità globali, ma il coefficiente di
clusterig è risultato sempre relativamente basso
17
PROSPETTIVE FUTURE


La valutazione del parametri è stata effettuata
principalmente sul sistema a regime. In futuro sarà
necessario effettuare nuove simulazioni, rallentando la
dinamica del sistema e valutando l’andamento dei
parametri nella fase di assestamento del sistema stesso.
Potrebbe verificarsi, ad esempio, un cambiamento
topologico della rete.
Sarebbe opportuno ridefinire i parametri d’analisi,
adattandoli al concetto di rete dinamica.
18