1

IL PARADIGMA DELLE RETI IL PARADIGMA DELLE RETI DINAMICHE PER LA DINAMICHE PER LA

CARATTERIZZAZIONE DI MODELLI DI CARATTERIZZAZIONE DI MODELLI DI MOTO COLLETTIVO MOTO COLLETTIVO

CANDIDATO

GIUSEPPE MARZIALE

RELATORE

ING. ALESSANDRO RIZZO

POLITECNICO DI BARI

FACOLTA’ DI INGEGNERIA INFORMATICA

2

SOMMARIOSOMMARIO

OBIETTIVO DELLA TESIOBIETTIVO DELLA TESI CONCETTI GENERALI SULLE RETI: CONCETTI GENERALI SULLE RETI:

PARAMETRI CARATTERISTICI E PARAMETRI CARATTERISTICI E TOPOLOGIETOPOLOGIE

IL MODELLO DI VICSEKIL MODELLO DI VICSEK PARALLELISMI TRA MODELLO DI PARALLELISMI TRA MODELLO DI

VICSEK E RETE DINAMICAVICSEK E RETE DINAMICA CONCLUSIONI E PROSPETTIVE CONCLUSIONI E PROSPETTIVE

FUTUREFUTURE

3

OBIETTIVO DELLA TESIOBIETTIVO DELLA TESI

ANALISI DEL MODELLO DI MOTO COLLETTIVO DI VICSEK

ATTRAVERSO IL PARADIGMA DELLE RETI DINAMICHE

4

CONCETTO DI RETE CONCETTO DI RETE COMPLESSACOMPLESSA

Una rete è un sistema costituito da molte entità,dette nodi,Una rete è un sistema costituito da molte entità,dette nodi, legate tralegate tra

loro e interagenti mediante connessioni. loro e interagenti mediante connessioni.

Una rete dinamica è una particolare categoria di rete in cui laUna rete dinamica è una particolare categoria di rete in cui latopologia delle connessioni è soggetta ad evolversi ed topologia delle connessioni è soggetta ad evolversi ed

adattarsi neladattarsi neltempotempo

Molti sistemi del mondo reale possono essere considerati retiMolti sistemi del mondo reale possono essere considerati reticomplesse e dinamiche ( es. Internet, la rete ferroviaria, la complesse e dinamiche ( es. Internet, la rete ferroviaria, la

reteretetelefonica ). telefonica ).

5

PARAMETRI CARATTERISTICI PARAMETRI CARATTERISTICI DELLE RETIDELLE RETI

Grado di un nodo (k): il numero di collegamentiche 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

6

TOPOLOGIE DI RETETOPOLOGIE DI RETE

I nodi sono posizionati in I nodi sono posizionati in maniera regolare a formare maniera regolare a formare una struttura cristallinauna struttura cristallina

Ciascun nodo è caratterizzato Ciascun nodo è caratterizzato dallo stesso numero di archi , dallo stesso numero di archi , e quindi dallo stesso grado.e quindi dallo stesso grado.

Buone caratteristiche locali: Buone caratteristiche locali: alto coefficiente di clusteringalto coefficiente di clustering

Qualità globali non buone: alto Qualità globali non buone: alto valore della distanza mediavalore della distanza media

RETICOLO REGOLARE

7

TOPOLOGIE DI RETETOPOLOGIE DI RETE

..

RETI RANDOM

Ogni nodo è collegato Ogni nodo è collegato casualmente con altri nodi casualmente con altri nodi (con grado fisso o casuale)(con grado fisso o casuale)

Ottime qualità globali: Ottime qualità globali: bassa distanza media tra i bassa distanza media tra i nodinodi

Pessime qualità locali: Pessime qualità locali: coefficiente di clustering coefficiente di clustering bassobasso

8

TOPOLOGIE DI RETETOPOLOGIE DI RETE

Fu introdotta da Watts & Strogatz Fu introdotta da Watts & Strogatz (1998) allo scopo di modellare la (1998) allo scopo di modellare la struttura di alcune reti reali come le struttura di alcune reti reali come le reti sociali, internet, le catene reti sociali, internet, le catene alimentari, aeroporti, etc....alimentari, aeroporti, etc....

Nasce da una topologia regolare in Nasce da una topologia regolare in cui alcuni link vengono spostati (a cui alcuni link vengono spostati (a distanza più lunga) con probabilità distanza più lunga) con probabilità bassa.bassa.

Fonde buone qualità locali e globali, Fonde buone qualità locali e globali, essendo caratterizzata da un basso essendo caratterizzata da un basso valore della distanza media e da un valore della distanza media e da un alto coefficiente di clusteringalto coefficiente di clustering

RETE SMALL WORD

9

MODELLO DI VISECKMODELLO DI VISECKCARATTERISTICH

E Il modello trae ispirazione dallo studio dei Il modello trae ispirazione dallo studio dei movimenti di gruppo di animali (es. stormi di movimenti di gruppo di animali (es. stormi di uccelli ) e può essere utilizzato per il uccelli ) e può essere utilizzato per il controllo di un gruppo di robotcontrollo di un gruppo di robot

