(Laboratorio di )
Sistemi Informatici Avanzati
Giuseppe Manco
GRAFI
Teoria dei grafi
Grafi
• Dimensione, ordine
• Degree, degree distribution
• Sottografi
• Cammini, componenti
• Geodetica
• Alcuni grafi particolari
• centralità
Grafi diretti
• Diadi e triadi
• Cmmini, geodetia,
componenti
fortemente/debolmente
connesse
• Centralità
• Alcuni grafi diretti
particolari
Definizione
• Un grafo G è una coppia (V,E) di vertici (V) e
archi (E)
Grafo indiretto
Digrafo
Archi simmetrici
Archi diretti
L
A
M
F
D
B
C
I
D
G
B
E
G
H
A
C
coauthorship links
Actor network
protein interactions
F
URLs su www
Chiamate telefoniche
metabolic reactions
Dimensione, ordine
• Dimensione
– Numero di nodi in V
• Ordine
– Numero L di archi in E
Dimensione 7
Ordine 8
Grado
• Il numero di archi in un grafo
A
B
kB = 4
kA =1
• I grafi diretti definiscono in-degree e out-degree.
D
B
kCin  2
C
E
G
A
F
kCout  1
kC  3
Grado medio
1
k 
N
j
i
D
B
k
C
in
1

N
 ki
i 1
N
k , k
i 1
in
i
2L
k º
N
N
out
1

N
N
out
in
out
k
,
k

k
 i
