1
Giulia RotundoUniversità degli Studi della Tuscia
RANDOM NETWORKSper le applicazioni economiche e finanziarie
Udine, 16 gennaio 2008
90
2
RANDOM NETWORKSper le applicazioni economiche e finanziarie
90
3
MATEMATICA
COMBINATORIA
TEORIA DEI GRAFI
INFORMATICA
RANDOM NETWORKS
TEORIA DELLA PERCOLAZIONE
FISICAAREE DI STUDIO
COMPLEX NETWORKS
RICERCA OPERATIVA
90
4
RANDOM NETWORKSper 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.90
5
•rete
•grafo (graph) (Sylvester (1878) Nature)
1. Definizione
Nodi (vertici, unità)
Archi (edges, lines). Un arco unisce due nodi.
Un grafo è un insieme di:
Applicazioni: i grafi servono per creare modelli astratti di problemi concreti.
RANDOM + NETWORKS
6
Leonhard Euler (1707-1783)
90
7
Koenigsberg ed il problema dei 7 ponti(Eulero, 1736)
Problema:Esiste un cammino che attraversi tutti i ponti percorrendo ciascuno di essi una volta sola ?
• esempio
Lunghezza del cammino= N. dei suoi archi PROBLEMI DI CAMMINO MINIMO
Cammino (path): Sequenza di nodi uniti da archi
8Osservazione: studio del caso peggiore del cammino minimo= studio del diametro
• esempio
Applicazioni:•Il problema del commesso viaggiatore•Problemi di trasporto•Logistica•Instradamento del flusso dati (reti di comunicazione)• …
PROBLEMI DI CAMMINO MINIMO
Osservazione: Limite superiore per la lunghezza del cammino
Diametro
lunghezza del path più lungo tra due nodi del grafo
90
9
RANDOM + NETWORKS
•rete
•grafo (graph) (Sylvester (1878) Nature)
1. Definizione
Utilizzo di metodi
probabilistici
Studio delle proprietà che valgono
con alta probabilità per grafi ottenuti utilizzando particolari
distribuzioni di probabilità per selezionare nodi ed archi.
90
10
RANDOM NETWORKS
Primo articolo sui random graphs (Erdos e Renyi, 1959)
1. esempio
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.
90
11
RANDOM NETWORKS
Scoperta principale: per molte proprietà p(N) esiste pc(N) tale che
1. esempio
- 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à
Risposte: 1. diametro=O(log(N))
2. -Se il valore medio degli
archi uscenti da un nodo è
3. solo se p>=1/N
- 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 ?
=pN<1, no
> 1 no, ma il diametro è lo stesso di un grafo dello stesso tipo e connesso
>=ln(N) si’
90
12
Random networks
Formalizzazione matematica e calcolo della soluzione
Ottima; algoritmi.
Utilizzo della probabilità e soprattutto del calcolo combinatorio
per lo studio della dipendenza del diametro dal numero dei
nodi ed archi
Ricerca operativa
Complex networks
1. esempio
Differenze di approccio tra le varie discipline
Utilizzo della probabilità per studiare reti con particolari
strutture e proprietà
Studio delle componenti connessePercolazione
13
RANDOM NETWORKSper 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.90
14
RANDOM NETWORKS
grafi ottenuti utilizzando particolari distribuzioni di probabilità per selezionare nodi ed archi.
COMPLEXNETWORKS
grafi con proprietà topologiche non banali
2. Dalle random network alle complex network
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).
15
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
16
Gli amici dei miei amici sono miei amici?
2.Dalle random network alle complex network 1. clustering coefficient
Clustering coefficient =
N. triangoli
N. triangoli cui manca un arco + +=
AB
C
D
A è amico di B che è amico di A e C, ma A e C non sono amici
Proprietà di transitività
90
17
Gli amici dei miei amici sono miei amici?
2.Dalle random network alle complex network 1. clustering coefficient C
Reti sociali
Reti tecnologiche
90
Reti complesse:
18
Gli amici dei miei amici sono miei amici?
2.Dalle random network alle complex network 1. clustering coefficient C
reti “puramente” random: C=O(n-1)
90
Griglie non triangolari: C=0
Grafi totalmente connessi: C=1
19
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
20
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 ha C(v) più alto
betweenness (rosso=0,blu=massimo)
90
21
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
22
il diametro della rete è piccolo rispetto al numero di nodi N (<=log(N))
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
Fotografia di un poster nella metro di Parigi che pubblicizzava una serie di eventi musicali (agosto 2007)
2.Dalle random network alle complex network 3. small world
90
23
Kevin Bacon number:
Kevin Bacon.
Nick Nolte
CAPE FEAR Robert De Niro
GOODFELLAS Joe Pesci
JFK
Grado di separazione di Nick Nolte: 3
Val Kilmer Tom Cruise Kevin Bacon
Numero di conoscenze intermedie per arrivare a Kevin Bacon (gioco del 1994)
Grado di separazione di Val Kilmer: 2
TOP GUN A FEW GOOD MAN
Esempio 1
Esempio 2
2.Dalle random network alle complex network 3. small world
24
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
2.Dalle random network alle complex network 3. small world
90
25
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
26
Grado 1Grado 2 Grado 3
Per ogni rete si può calcolare la probabilità P(k) del grado k dei nodi
Grado di un nodo = numero di archi uscenti
2.Dalle random network alle complex network 4. scale-free
Reti scale-free: P(k) k-
90
27
2.Dalle random network alle complex network 4. scale-free
90
28
single-scale network
Decresce rapidamente.
Esempi: random networks (decrescita esponenziale), traffico tra aeroporti, rete di conoscenti: comunità mormone dello Utah, studenti della scuola superiore.
Sono “small world” le reti in cui la distribuzione di probabilità del grado dei nodi
2.Dalle random network alle complex network 4.a confronto small-world e scale-free
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, …
29
Osservazione: le griglie NON sono small world e NON sono scale-free
Lattice d=1 Lattice d=2Lattice d=3
Come costruire una rete scale-free?
2.Dalle random network alle complex network 4.a confronto small-world e scale-free
90
30
preferential attachment
I nuovi nodi che sono aggiunti alla rete sono collegati più facilmente a nodi che hanno più archi.
2.Dalle random network alle complex network 4.b algoritmi per le scale-free networks
Modelli di reti sociali
90
31
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
32
Assortative networks:I nuovi nodi che sono aggiunti alla rete sono collegati più facilmente a nodi che hanno più archi.
2.Dalle random network alle complex network 5. assortativity/disassortativity
Esempi: reti sociali
Correlazione tra i gradi di nodi uniti da archi
Disassortative networks:
Nodi con pochi archi sono collegati con nodi
con molti archi e viceversa. Esempio: reti tecnologiche90
33
Grafo dei collegamenti dalla pagina principale di wikipedia
90
34
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
35
I nodi si dividono in gruppi con - alta densità di connessioni fra di loro e - bassa densità di connessioni verso gli altri
2.Dalle random network alle complex network 6. community structure
Esempio:
rete di amicizie
nelle scuole
90
36
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
37
2.Dalle random network alle complex network 7. strutture gerarchiche
90
Caso particolare della suddivisione
In communities
38
Proprietà importanti:
2. Dalle random network alle complex network
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. Resilience90
39
Robustezza delle reti rispetto a rimozione random dei nodi
-scale-free: rimozione di piu’ del 99% dei nodi
2.Dalle random network alle complex network 8. resilience
Interventi mirati: isolare gli hubs (nodi piu’ connessi)
Assortative: rimuovere il “club” centraleDisassortative: gli hubs sono sparsi nella rete
90
40
Interventi mirati: isolare gli hubs
• Robustezza delle reti rispetto a rimozione random dei nodi
-scale-free: rimozione casualedi piu’ del 99% dei nodi
2.Dalle random network alle complex network 8. resilience
• Assortative: rimuovere il “club” centrale• Disassortative: rimuovere gli hubs sparsi nella rete
90
La proprietà di resilience è particolarmente importante nello studio della diffusione di epidemie.
41
RANDOM NETWORKSper 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.90
42
La struttura della rete è importante per lo studio
dei processi diffusivi
3. Processi diffusivi
Problema importante per la diffusione delle epidemie. Esempio: diffusione della SARS
Interventi mirati: isolare gli hubs 90
43
Importanza della struttura dei primi vicini:
diffusione delle epidemie
3. Processi diffusivi
DisassortativeNeutralAssortative
t90
44
Diffusione dell’informazione3. Processi diffusivi importanza della struttura dei primi vicini
45
The Diffusion of Innovations in Social NetworksH. 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. [..]
3. Processi diffusivi importanza della struttura dei primi vicini
90
46
RANDOM NETWORKSper 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.90
47
3. Self-organized criticality
Self-organized criticality
“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.
”
Modello di Bak e Sneppen
90
48
1-d Bak-Sneppen Evolution Model
•L agents
•Fitness
•Drawn at t=0: uniform distribution in (0,1)
•coevolution:•at each time step t the lowest fi and its first
2 neighbours are replaced by a uniform sampling
( ), 1,if t i N
min(fi)
90
49
Caratteristiche perSoglia critica fc: i valori di fi hanno una distribuzione
uniforme al di sopra di un valore fc :
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:
Media delle fitness
1
1( ) ( )
dL
idi
f t f tL
N
( ,1)i cf f
( ,1)av avcf f
( )P s s
50
Modello co-evolutivo
Fase transiente
Fase stabile90
51
2-d Bak-Sneppen Evolution Model
•L2 agents
•Fitness • 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
( ), 1,if t i N
90
52 90
53
RANDOM NETWORKSper 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.90