Rotundo_reti - Università degli Studi di Udine: Home

RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
Giulia Rotundo
Università degli Studi della Tuscia
[email protected]
1
90
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
2
90
AREE DI
STUDIO
FISICA
TEORIA DELLA PERCOLAZIONE
COMPLEX NETWORKS
RANDOM NETWORKS
TEORIA DEI GRAFI
INFORMATICA
COMBINATORIA
RICERCA OPERATIVA
MATEMATICA
3
90
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
1. Definizione di network; esempi;
2. Dalle random network alle
complex network: esempi dal
mondo reale e proprietà
importanti;
3. Processi diffusivi su reti;
4. Self-organized criticality;
5. Applicazioni economiche e
finanziarie.
4
90
1.
Definizione
RANDOM + NETWORKS
•rete
•grafo (graph)
(Sylvester (1878) Nature)
Un grafo è un insieme di:
Nodi
(vertici, unità)
Archi (edges, lines).
Un arco unisce due nodi.
5
Applicazioni: i grafi servono per creare modelli astratti di problemi concreti
Leonhard Euler (1707-1783)
6
90
•
esempio
Koenigsberg ed il problema dei 7 ponti
(Eulero, 1736)
Cammino (path): Sequenza di nodi uniti da archi
Problema:
Esiste un cammino che attraversi tutti i ponti
percorrendo ciascuno di essi una volta sola ?
Lunghezza del cammino= N. dei suoi archi
PROBLEMI DI CAMMINO MINIMO
7
•
esempio
PROBLEMI DI CAMMINO MINIMO
Applicazioni:
•Il problema del commesso viaggiatore
•Problemi di trasporto
•Logistica
•Instradamento del flusso dati (reti di comunicazione)
•…
Osservazione: Limite superiore per la lunghezza del cammino
Diametro
lunghezza del path più lungo
tra due nodi del grafo
Osservazione:
studio del caso peggiore del cammino minimo= studio del diametro
8
90
1.
Definizione
RANDOM + NETWORKS
•rete
Utilizzo di metodi
•grafo (graph)
(Sylvester (1878) Nature)
probabilistici
Studio delle
proprietà che valgono
con alta probabilità per grafi
ottenuti utilizzando particolari
distribuzioni di probabilità
per selezionare nodi ed
archi.
9
90
1.
esempio
RANDOM NETWORKS
Primo articolo sui random graphs (Erdos e Renyi, 1959)
Rete con N nodi e connettendo ogni coppia di nodi con probabilità p
Osservazione: Il numero delle coppie di nodi è N(N-1)/2
Osservazione: il valore atteso del numero di archi m è E(m)= p N(N-1)/2
Domande classiche:
Come dipende il diametro dal numero di nodi?
Esiste un cammino che tocca tutti i nodi (ovvero, il grafo è connesso)?
Ci sono cammini del tipo
(triangoli) ?
Obbiettivo: trovare la soglia pc oltre la quale le proprietà sono verificate quasi sempre.
10
90
1.
esempio
RANDOM NETWORKS
Scoperta principale: per molte proprietà p(N) esiste pc(N) tale che
- Se la p(N) cresce con N più velocemente di pc(N) allora quasi ogni grafo con
probabilità di connessione p(N) ha la proprietà
- Se la p(N) cresce con N più lentamente di pc(N) allora quasi ogni grafo con
probabilità di connessione p(N) NON ha la proprietà
Domande classiche:
1. Come dipende il diametro dal numero di nodi?
2. Esiste un cammino che tocca tutti i nodi (ovvero, il grafo è connesso)?
3. Ci sono triangoli ?
Risposte: 1. diametro=O(log(N))
=pN<1, no
2. -Se il valore medio degli
archi uscenti da un nodo è
3. solo se p>=1/N
> 1 no, ma il diametro è lo
stesso di un
grafo
dello stesso tipo e connesso
11
90
1.
esempio
Differenze di approccio tra le varie discipline
Ricerca operativa
Formalizzazione matematica e calcolo della soluzione
Ottima; algoritmi.
Percolazione
Studio delle componenti connesse
Utilizzo della probabilità e soprattutto del calcolo combinatorio
Random networks
per lo studio della dipendenza del diametro dal numero dei
nodi ed archi
Utilizzo della probabilità per studiare reti con particolari
Complex networks
strutture e proprietà
12
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
1. Definizione di network; esempi;
2. Dalle random network alle
complex network: esempi dal
mondo reale e proprietà
importanti;
3. Processi diffusivi su reti;
4. Self-organized criticality;
5. Applicazioni economiche e
finanziarie.
13
90
2.
Dalle random network alle complex network
RANDOM
NETWORKS
grafi ottenuti utilizzando
particolari distribuzioni
di probabilità per selezionare
nodi ed archi.
COMPLEX
NETWORKS
grafi con proprietà
topologiche non banali
Il termine “COMPLEX” è in opposizione a “SEMPLICE”
Reti “SEMPLICI” sono quelle con struttura regolare, come le
griglie (lattice) oppure grafi completi (ciascun nodo è collegato
con ciascun altro).
14
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
15
90
2.Dalle random network alle complex network
1. clustering coefficient
Gli amici dei miei amici sono miei amici?
Proprietà di transitività
C
A è amico di B che è
amico di A e C, ma A e
C non sono amici
B
A
D
Clustering
coefficient
=
N. triangoli
N. triangoli
cui manca un arco
=
+
+
16
90
2.Dalle random network alle complex network
1. clustering coefficient C
Gli amici dei miei amici sono miei amici?
Reti complesse:
Reti sociali
Reti tecnologiche
17
90
2.Dalle random network alle complex network
1. clustering coefficient C
Gli amici dei miei amici sono miei amici?
reti “puramente” random: C=O(n-1)
Griglie non triangolari: C=0
Grafi totalmente connessi: C=1
18
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
19
90
2.Dalle random network alle complex network
2. betweenness (centrality)
Esprime l’importanza di un nodo nel grafo
Numero dei cammini più brevi tra
qualsiasi coppia di nodi che passa
attraverso v
C(v)=
Numero dei cammini più brevi tra
qualsiasi coppia di nodi
Esempio: il nodo
betweenness
(rosso=0,blu=massimo)
ha C(v) più alto
20
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
21
90
2.Dalle random network alle complex network
3. small world
il diametro della rete è piccolo rispetto al
numero di nodi N
(<=log(N))
Fotografia di un poster nella metro di Parigi che
pubblicizzava una serie di eventi musicali (agosto 2007)
Esempi (reti sociali):
•
esperimento del sociologo Stanley Milgram (1967):
è possibile contattare chiunque tramite (in media)
d=6 conoscenti
•
Per gli attori di Hollywood (in media) d=3.65
•
Co-autori matematici (in media) d =9.5
22
90
2.Dalle random network alle complex network
3. small world
Kevin Bacon number:
Numero di conoscenze intermedie per arrivare a
Kevin Bacon (gioco del 1994)
Esempio 1
Nick
Nolte
CAPE FEAR
Robert
De Niro
GOODFELLAS
Joe
Pesci
JFK
Kevin
Bacon.
Grado di separazione di Nick Nolte: 3
Esempio 2
Val Kilmer
TOP GUN
Tom Cruise
A FEW GOOD MAN
Kevin Bacon
23
Grado di separazione di Val Kilmer: 2
2.Dalle random network alle complex network
3. small world
Erdős–Bacon number:
Erdős : matematico ungherese
Numero di Erdős = lunghezza della più breve
catena di coautori in cui solo l’ultimo ha scritto
un lavoro con Erdős
Erdős–Bacon number=
Erdős number + Bacon number
Esempio: Erdős ha Bacon number 3:
Erdős -> N is a number: a portait of Paul Erdős ->
Mark Adler -> Rat Pack -> Joe Mantegna -> Sognando Manhattan K.Bacon
24
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
25
90
2.Dalle random network alle complex network
4. scale-free
Grado di un nodo = numero di archi uscenti
Grado 1
Grado 2
Grado 3
Per ogni rete si può calcolare la probabilità P(k) del grado k dei nodi
Reti scale-free: P(k) k-
26
90
2.Dalle random network alle complex network
4. scale-free
27
90
2.Dalle random network alle complex network
4.a confronto small-world e scale-free
Sono “small world” le reti in cui la
distribuzione di probabilità del grado dei nodi
single-scale network
Decresce rapidamente.
Esempi: random networks (decrescita esponenziale), traffico tra aeroporti, rete di
conoscenti: comunità mormone dello Utah, studenti della scuola superiore.
broad-scale network
Decresce polinomialmente fino ad un certo punto e poi più rapidamente (cutoff)
Esempi: movie-actor network
scale-free network
Decresce polinomialmente
Esempi: rete di citazione di lavori scientifici, www,
Internet (router, domini), reti elettriche, rete neurale del
verme caenorhabditis elegans, …
28
2.Dalle random network alle complex network
4.a confronto small-world e scale-free
Osservazione: le griglie NON sono
small world e NON sono scale-free
Lattice d=1
Lattice d=2
Lattice d=3
Come costruire una rete scale-free?
29
90
2.Dalle random network alle complex network
4.b algoritmi per le scale-free networks
preferential attachment
I nuovi nodi che sono aggiunti alla rete sono collegati più facilmente a nodi che
hanno più archi.
Modelli di reti sociali
30
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
31
90
2.Dalle random network alle complex network
5. assortativity/disassortativity
Correlazione
tra i gradi di nodi uniti da archi
Assortative networks:
I nuovi nodi che sono aggiunti alla rete sono collegati
più facilmente a nodi che hanno più archi.
Esempi: reti sociali
Disassortative networks:
Nodi con pochi archi sono collegati con nodi
con molti archi e viceversa. Esempio: reti tecnologiche
32
90
Grafo dei collegamenti dalla pagina
principale di wikipedia
33
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
34
90
2.Dalle random network alle complex network
6. community structure
I nodi si dividono in gruppi con
- alta densità di connessioni fra di loro e
- bassa densità di connessioni verso gli altri
Esempio:
rete di amicizie
nelle scuole
35
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
36
90
2.Dalle random network alle complex network
7. strutture gerarchiche
Caso particolare della suddivisione
In communities
37
90
2.
Dalle random network alle complex network
Proprietà importanti:
1. Clustering
2. Betweenness
3. Small world
4. Scale-free
a.Confronto small word e scale-free
b.Algoritmi per la costruzione scale free
5. Assortativity/disassortativity
6. Community structure
7. Hierarchical structure
8. Resilience
38
90
2.Dalle random network alle complex network
8. resilience
Robustezza delle reti rispetto a rimozione random
dei nodi
-scale-free: rimozione di piu’ del 99% dei nodi
Interventi mirati: isolare gli hubs (nodi piu’ connessi)
Assortative: rimuovere il “club” centrale
Disassortative: gli hubs sono sparsi nella rete
39
90
2.Dalle random network alle complex network
8. resilience
• Robustezza delle reti rispetto a rimozione random dei
nodi
-scale-free: rimozione casualedi piu’ del 99% dei nodi
Interventi mirati: isolare gli hubs
• Assortative: rimuovere il “club” centrale
• Disassortative: rimuovere gli hubs sparsi nella rete
La proprietà di resilience è particolarmente importante nello studio della
diffusione di epidemie.
40
90
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
1. Definizione di network; esempi;
2. Dalle random network alle
complex network: esempi dal
mondo reale e proprietà
importanti;
3. Processi diffusivi su reti;
4. Self-organized criticality;
5. Applicazioni economiche e
finanziarie.
41
90
3. Processi diffusivi
La struttura della rete è importante per lo studio
dei processi diffusivi
Problema importante per la diffusione delle
epidemie. Esempio: diffusione della SARS
Interventi mirati: isolare gli hubs
42
90
3. Processi diffusivi
Importanza della struttura dei primi vicini:
diffusione delle epidemie
Disassortative
Neutral
Assortative
t
43
90
3. Processi diffusivi
importanza della struttura dei primi vicini
Diffusione dell’informazione
44
3. Processi diffusivi
importanza della struttura dei primi vicini
The Diffusion of Innovations in Social Networks
H. Peyton Young
[..] New ideas and ways of doing things do not necessarily take hold all
at once, but often spread gradually through social networks. In a
classic study, Coleman, Katz, and Menzel (1966) showed how
doctors‘ willingness to prescribe the new antibiotic
tetracycline diffused through professional contacts.
A similar pattern has been documented in the adoption of
family planning methods, new agricultural practices,
and a variety of other innovations (Rogers and Shoemaker,
1971; Rogers and Kincaid, 1981; Rogers, 1983; Valente, 1995).
In the first stage a few innovators adopt, then people in
contact with the innovators adopt, then people in
contact with those people adopt, and so forth until
eventually the innovation spreads throughout the
society. [..]
45
90
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
1. Definizione di network; esempi;
2. Dalle random network alle
complex network: esempi dal
mondo reale e proprietà
importanti;
3. Processi diffusivi su reti;
4. Self-organized criticality;
5. Applicazioni economiche e
finanziarie.
46
90
3. Self-organized criticality
Self-organized criticality
“
Modello di Bak e
Sneppen
is a property of (classes of) dynamical
systems which have a critical point as an
attractor.
Their macroscopic behaviour thus displays
the spatial and/or temporal scale-invariance
characteristic of the critical point of a phase
transition, but without the need to tune
control parameters to precise values.
”
47
90
1-d Bak-Sneppen Evolution Model
•L agents
•Fitness
fi (t ), i  1, N
•Drawn at t=0: uniform distribution in (0,1)
•coevolution:
•at each time step t the lowest fi and its first
2
min(fi)
neighbours are replaced by a uniform sampling
48
90
Caratteristiche per
N 
Soglia critica fc: i valori di fi hanno una distribuzione
uniforme al di sopra di un valore fc : fi  ( fc ,1)
Avalanche:
Durata di un avalanche= tempo che intercorre tra due istanti in cui tutti i
valori sono al di sopra di fc

Probabilità di avere un avalanche di durata s:
P( s )  s
Media delle fitness
1
f (t )  d
L
Ld
 f (t )
i 1
i
f av  ( f avc ,1)
49
Modello co-evolutivo
Fase transiente
Fase stabile 50
90
2-d Bak-Sneppen Evolution Model
•L2 agents
•Fitness fi (t ), i  1, N
• drawn at t=0 : uniform distribution
•coevolution:
•at each time step t the lowest fi and its first
4
neighbours are replaced by a uniform sampling
51
90
52
90
RANDOM NETWORKS
per le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
1. Definizione di network; esempi;
2. Dalle random network alle
complex network: esempi dal
mondo reale e proprietà
importanti;
3. Processi diffusivi su reti;
4. Self-organized criticality;
5. Applicazioni economiche e
finanziarie.
53
90