Reti Complesse
seconda lezione
Programma
I.
Alcuni Esempi di reti complesse
II.
Concetti base di teoria dei grafi e delle reti
III.
Modelli
IV.
La rete come insieme di comunità
Bibliografia
• Evolution of networks
S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002),
cond-mat/0106144
• Statistical mechanics of complex networks
Reka Albert, Albert-Laszlo Barabasi
Reviews of Modern Physics 74, 47 (2002), cond-mat/0106096
• The structure and function of complex networks
M. E. J. Newman, SIAM Review 45, 167-256 (2003),
cond-mat/0303516
• Complex networks: structure and dynamics
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang
Physics Reports 424, 175-308 (2006)
Definizione di Network
Network=insieme di vertici (nodi) uniti da
legami (links)
Rappresentazione molto astratta
molto generale
Utile per descrivere
sistemi molto diversi
Esempi
Nodi
Links
Reti sociali
Individui
Relazioni sociali
Internet
Routers
AS
Webpages
Cavi + coll. wireless
Accordi commerciali
Hyperlinks
Proteine
Reazioni chimiche
WWW
Rete di interazione
tra proteine
Argomento interdisciplinare
Reti complesse sono importanti per:
-teoria dei grafi
-sociologia
-scienza delle comunicazioni
-biologia
-fisica
-informatica
Piano della lezione
1) Breve introduzione ai concetti base di
teoria dei grafi
2) Approccio statistico: Ensemble di grafi,
distribuzioni di probabilità e correlazioni
3) Reti pesate.
Obiettivo
Definire una serie di osservabili che
permettano di caratterizzare un sistema
complesso e che forniscano indicazioni per
spiegare i meccanismi microscopici che
hanno portato alla formazione del sistema
1) Introduzione alla teoria dei grafi
-
Definizioni di base
Matrice di adiacenza
Densità
Cammini e connettività
Alberi
Centralità
Clustering
Teoria dei grafi
Grafo G=(V,E)
• V=insieme di vertici i=1,…,N
• E=insieme di links (i,j)
Link ordinario:
Link diretto :
i
j Bidirezionale
comunicazione/
interazione
i
j
Teoria dei grafi
Numero massimo di links
• Non diretti: N(N-1)/2
• Diretti: N(N-1)
Grafo completo:
(interazione “tutti con tutti”)
Matrice di adiacenza
N nodi i=1,…,N
1 if (i,j)  E
0 if (i,j)  E
aij=
0
1
2
3
0
0
1
1
1
1
1
0
1
1
2
1
1
0
1
3
1
1
1
0
0
1
2
3
Matrice di adiacenza
N nodi i=1,…,N
1 if (i,j)  E
0 if (i,j)  E
aij=
0
1
2
3
0
0
1
0
0
1
1
0
1
1
2
0
1
0
1
3
0
1
1
0
Simmetrica se i link non
sono diretti.
0
1
2
3
Matrice di adiacenza
N nodi i=1,…,N
1 if (i,j)  E
0 if (i,j)  E
aij=
0
1
2
3
0
0
0
0
0
1
1
0
1
1
2
0
0
0
1
3
1
0
0
0
Non simmetrica
Se i links sono diretti
0
1
2
3
Densità di un grafo
Densità di un grafo: D=|E|/(N(N-1)/2)
Numero dei links
D=
Massimo num. di links possibile
Matrice di adiacenza
con pochi 1 e molti 0
Rappresentazione: lista dei vicini di ogni nodo
Grafo “sparso”: D <<1
l(i, V(i))
V(i)= vicini di i
Cammini
G=(V,E)
Cammino di lunghezza n = lista ordinata di
• n+1 vertici i0,i1,…,in 
V
• n links (i0,i1), (i1,i2)…,(in-1,in)  E
i3

i4
i0
i1
 i2