i 1
E
A
F
L
k º
N
Grafi completi
Ordine massimo
Lmax
æ N ö N(N -1)
=ç ÷=
2
è2ø
Un grafo di ordine L=Lmax è un grafo completo
Il grado medio è
k º N -1
Sparsità
• Rapporto tra il numero effettivo di archi e il
massimo numero di archi
d=
2L
N (N - 1)
d=
2´8
= 8 / 21
7´6
Alcune reti
• Estrema sparsità
L << Lmax
or
<k> <<N-1.
WWW (ND Sample):
Protein (S. Cerevisiae):
Coauthorship (Math):
Movie Actors:
N=325,729;
N= 1,870;
N= 70,975;
N=212,250;
L=1.4 106
L=4,470
L=2 105
L=6 106
Lmax=1012
Lmax=107
Lmax=3 1010
Lmax=1.8 1013
<k>=4.51
<k>=2.39
<k>=3.9
<k>=28.78
(Sorgente: Albert, Barabasi, RMP2002)
N
L
<k>
(Sorgente: : The structure and function of complex
networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)
Metcalfe’s law
Lmax
æ N ö N(N -1)
=ç ÷=
2
è2ø
(Sorgente: Barabasi,
http://spectrum.ieee.org/computing/networks/met
Matrice di adiacenza
Aij=1 se esiste un arco (i,j)
4
4
3
2
1
1
æ
ç
A=ç
ç
çè
0
1
0
1
3
2
1
0
0
1
0
0
0
1
1
1
1
0
ö
÷
÷
÷
÷ø
æ
ç
A=ç
ç
çè
0
1
0
0
0
0
0
1
0
0
0
1
1
0
0
0
ö
÷
÷
÷
÷ø
Matrice di adiacenza
a
e
h
b
f
g
c
d
a
b
c
d
e
f
g
h
a
0
1
0
0
1
0
1
0
b
1
0
1
0
0
0
0
1
c
0
1
0
1
0
1
1
0
d
0
0
1
0
1
0
0
0
e
1
0
0
1
0
0
0
0
f
0
0
1
0
0
0
0
0
g
1
0
1
0
0
1
0
0
h
0
1
0
0
0
0
0
0
1
1
1
0
Aij = A ji
Aii = 0
2
1
3
0
0
0
0
1
0
0
1
0
0
0
1
j =1
N
k j = å Aij
i=1
N
N
1
1
L = å ki = å Aij
2 i=1
2 ij
1
0
0
0
ö
÷
÷
÷
÷ø
N
4
æ
ç
A=ç
ç
çè
ki = å Aij
ij
0
0
0
1
N
out
i
k
= å Aij
i =1
N
Aij ¹ A ji
Aii = 0
k
1
1
0
0
1
i=1
3
2
0
1
0
1
N
= åA
4
ö
÷
÷
÷
÷ø
in
j
æ
ç
A=ç
ç
çè
N
L = åk = åk
in
i
i=1
j=1
N
out
j
= å Aij
i, j
Grafi speciali
• Grafo vuoto con 5 nodi (Z5)
• Stella con 5 vertici
• Ciclico con 5 vertici
• Albero
• Foresta
Indiretto
Digrafo
4
4
1
1
2
2
3
æ
ç
A=ç
ç
çè
3
0
1
1
0
1
0
1
1
Aii = 0
N
1
L = å Aij
2 i, j=1
1
1
0
0
0
1
0
0
ö
÷
÷
÷
÷ø
Aij = A ji
2L
< k >=
N
Actor network, protein-protein interactions
æ
ç
A=ç
ç
çè
0
0
1
0
1
0
0
0
Aii = 0
L=
N
åA
ij
i, j=1
WWW, citation networks
0
1
0
0
0
1
0
0
ö
÷
÷
÷
÷ø
Aij ¹ A ji
L
< k >=
N
Non pesato
Pesato
4
4
1
1
2
2
3
æ
ç
A=ç
ç
çè
3
0
1
1
0
Aii = 0
N
1
L = å Aij
2 i, j=1
1
0
1
1
1
1
0
0
0
1
0
0
ö
÷
÷
÷
÷ø
Aij = A ji
2L
< k >=
N
protein-protein interactions, www
æ 0 2 0.5 0 ö
ç 2 0 1 4 ÷
A=ç
÷
ç 0.5 1 0 0 ÷
çè 0 4 0 0 ÷ø
Aii = 0
N
1
L = å nonzero(Aij )
2 i, j=1
Call Graph, metabolic networks
Aij = A ji
2L
< k >=
N
auto-archi
multigrafo
4
4
1
1
2
2
3
æ
ç
A=ç
ç
çè
3
1
1
1
0
1
0
1
1
1
1
0
0
Aii ¹ 0
N
0
1
0
1
ö
÷
÷
÷
÷ø
æ
ç
A=ç
ç
çè
Protein interaction network, www
2
0
1
3
1
1
0
0
Aij = A ji
Aii = 0
?
1
L = å nonzero(Aij )
2 i, j=1
N
N
1
L=
Aij + å Aii
å
2 i, j=1,i¹ j
i=1
0
2
1
0
ö
÷
÷
÷
÷ø
0
3
0
0
Aij = A ji
2L
< k >=
N
Social networks, collaboration networks
Completo (K4)
4
1
2
3
æ0
ç
1
ç
Aij =
ç1
ç
è1
1 1 1ö
÷
0 1 1÷
1 0 1÷
÷
1 1 0ø
Aii = 0
N(N -1)
L = Lmax =
2
Ai¹ j = 1
< k >= N -1
Actor network, protein-protein interactions
I grafi reali
• WWW
– multigrafo diretto, auto-archi
• Protein Interactions
– Indiretto non pesato con auto-archi
• Collaboration network
– Indiretto, multigrafo, pesato
• Chiamate a telefonia
– Diretto, pesato
• Collegamenti Facebook
– Indiretto
Grafo bipartito
• Nodi suddivisi in due gruppi
– Nessun arco ammesso nello stesso gruppo
Hollywood actor network
Collaboration networks
Disease network (diseasome)
• Grafi completi bipartiti
DISEASOME
GENOME
Goh, Cusick, Valle, Childs, Vidal & Barabási, PNAS (2007)
PHENOME
Sottografo
• Un sottoinsieme W di V che include tutti gli
archi in E relativi a W
Diade
• Sottografo di due nodi
æ N ö
D0 = ç
-L
÷
è 2 ø
D1 = L
• Dyad census: (D0,D1)
Diade
N numero di coppie senza archi
A numero di coppie con un solo arco
M numero di coppie con più archi
Dyad census: (M,A,N)
Triade
• Sottografo di dimensione 3
T0 =
1
(1- Aij )(1- Aik )(1- A jk )
å
6 i, j,k
1
T1 = å (1- Aij )(1- Aik )A jk
6 i, j,k
1
T2 = å (1- Aij )Aik A jk
6 i, j,k
T3 =
1
Aij Aik A jk
å
6 i, j,k
Triade
• Tryad census: il conteggio dei 16 tipi di grafi
elencati sopra
Cammini
• Un cammino è una sequenza di nodi adiacenti
(ovvero, collegati da un arco)
1.2.4
1.3.5.6
1.3.4.5.7
1.2
2.1
1.3.4
4.2.1.3
Cammini tra due nodi
Nij numero di cammini tra i e j
N
2
N (2)
=
A
A
=
[A
]ij
å ik kj
ij
k =1
N
N ij(3) = å[A 2 ]ik Akj = [A3 ]ij
k=1
N ij = [A ]ij
(n)
n
Raggiungibilità
• Se esiste un cammino da A a B, allora B è
raggiungibile da A
• Se ogni vertice è raggiungibile da un altro,
allora il grafo è connesso
Componenti connesse
• Una componente connessa di un grafo
indiretto è un sottografo massimale connesso
B
A
C
D
Componenti connesse
• Se ogni nodo di un digrafo è raggiungibile da
un altro, allora il grafo è fortemente connesso
• Se ogni nodo di un digrafo è raggiungibile da
un altro senza considerare il verso degli archi,
allora il grafo è debolmente connesso
• Una componente connessa
(debolmente/fortemente) è un sottografo
massimale (debolmente/fortemente)
connesso
Connettività, componenti
La matrice di adiacenza di un grafo con molte componenti può essere rappresentata a
blocchi
La componente gigante
• Una componente che racchiude la maggior parte del grafo
Distanza
La distanza geodetica (geodesic path) tra due nodi è il
B
cammino di lunghezza minima tra questi due nodi
A
*se i due nodi sono sconnessi, la distanza è infinita
C
D
B
Nei digrafi il verso conta
A
La distanza tra A e B può essere diversa da quella tra B e A
C
D
Diametro, distanza media
dmax la distanza massima tra una coppia di nodi nel grafo.
Distanza media, <d>, per un grafo connesso:
1
= d º
dij
å
2Lmax i, j¹i
dij è la distanza tra i e j
Su un grafo indiretto, dij =dji , quindi
1
d º
dij
å
Lmax i, j>i
N
L
<k>
(Sorgente: : The structure and function of complex
networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)
MISURE SU GRAFI
Cutpoints
• Un vertice è un cutpoint se la sua rimozione
aumenta le componenti di un grafo
Ponti
• Un arco è un bridge (ponte) se la sua
rimozione aumenta le componenti
– Grafo senza ponti
Connettività
• La connettività k (G) di un grafo G è il minimo
numero di nodi che bisogna eliminare per
rendere il grafo disconnesso
Connettività (archi)
• Il minimo numero l (G) di archi da eliminare
per rendere il grafo disconnesso
Edge-connectivity
Connectivity
Centralità
• Il grado di centralità (potenziale di
comunicazione) è il grado (normalizzato) di un
nodo
Cd (a) = ka
C d (a) =
4
C d (x) =
6
ka
L -1
Closeness
• Potenziale di comunicazione indipendente
1
CD (a) =
å dab
b
L -1
C D (a) =
å dab
b
CD (a) = 1/ (1+1+1+1+ 2 + 2) = 1/ 8
C D (a) = 6 / 8
Betweeness
• Il numero di cammini che contengono a
BD (a) =
N i, j|a
N ij
B D (a) =
Ni, j|a
Nij (L2 - 3L + 2)
BD (a) = 14
B D (a) = 7 /15
Coefficiente di clustering
• Quanti dei tuoi vicini sono connessi da un arco?
1
C = å Ci
N i
• Alternativamente
3 ´ numero di triangoli nel grafo
C=
numero di triple connesse
Nodi su una linea
P(k) = d (k - 4)
C=
k = 4 per ogni nodo
1
per ogni nodo se N > 6
2
d max
1+ å 4 » N Þ d max
l =1
N
»
4
d max
<d> =
4 åd
d =1
N
Þ
N
<d> »
8
N
L
<k>
(Sorgente: : The structure and function of complex
networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)
Degree distribution
Degree distribution P(k): probabilità che un vertice scelto in maniera
casuale abbia grado k
Nk = # nodi di grado k
P(k) = Nk / N
P(k)
0.6
0.5
0.4
0.3
0.2
0.1
1
2
3
4
k
Degree distribution e reti reali
• Right-skewed
– Una coda lunga di valori molto lontani dal valore
medio
– Complicata da misurare
• Istogrammi su scale esponenziali
– Power laws
Cumulative degree distribution
¥
Pk = å pk '
k '=k
(Sorgente: : The structure and function of complex
networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)
Power laws
• Probabilità di un valore che varia in misura
inversamente proporzionale ad una potenza di
quel valore
Distribuzioni classiche
Distribuzioni power law
Distribuzioni power law
• Poche città con una grande popolazione, molte città
con una popolazione piccola
– 40 città della dimensione di New York
– 2700 città con meno di 110,000.
• Plottando l’istogramma, su scale logaritmiche,
otteniamo una linea retta
Power law
• Possiamo rappresentare gli istrogrammi con
ln(y) = Aln(x) + c
• Se p(x) rappresenta la distribuzione tra x e x +
dx
– E l’istogramma è una linea in scala log-log
ln p(x) = -a ln(x) + c
p(x) = Cx
-a
Power law
• Piccole occorrenze estremamente comuni
• Grandi occorrenze molto rare
• Occorrono in diversi fenomeni
–
–
–
–
–
–
–
–
–
city populations
Grado dei terremoti, crateri lunari, tempeste solari
computer files
Frequenze d’uso delle parole nel linguaggio umano
Il numero di articoli che un ricercatore scrive
Il numero di citazioni di un articolo
Il numero di link di una pagina web
Le vendite di un libro
…
Power law: Social networks
Numero di azioni che un utente compie (digg)
Numero di amicizie (flixster)
Plottare le power-laws
• α = 2.5
• Istogramma
con
equal binning
I I Measuring power
laws
1.5
10
(a)
1
samples
samples
10
0.5
10
0
2
4
6
-1
-3
-4
10
0
(b)
-2
10
10
0
-5
8
1
10
ples
10
10
-1
-3
(c)
x
th value > x
x
10
10
0
-2
(d)
La scala lineare
• La relazione power-law non apparente
• Ha senso se si guarda a pochi bin
5
5
x 10
5
4.5
4.5
4
4
3.5
3.5
frequency
frequency
5
3
2.5
2
3
2.5
2
1.5
1.5
1
1
0.5
0.5
0
0
2
4
6
8
10
12
14
16
integer value
Range limitato
18
20
x 10
0
0
1000
2000
3000
4000
5000
6000
integer value
Intero range
7000
8000
9000 10000
Log-log plot
• Le potenze spaziate in maniera uniforme
1
2
3
10
20
30
100
200
20=1, 21=2, 22=4, 23=8, 24=16, 25=32,
26=64, ….
Log-log plot
• Metodo più comune
• Non necessariamente accurato
ln (# di occorrenze di x)
ln(x)
Plottare le power laws
Molte
osservazioni
quando x < 10
Rumore sulla
coda, molta
variabilità
Logarithmic binning
• La size dei bin aumenta in progressione
geometrica
– 0.1, 0,2, 0.4, ….
• Normalizzazione: il numero di elementi in un
intervallo di ampiezza Δx va diviso per Δx
stesso per rendere il conteggio unitario
– Il dato normalizzato diventa indipendente
dall’ampiezza
Plottare le power laws
• Logarithmic binning
Ancora
rumore
Distribuzione cumulativa
• Nessuna perdita di informazione
– P(x) = P(X>x)
– Il risultato è ancora una power-law con esponente
α – 1.
10
(a)
samples
10
(b)
-1
-2
Plottare le power laws
10
10
10
-4
• Cumulative distribution
10
0
-3
2
4
6
-5
8
1
10
x
samples with value > x
x
(c)
1
10
100
x
100
1000
10
10
10
0
(d)
-2
-4
1
10
100
1000
x
set of 1 million random numbers described in t he t ext , which have a power-law dist ribut ion wit h
same hist ogram on logarit hmic scales. Not ice how noisy t he result s get in t he t ail t owards t he
T his happens because t he number of samples in t he bins becomes small and st at ist ical fluct uat ions
n of sample number. (c) A hist ogram const ruct ed using “ logarit hmic binning” . (d) A cumulat ive
plot of t he same dat a. T he cumulat ive dist ribut ion also follows a power law, but wit h an exponent
Power laws, Pareto distribution, Zipf's law
• Le distribuzioni cumulative sono anche chiamate
rank/frequency distributions.
• Le cumulative che seguono una powe law sono
anche dette Zipf o Pareto
– “Zipf’s law” e“Pareto distribution” sono sinonimi di
“power-law distribution”.
• Le differenze sono essenzialmente nel plot
– Zipf x sull’asse orizzontale, P(x) su quello verticale
– Pareto al contrario
Cumulative, rank/frequency
• Si ordinano le misurazioni
– Si plotta il rank sulla misurazione
Stimare una power-law
• Va individuato il valore xmin da cui la powerlaw comincia
• xmin è maggiore di 0
– Perché?
Stimare α dai dati
• Si trova lo slope direttamente dalla linea
– Nell’esempio precedente, il logarithmic binning produce α
= 2.26 ± 0.02
• Si estrae l’esponente utilizzando la formula
– α = 2.500 ± 0.002 nell’esempio precedente
Esempi di
power laws
N
L
<k>
(Sorgente: : The structure and function of complex
networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)
Non tutto è una power law
Non tutto è una power law
• Exponential tails
p(x) = Ce
-a x
– Distribuzione cumulativa ancora esponenziale
– Semi-logarithmic plot
Maximum degree
• Il grado oltre il quale non ci sono più nodi
npkmax = 1
• Su una power-law, otteniamo
1/a
kmax µ n
– Stima approssimativa
Maximum degree
• Una stima più accurata
– Un grafo con esattamente m vertici di grado k e
nessun vertice di grado maggiore di k ha
probabilità
– Probabilità che il grado più alto sia k
Resilience
• Studio della connettività
• Se alcuni vertici sono rimossi, la lunghezza dei
cammini aumenta
– Alcuni nodi divengono disconnessi
• Livello di resilience correlato alla distanza media
– Epidemiologia
– Robustezza ad attacchi
Uno studio
• World Wide Web
– Un frammento di 326.000 pagine
– Distribuzione Power-law
• Due strategie di removal
– Random
– Rimozione progressiva dei vertici di grado più alto
Risultato
• Cosa possiamo concludere?
Risultato
• Cosa possiamo concludere?
– Alta tollerabilità ai “fallimenti” random
– Estrema vulnerabilità ai “fallimenti” degli hub