Il modello si applica ad un numero prefissato Il modello si applica ad un numero prefissato NN di particelle che si muovono in uno spazio di particelle che si muovono in uno spazio tridimensionale di lato tridimensionale di lato L L

Le particelle si muovono con velocità Le particelle si muovono con velocità costante in modulo (costante in modulo (νν ) )

La posizione e la direzione iniziale delle La posizione e la direzione iniziale delle particelle nello spazio sono estratte particelle nello spazio sono estratte casualmentecasualmente

10

EQUAZIONI DEL MODELLOEQUAZIONI DEL MODELLO

Le particelle assumono, ad ogni passo dellaLe particelle assumono, ad ogni passo della

simulazione, la direzione media delle particelle chesimulazione, la direzione media delle particelle che

si trovano a una distanza inferiore del raggio disi trovano a una distanza inferiore del raggio di

interazione (interazione (ττ ) )

xi (t+1) = xi (t) + ν*Δtθi (t+1) = ‹θ(t)› τ + Δθ

))(cos(

))(sin(arctan(t)

t

t

11

MODELLO DI VISECKMODELLO DI VISECK

Parametro d’ordine: Parametro d’ordine:

velocità media normalizzata delle velocità media normalizzata delle particelleparticelle

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

12

CONNESSIONI DI LUNGO CONNESSIONI DI LUNGO RAGGIORAGGIO

Per migliorare le prestazioni del modello di Per migliorare le prestazioni del modello di VicsekVicsek

si introducono connessioni di lungo raggio.si introducono connessioni di lungo raggio.

Ad un determinato numero di particelle èAd un determinato numero di particelle è

concesso, ad ogni passo della simulazione , diconcesso, ad ogni passo della simulazione , di

creare collegamenti a lunga distanza con creare collegamenti a lunga distanza con particelleparticelle

situate al di fuori del loro raggio d’interazionesituate al di fuori del loro raggio d’interazione

13

EFFETTO DELLE EFFETTO DELLE CONNESSIONI 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

14

MODELLO DI VICSEK E RETI MODELLO DI VICSEK E RETI DINAMICHEDINAMICHE

Il modello di Vicsek può essere reinterpretato Il modello di Vicsek può essere reinterpretato attraverso il paradigma delle reti dinamicheattraverso il paradigma delle reti dinamiche

Le particelle possono essere viste come nodi Le particelle possono essere viste come nodi di una retedi una rete

Ciascun nodo della rete è connesso con i nodi Ciascun nodo della rete è connesso con i nodi che sono a distanza inferiore del raggio di che sono a distanza inferiore del raggio di interazioneinterazione

La topologia della rete è soggetta a La topologia della rete è soggetta a modificarsi dinamicamente in funzione della modificarsi dinamicamente in funzione della posizione assunta dalle particelle nello spazioposizione assunta dalle particelle nello spazio

15

RISULTATI RISULTATI SPERIMENTALISPERIMENTALI

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.

16

RISULTATI RISULTATI SPERIMENTALISPERIMENTALI

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)

17

CONCLUSIONICONCLUSIONI

Analisi del modello di collettivo di Vicsek Analisi del modello di collettivo di Vicsek attraverso il paradigma delle reti dinamicheattraverso il paradigma delle reti dinamiche

Realizzazione di un software per la Realizzazione di un software per la simulazione del modello di Vicsek e simulazione del modello di Vicsek e integrazione con il pajek per la valutazione integrazione con il pajek per la valutazione dei parametri delle retidei parametri delle reti

Intorduzione delle connessioni di lungo raggioIntorduzione delle connessioni di lungo raggio La rete in esame è risultata caratterizzata in La rete in esame è risultata caratterizzata in

tutte le prove da buone qualità globali, ma il tutte le prove da buone qualità globali, ma il coefficiente di clusterig è risultato sempre coefficiente di clusterig è risultato sempre relativamente bassorelativamente basso

18

PROSPETTIVE FUTUREPROSPETTIVE FUTURE La valutazione del parametri è stata La valutazione del parametri è stata

effettuata principalmente sul sistema a effettuata principalmente sul sistema a regime. In futuro sarà necessario regime. In futuro sarà necessario effettuare nuove simulazioni, rallentando la effettuare nuove simulazioni, rallentando la dinamica del sistema e valutando dinamica del sistema e valutando l’andamento dei parametri nella fase di l’andamento dei parametri nella fase di assestamento del sistema stesso. Potrebbe assestamento del sistema stesso. Potrebbe verificarsi, ad esempio, un cambiamento verificarsi, ad esempio, un cambiamento topologico della rete.topologico della rete.

Sarebbe opportuno ridefinire i parametri Sarebbe opportuno ridefinire i parametri d’analisi, adattandoli al concetto di rete d’analisi, adattandoli al concetto di rete dinamica. dinamica.