i5
Ciclo/loop = cammino chiuso (i0=in)
Alberi
Un albero è un grafo senza cicli
• N nodi, N-1 links
Cammini e connettività
G=(V,E) è connesso se e solo se esiste un cammino
che connette ogni coppia di nodi di G .
È connesso
• non è connesso
• è formato da due componenti
Cammini e connettività
G=(V,E)=> distribuzione delle componenti connesse
Componente gigante= componente la cui
dimensione cresce in modo proporzionale
al numero di vertici N
Esistenza di una
componente gigante
Una frazione
macroscopica dei nodi
del grafo è connessa
Cammino minimo (shortest path)
Cammino minimo tra i e j: numero minimo di links
necessari a congiungere i e j
distanza l(i,j)= cammino
j
minimo tra i and j
i
Diametro di un grafo= max(l(i,j))
Cammino minimo medio = ij l(i,j)/(N(N-1)/2)
Grafo completo: l(i,j)=1 per tutte le coppie i,j .
“Piccolo mondo”(Small-world): “piccolo” diametro
Centralità
Come quantificare l’importanza di un nodo?
• Grado (degree)=numero di vicini =j aij
ki=5
i
(grafi diretti: kin, kout)
“Betweenness centrality”
Per ogni coppia di nodi (l,m) , definisco:
slm numero di cammini minimi tra l e m
silm num. di cammini minimi che passano per i
bi è la somma silm / slm su tutte le coppie (l,m)
Importante: è una quantità basata sui cammini
i
j
bi è grande
bj è piccola
NB: quantità simile: “load” li= silm
NB: generalizzazione: “link betweenness centrality”
“Clustering
”Coefficiente di clustering di un nodo
k
3
C(i) =
i
2
# di links tra 1,2,…n vicini
k(k-1)/2
1
Clustering: c’è un’alta probabilità che i miei amici si conoscano!
(esempio tipico: social networks)
Clustering
Coefficiente di clustering medio di un grafo
C=i C(i)/N
2) Approccio statistico
-
Distribuzione di probabilità dei gradi
Correlazioni a più punti
Rappresentazione spettrale
Assortatività e dissortatività
Distribuzione dei gradi
•Lista dei gradi k1,k2,…,kN
Non molto utile!
•Istogramma:
Nk= numero dei nodi di grado k
•Distribuzione:
P(k)=Nk/N=probabilità che un nodo scelto a
caso abbia grado k
•Distribuzione cumulativa:
P>(k)=probabilità che un nodo scelto
a caso abbia grado almeno k
Distribuzione dei gradi
P(k)=Nk/N= probabilità che un nodo scelto a caso
abbia grado k
Media=< k > = i ki/N = k k P(k)=2|E|/N
Grafo “sparso”: < k > << N
Fluttuazioni: < k2 > - < k > 2
< k2 > = i k2i/N = k k2 P(k)
< kn > = k kn P(k)
Correlazioni a più punti dei gradi
P(k): non è sufficiente a descrive un network
Reti “assortative”:
Nodi di grado alto
preferiscono connettersi con
altri nodi di grado alto.
Ex: social networks
Reti “dissortative”:
Nodi di grado alto
preferiscono connettersi a nodi
di grado basso.
Ex: technological networks
Correlazioni a più punti dei gradi
Misura della correlazione:
P(k’,k’’,…k(n)|k): probabilità condizionale che un nodo di
grado k sia connesso a nodi di grado k’, k’’,…
Caso più semplice:
P(k’|k): probabilità condizionale che un nodo di grado k
sia connesso ad un nodo di grado k’
Correlazioni a più punti dei gradi
misura “pratica” di correlazione :
Grado medio dei primi vicini
k=4
k=4
i
k=7
k=3
ki=4
knn,i=(3+4+4+7)/4=4.5
Grado medio dei primi vicini
“Spettro di correlazione”:
Costruito mettendo assieme
nodi con lo stesso grado
Class di grado k
Esempio: rete casuale e scorrelata
P(k’|k) indipendente da k
(ricorda: P(k’|k) = prob. che un link di grado k
punti ad un nodo di grado k’)
numero di link uscenti da un nodo di grado k’
numero di link uscenti da un nodo qualsiasi
Punc(k’|k)=k’P(k’)/< k >
proporzionale
a k’ stesso
Assortatività
• Comportamento Assortativo :
knn(k) è una funzione crescente di k
Esempio: social networks
• Comportamento Dissortativo:
knn(k) è una funzione decresente di k
Esempio: internet (struttura gerarchica)
3) Reti pesate
1) Definizioni ed esempi
2) Coefficiente di clustering pesato
3) Assortatività pesata
Reti pesate
Nelle reti reali i links:
• Portano traffico (reti di trasporti, Internet…)
• Hanno intensità diverse (social networks…)
Descrizione generale: pesi
i wij
j
aij: 0 or 1
Wij: variabile continua
Pesi: esempi
- Collaborazioni scientifiche: numero di articoli in
comune
Internet, emails: numero di emails scambiati
●
Aereoporti: numero di passeggeri
●
Reti metaboliche: flussi
●
Reti economiche: numero di azioni possedute
●
…
●
In generale si pone: wii=0
Ed il peso è simmetrico: wij=wji
Reti Pesate
I pesi stanno sui link (weigths)
Forza (Strength) di un nodo:
si = j  V(i) wij
=>Generalizza in modo naturale la nozione di grado alle reti pesate

=>Esempio: quantifica il traffico totale che passa per un nodo.
Coefficiente di clustering
pesato
i
i
wij=1
wij=5
si=16
ciw=0.625 > ci
ki=4
ci=0.5
si=8
ciw=0.25 < ci
Coefficiente di clustering
pesato
k
(wjk)
wik
i
wij
j
Coefficiente di clustering medio
C=i C(i)/N
Cw=i Cw(i)/N
Se i pesi sono random: C = Cw
C < Cw : piu pesi sui grafi completi (cliques)
C > Cw : meno pesi sui grafi completi (cliques)
Rappresentazione spettrale del Clustering:
Assortatività pesata
5
5
1
5
i
5
ki=5; knn,i=1.8
Assortatività pesata
1
1
5
1
i
1
ki=5; knn,i=1.8
Assortatività pesata
5
5
1
5
i
5
ki=5; si=21; knn,i=1.8 ; knn,iw=1.2:
knn,i > knn,iw
Assortatività pesata
1
1
5
1
i
1
ki=5; si=9; knn,i=1.8 ; knn,iw=3.2: knn,i
< knn,iw
“Participation ratio”
1/ki se tutti i pesi sono uguali
vicino a 1 se alcuni pesi dominano