Università degli Studi di Pisa
Dipartimento di Informatica
Lezione n.20
POWER LAW
SCALE FREE NETWORKS
Materiale Didattico
Van Steen, GRAPH THEORY ANDCOMPLEX NETWORKS
Cap 7
Laura Ricci
8/5/2013
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
1
INTRODUZIONE

Distribuzioni power law

Che tipo di processo genera una distribuzione power law?

Reti scale free


Il modello di Barabasi Albert
Applicazioni per reti P2P
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
2
INTRODUZIONE
Esistono molti tipi di rete
●
sociali
●
tecnologiche
●
ecologiche (preda-predatore, proteine,...)
che sono caratterizzate dall'essere
●
small world
●
clusterizzate
●
scale free: caratterizzate da una distribuzione power law
Nella lezione di oggi vogliamo capire
●
cosa è una distribuzione power law
●
come si può modellare una rete con tale distribuzione
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
3
SCALA LOGARITMICA: RICHIAMI
si consideri l'asse cartesiano x ed una serie di valori x 1,...xn.

ogni valore xi è rappresentato sull'asse ad una distanza dall'origine pari a
log10(x) (trasformazione di variabili X = log10 x )


poichè per valori crescenti dell'argomento la curva logaritmica cresce
sempre più lentamente, la distanza di un valore dall'origine aumenta
sempre più lentamente
il valore 1 si trova distanziato di 0 unità rispetto alla origine, il valore 10
distanziato di 1, il valore 100 distanziato di 2 e così via
●
i valori 101 , 102 , 103 , . . .(potenze della base) sono equamente
distanziati poichè il loro logaritmo in base 10 restituisce i valori 1,2,3,..
●
la distanza dei valori intermedi tra una potenza di 10 e la successiva
(ad.esempio 2,..5,...9) è sempre più smorzata
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
4
DISTRIBUZIONE POWER LAW
P(x)= C *x-α


una distribuzione di probabilità viene detta power law se la probabilità che una
certa variabile casuale assuma un certo valore x decresce ad una potenza -α di
x, con α valore costante (in generale α compreso tra 2 e 3)
la probabilità decresce all'aumentare di α, ma non esponenzialmente (-α
costante)

ad esempio: probabilità di avere una città di 100 abitanti....

probabilità di avere una città con 1000000 di abitanti bassa, ma non 0

molte città con pochi abitanti, poi una lunga coda di città con un numero molto
inferiore di abitanti,
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
5
POWER LAW SU SCALA LOGARITMICA


Una power law viene rappresentata come una retta se si utilizza un grafico con
scala logaritmica per entrambi gli assi (log-log graph)
Consideriamo la seguente power law
y=k * xα
se si passa ai logaritmi si ottiene
log(y) = α log(x) + log(k)
applicando la trasformazione X=log(x), Y=log(y) (scala logaritmica)

per m=α e q=log(k) possiamo ricondurci alla retta
Y = mX + q
dove m, il coefficente angolare della retta, dipende da α
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
6
LINEARIZZAZIONE FUNZIONI POTENZA

la funzione rappresentata a sinistra è una funzione di potenze, power law
y=k * xα

in scala log-log la funzione viene rappresentata come una retta

la potenza α determina il coefficente angolare della rette
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
7
POWER LAW VS. ESPONENZIALE
Distribuzione Esponenziale:
la probabilità di trovare un valore molto grande diventa rapidamente 0
Distribuzione Power Law:
presenta una lunga coda (heavy tail, right skew)
la probabilità di trovare un valore molto alto è bassa, ma non nulla:
infinite variance
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
8
POWER LAW VS. ESPONENZIALE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
9
DISTRIBUZIONE GAUSSIANA DELLE ALTEZZE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
10
DISTRIBUZIONE POWER LAW

Distribuzione power law (o zipfiana), caratteristiche:

right skew (skew=distorto), heavy tailed

La maggior parte delle città hanno pochi abitanti, ma esistono anche
molte città con un gran numero di abitanti, in proporzione sono poche
e tutte con un numero diverso di abitanti

alto rapporto tra il valore massimo ed il valore minimo

popolazione delle città negli USA:
New YorK City:popolazione: 8 milioni, Duffield, Virginia, popolazione
52 abitanti: rapporto 150000

distribuzione normale (non heavy tailed)

le altezze dei maschi nella popolazione umana, centrate su 180 cm

uomo più alto 272 cm, uomo più basso 57 centimetri: rapporto 4.77
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
11
DISTRIBUZIONE POWER LAW
high skew: asimmetria
●
lineare in una scala log-log
●
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
12
POWER LAW ONNIPRESENTI....
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
13
POWER LAW ONNIPRESENTI....
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
14
UBIQUITA' DELLE POWER LAW



Molti sistemi reali presentano un comportamento 'power law'

Non seguono una distribuzione normale o esponenziale
Esempi:

Grado dei nodi in Gnutella

Distribuzione delle latenze in Internet

Interazione tra proteine: poche proteine che interagiscono con molte
altre

Potenza distruttrice dei terremoti

Lunghezza dei fiumi

Ricchezza delle persone

Negli esempi precedenti l'esponente della power law è sempre circa 2.5
La “power law” è la distribuzione classica per modellare “sistemi complessi”
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
15
LA REGOLA 20-80

un modo di dire, con un fondamento scientifico...

valida per tutti i sistemi che seguono una distribuzione power law

20% dei siti Web ricevono 80% delle visite

20% dei routers Internet gestisce l'80% del traffico

20% delle industrie mondiali possiede l'80% dei ricavi

20% della popolazione mondiale conuma l'80% delle risorse

20% dei terremoti causa l'80% delle viitime

20% delle proteine è responsabile dell'80% dei processi metabolici
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
16
GENERAZIONE DI POWER LAW



supponiamo che voglia generare un milione di valori distribuiti secondo una
distribuzione power law con α =2.5
si può utilizzare un 'metodo' di trasformazione
schema dell'algoritmo:

generare un valore random r uniformemente distribuito nell'intervallo
[0,1) (utilizzare ad esempio Math.Random di JAVA)

un valore x distribuito secondo una power law di parametro α può essere
generato mediante la seguente formula:
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
17
PERCHE' UTILIZZARE UNA SCALA LOGARITMICA


Power Law: il dominio dei valori è molto 'esteso'
È interessante evidenziare quali sono i valori che hanno alta frequenza,
meno importante mettere in evidenza i molti valori di bassa frequenza

scale free networks: quale è la distribuzione dei nodi di alto grado?

disegnando una power law in scale lineare, i pochi valori con grado alto
vengono 'schiacciati' a causa della lunga coda
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
18
POWER LAW SU SCALA LOGARIMICA


Per valori piccoli di x, rilevazioni
aggregate, ad esempio decine di
migliaia di rilevazioni dello stesso
valore
Nella coda della power law un alto
numero di rilevazioni “individuali”

poche rilevazioni per ogni
valore di x

molte rilevazioni di valore
diverso

“accumulo” di dati provoca
rumore nella coda della power
law

molti slot vuoti corrispondenti
a valori con nessuna occorrenza
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
19
POWER LAW FITTING




curve fitting: partire dai dati
sperimentali, individuare la curva
che meglio approssima i dati
regressione lineare: individua una
retta che approssima la power law
in scala log-log: individuazione del
coefficente angolare α (parametro
della power law)
il 'rumore' nella coda della power
law può indurre errori nella
regressione
soluzione:
utilizzare
esponenzialmente
sempre
grandi
Dipartimento di Informatica
Università degli Studi di Pisa
bins
più
Laura Ricci
Power Law Scale Free Networks
20
POWER LAW FITTING: CUMULATIVE DISTRIBUTION

la CDF di una power law è ancora una power law di esponente α-1
Miglior fitting se si utilizza la CDF: nessun valore uguale a 0
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
21
POWER LAW: CURVE 'MISTE'
●
●
●
eliminare alcuni dati per ottenere una power law
selezionare xmin, il valore dopo cui inizia il comportamento 'power law'
nella power law delle citazioni il comportamento power law è evidente solo per
x>100
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
22
MAXIMAL LIKEWOOD FITTING

Date n misurazioni x1, ...xi, ...xn, calcolare α come
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
23
POWER LAW CON CUT-OFF ESPONENZIALE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
24
RITORNIAMO ALLA ANALISI DI RETI COMPLESSE...
Ci interessa disegnare la distribuzione dei gradi dei nodi
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
25
DISTRIBUZIONE DEI GRADI: NODE RANKING
• considerare i grafi del lucido precedente: 100 vertici
• si ordinano i vertici in base al loro gradi.
• si assegna un rank (posizione nell'ordinamento) ad ogni vertice
asse X : rank del vertice
asse Y : grado del vertice
• a destra ranking del grafo (a) a sinistra del grafo (b)
• grafo (a): esiste un solo vertice di grado 10, tre vertici di grado 9,....
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
26
SCALE FREE NETWORKS
Scale free Networks:
•
pochi vertici di grado alto, un altissimo numero vertici di grado basso
• può essere descritto con una power law
•
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
27
SCALE FREE NETWORKS



Watts e Strogatz modellano in modo appropriato il modello small world
Tuttavia questo modello non cattura bene altre proprietà importanti di alcune
reti reali: in molte reti reali esistono pochi nodi con grado alto e molti con
grado basso

struttura dei web links

topologia di Internet

reti P2P: Swarm Bittorrent

collaboration Networks
Scale Free Network: la distribuzione dei gradi dei nodi segue una legge power
law
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
28
SCALE FREENESS
●
Scale Freeness: una funzione F è scale free sse
f(bx) = C(b) f(x)
dove C(b) è una costante dipendente solo da b
●
Scale Freeness: la 'forma' della funzione f non cambia quando si considerano
valori di x che sono moltiplicati per un fattore b

Le power law soddisfano al precedente proprietà, infatti:
f(bx) = (bx)
Dipartimento di Informatica
Università degli Studi di Pisa
-α
=b
-α
x-α = b
-α
f(x)
Laura Ricci
Power Law Scale Free Networks
29
SCALE FREE NETWORKS
• A sinistra: distribuzione dei gradi per nodi con rank tra 10 e 100
• A destra: distribuzione dei gradi per nodi con rank tra 100 e 1000
La forma della funzione non cambia,
la forma è indipendente dall'intervallo considerato
• Questa proprietà caratteristica le funzioni scale free
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
30
SCALE FREE NETWORKS
• esempio di rete scale free: sistema aereo statunitense
• contiene alcuni nodi (hubs, rappresentati in rosso) e caratterizzati da un
alto numero di links
• la distribuzione dei nodi, rappresentata in scala log-log è rappresentata
da una retta
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
31
GRAFI RANDOM VS. SCALE FREE NETWORKS

Random Graphs (Erdos-Renyi): i link tra i nodi vengono stabiliti in modo
casuale, utilizzando una distribuzione binomiale

La maggior parte dei nodi possiedono lo stesso numero di links

Distribuzione gaussiana dei links dei nodi

Esempio di grafo random: sistema autostradale americano
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
32
SCALE FREE: IL WEB
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
33
SCALE: LA RETE DELLE PROTEINE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
34
SCALE FREE: I ROUTERS DI INTENET
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
35
SCALE FREE NETWORKS:TOPOLOGIA
Random Graph
Scale Free Network
• le reti rappresentate hanno lo stesso numero di nodi e di archi
• in rosso i nodi con il maggior numero di links, in verde i loro vicini


tutti i nodi hanno approssimamente
lo stesso numero di vicini
• molti nodi con pochi vicini, pochi nodi con
un alto numero di vicini
• il 60% dei nodi della rete possono essere
solo il 27% dei nodi della rete sono
raggiunti direttamente dai nodi rossi
raggiunti direttamente dai nodi rossi
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
36
WEB TOPOLOGY
Esperimento di Barabasi:

obiettivo: esaminare una parte del web

utilizza un crawler che memorizza in un database, tutte le URL individuate in
un documento e poi, ricorsivamente, segue queste URL per reperire i
documenti puntati

costruisce la rete corrispondente, in cui i nodi corrispondono alle pagine, gli
archi ai links (URLs) tra pagine.

ipotesi iniziale di Barabasi: il web può essere descritto mediante un grafo
random, perchè ogni persona:

sceglie in modo indipendente, secondo i propri interessi, i links da inserire
nella propria pagina

ha, in genere, interessi diversi

può scegliere tra un altissimo numero di pagine da linkare
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
37
SCALE FREE NETWORKS: IL WEB



l'esperimento contraddice l'ipotesi iniziale di Barabasi: più dell'80% delle
pagine ha meno di 4 links, ma lo 0.01 per cento delle pagine include più di 1000
links
esistono alcuni hubs (es: Yahoo o Google), che 'dominano' la rete
Pout(k) e Pin(k), probabilità che un documento abbia, k archi rispettivamente in
uscita ed in ingresso possono essere descritte come delle power law
P(k) ≅ k-γ
con valori tipici di γ compresi tra 2 e 3.
Esperimento dei fratelli Faloutsos:

Esamina la rete definita dai routers e dalle connessioni esistenti tra di loro

Anche in questo caso si rileva una distribuzione di tipo power law
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
38
COSTRUZIONE DI SCALE FREE NETWORKS

Le reti ER (Erdos Renyi) e WS (Watts e Strogatz) possono essere costruite a
partire da un insieme di vertici dato



Le reti scale free sono il risultato di due processi

un processo dinamico di crescita

un processo denominato preferential attachment
Procedura per la costruzione di una scale free networl proposta per la prima
volta da Barabasi ed Albert, nel 1999
La procedura combina la crescita dinamica di una rete con il fatto che i nuovi
nodi si collegano ai nodi già esistenti secondo certe preferenze

Watts e Strogatz: riavvolgimento di archi

Barabasi ed Albert: crescita + preferential attachment
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
39
COSTRUZIONE DI SCALE FREE NETWORKS

Si considera un grafo Go ER(no,p), con V0 = V(G0), n0 insieme di nodi iniziali,
piccolo

Ad ogni passo s > 0:
1. si aggiunge un nuovo vertice vs a Vs-1 ottenendo così: Vs ← Vs-1 ∪{vs}
2. si aggiungono m ≤ n0 archi. Ogni arco è incidente in vs ed in un vertice u∈Vs-1
con u scelto con probabilità
u non deve essere stato scelto precedentemente durante lo stesso passo
dell'algoritmo . La probabilità di scegliere u è proporzionale al suo grado.
3. Si ripetono i passi precedenti fino a che non sono stati aggiunti n vertici

BA(n,n0,m) è il grafo risultante applicando il processo precedente
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
40
BARABASI ALBERT: COSTRUZIONE
Caratteristiche delle scale free networks che favoriscono il formarsi di nodi
caratterizzati da alto grado

Crescita dinamica della rete




il numero di nodi cresce con il tempo. Ad esempio il web cresce
continuamente
i nodi 'più vecchi' hanno maggior opportunità di acquisire nuovi links
al contrario, nella costruzione di un Grafo Random si suppone che tutti i
nodi siano disponibili quando comincia la generazione casuale degli archi tra i
nodi della rete
Preferential Attachment


i links non vengono generati in modo random, alcuni nodi vengono scelti più di
frequente
Esempio: in internet nuovi hosts tendono a connettersi a routers che hanno
già molte connessioni, perchè dispongono di una maggior banda
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
41
BARABASI ALBERT
Growth + Preferential Attachment




Il tempo è discretizzato: la rete cresce nel tempo, ad ogni passo un nuovo
nodo entra nella rete
la generazione di un arco tra un nuovo nodo w ed uno vecchio v non avviene in
modo casuale, ma segue il seguente principio
più alto è il grado di v , più alta è la probabilità che w stabilisca un
collegamento con v
Con una metafora......the rich get richer
Preferential Attachment: La probabilità Π(v) che si stabilisca un collegamento
tra il vertice v ed il nuovo vertice w è definita come
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
42
GENERAZIONE DI UNA SCALE FREE NETWORK
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
43
GENERAZIONE DI SCALE FREE NETWORKS
Una semplice procedura per la generazione di scale free networks:



si definisce una rete iniziale, generata casualmente
si considerano gli archi del grafo che descrive la rete e, per ogni arco, si
registrano in un vettore i due vertici dell'arco
si inseriscono incrementalmente nuovi vertici nella rete, per ogni vertice
inserito

si selezionano i vertici a cui collegare il nuovo vertice scegliendo in modo
casuale i vertici dal vettore precedente

la probabilità di selezionare un vertice è proporzionale al numero di volte
in cui compare nel vettore, che corrisponde al grado del vertice
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
44
GENERAZIONE DI SCALE FREE NETWORKS
Registrare in un vettore i vertici di ogni arco, ordinandoli
La probabilità di selezionare un vertice è
proporzionale al numero di volte in cui esso
compare nel vettore, che corrisponde
a sua volta al grado del vertice
Ad ogni passo si selezionano m vertici
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
45
BARABASI ALBERT: PROPRIETA'


Distribuzione dei nodi del grafo. Per ogni grafo G ∈ BA(n,no,m), u ∈V(G)
Coefficente di clusterizzazione. Poiché il processo di costruzione di una rete
scale free è dinamico, si deve calcolare il coefficente di clusterizzazione

di un vertice vs

dopo t passi effettuati nella costruzione del grafo BA(t,n 0,m),

vs è stato aggiunto al grafo al passo s≤ t
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
46
BARABASI ALBERT: CLUSTERIZZAZIONE
si considera BA(100000, n0, 8) e si varia s
basso coefficente di clusterizzazione
Risulati sperimentali mostrano che il coefficente di clusterizzazione
cresece all'aumentare della dimensione della rete
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
47
BARABASI ALBERT: DIAMETRO

Lunghezza media dei cammini per BA(n,n 0,m)
γ costante di Eulero
Confronto tra grafi ER e BA
con lo stesso grado medio dei nodi
uguale a 10
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
48
BARABSI ALBERT: DIAMETRO

i grafi BA tendono a presentare una lunghezza media dei cammini minimi
tra due nodi inferiore a quella dei grafi ER

La lunghezza media dei cammini per un grafo random è già molto bassa

Questo è dovuto alla presenza di hubs con grado molto alto



un hub è vicino ad ogni vertice della rete

l'eccentricità di un hub è bassa

gli hub si comportano come connettori per i nodi di grado basso
Da un qualsiasi vertice si raggiunge un qualsiasi altro vertice della rete
mediante un cammino che contiene almeno un hub
Per questa ragione una rete scale free viene spesso definita una rete
Super Small World

diametro log(n)/log(log(n))
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
49
MODELLO DI BARABASI ALBERT: PROBLEMI


Non modella bene la clusterizzazione dei nodi

da questo punto di vista migliore Watts-Strogatz oppure Kleinberg
Le reti reali non sono completamente power-law

exponential cut-off: power law, quindi, improvvisamente, decrescita
esponenziale

ad esempio l'overlay Gnutella presenta un


exponential cut-off
in generale, la distribuzione presenta una 'lunga coda' rispetto ad una
distribuzione esponenziale, ma...la coda non è infinita
il modello di Barabasi Albert non modella bene
questo aspetto
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
50
POWER LAW: COME 'LEGGERE' I GRAFICI
Distribuzione delle visite degli utenti AOL su vari siti
Pochi siti con più di 2000 visitatori, la maggior parte dei siti con pochi visitatori
(70000 siti con un unico visitatore)
distribuzione “ad L”
un sito con pochi visitatori è messo in evidenza più di un sito con molti visitatori
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
51
SCALE FREE NETWORKS: PROPRIETA'
Robustezza rispetto a guasti casuali



le scale-free networks presentano buone caratteristiche di tolleranza ai
guasti
fino all'80% dei routers in Internet può essere soggetta a crash senza
pregiudicare la connettività della rete

esiste un cammino tra due host qualsiasi anche se l'80% dei routers si
rende indisponibile
Scale free networks sono caratterizzate da una notevole robustezza che
deriva dalla loro disomogeneità.
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
52
SCALE FREE NETWORKS: PROPRIETA'
Robustezza rispetto a guasti casuali:

se si rimuove in modo casuale (distribuzione uniforme) un nodo v, con alta
probabilità, tale vertice è di grado basso

la struttura della rete, con alta probabilità, non subisce modifiche
rilevanti

la lunghezza media dei cammini non subisce modifiche sostanziali
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
53
SCALE FREE NETWORKS: PROPRIETA'
Robustezza rispetto a guasti casuali:

esiste un cammino tra due host qualsiasi anche se l'80% dei routers si
rende indisponibile

Scale free networks sono caratterizzate da una notevole robustezza
che deriva dalla loro disomogeneità.
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
54
SCALE FREE NETWORKS: PROPRIETA'
Vulnerabilità verso gli attacchi

un attacco mirato può colpire i vertici di grado più alto

rimuove prima l'hub di dimensione maggiore, poi quello successivo e
così via...

la rimozione di un numero limitato di hubs può provocare il
frazionamento della rete in tante componenti di piccola dimensione

Lunghezza media dei cammini cresce repentinamente
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
55
ERRORI ED ATTACCHI
RANDOM VS. SCALE FREE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
56
SCALE FREE NETWORKS: VULNERABILITA'
• Scale free Network: si rimuovono vertici dagli hub
• Random Network: si rimuovono i vertici di grado maggiore da una rete
random
•Scale free network Random Removal: si rimuovono vertici dalla rete
scale free in modo casuale
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
57
RANDOM NETWORKS: FALLIMENTO ACCIDENTALE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
58
SCALE FREE NETWORKS: FALLIMENTO ACCIDENTALE
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
59
SCALE FREE NETWORKS: ATTACCO AGLI HUBS
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
60
SCALE FREE NETWORKS CLUSTERIZZATE

Si considera un grafo Go ER(no,p), con V0 = V(G0), n0 piccolo

Per ogni passo s>0
1. si aggiunge un nuovo vertice vs a Vs-1 ottenendo così: Vs ← Vs-1 ∪{vs}
2. si seleziona un vertice u da Vs-1 con una probabilità proporzionale al grado del
vertice δ(u). Si aggiunge l'arco 〈vs,u〉. I rimanenti m-1 archi si aggiungono come
segue
a) con probabilità q si seleziona un vertice w adiacente ad u. Se tale
vertice esiste si aggiunge l'arco 〈vs,w〉 e si esegue c) atrimenti si esegue b)
b) si seleziona un vertice u' da Vs-1 con una probabilità proporzionale al
grado del vertice δ(u') e si aggiunge l'arco vs, u e si pone u= u'
c) se sono stati aggiunti m archi si va a 3. altriemnti si torna ad a),
3. Se non sono stati ancora aggiunti n vertici si ritorna al passo 1..
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
61
SCALE FREE NETWORKS: CLUSTERIZZAZIONE

La procedura precedente costruisce eplicitamente, con probabilità uguale a p
un triangolo contenente




il nuovo vertice vs,
il vertice u a cui il nuovo vertice vs è stato connesso
un vicino w di u
Ad esempio se q=1 (probabilità di formare un triangolo =1) e supponendo che u
abbia k m vicini, w1,... wk, allors si crea una connessione tra vs ed ognuno di
questi vicini
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
62
SCALE FREE NETWORKS: CLUSTERIZZAZIONE



Un altro modello proposto recentemente prevede di definire una rete scale
free gerarchica
Ad ogni livello della gerarchia si creano molti triangoli
Un rappresentante per ogni livello della gerarchia connesso con un hub del
livello superiore
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
63
P2P SCALE FREE NETWORKS



analisi della rete Gnutella effettuata negli anni 2000-2001
sviluppato un crawler che si unisce alla rete Gnutella come servent ed usa i
messaggi di PING PONG per analizzare la struttura dell'overlay
all'inizio l'unica informazione disponibile riguarda una lista di servent ottenuti
dal bootstrap

successivamente informazioni su più di un milione di nodi

osservate diverse proprietà della rete:

numero di nodi nella componente connessa di dimensione massima
(giant component)

traffico generato dai diversi tipi di messaggio

struttura dell'overlay

lunghezza media dei cammini tra coppie di nodi

grado medio dei nodi
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
64
GNUTELLA: LUNGHEZZA MEDIA DEI CAMMINI
Dati collezionati da diversi crawls della rete
95% delle coppie di nodi raggiungibile in meno di 7 hops
Rete small world
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
65
GNUTELLA: GRADO MEDIO DEI NODI
dati riportati da un crawler nel novembre 2000
●
il grado dei nodi segue una distribuzione power law
●
molti nodi con pochi links, alcuni nodi con molti links (server-like)
●
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
66
GNUTELLA: GRADO MEDIO DEI NODI
●
●
●
dati riportati dal crawler nel marzo 2001
power law per nodi con un numero di links maggiore di 10
per nodi con meno di 10 links, la distribuzione è quasi costante
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
67
POWER LAW E RETI P2P
analisi di Bittorrent
●
analizzati 4 dei siti più noti di indicizzazione di .torrent
●
rank degli uploaders rispetto al numero di file di cui è stato fatto l'upload
●
comportamento power law:la maggior parte degli utenti uploada pochi
torrent, alcuni uploadano una quantità enorme di .torrent
●
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
68
POWER LAW E RETI P2P
●
●
numero di peer in un torrent
●
82% dei torrent non hanno più di 10 peer
●
22 torrent con più di 10000 peer
●
un torrent con più di 150000 peer (heroes, serie TV)
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
69
CONCLUSIONI



La struttura di una rete peer-to-peer system influenza

la lunghezza media dei cammini,

la possibilità di definire algoritmi di routing greedy, decentralizzati

la stabilità della rete verso guasti

la sensibiltà della rete verso gli attacchi
Caratteristiche importanti di una rete P2P :

la lunghezza media dei cammini

il coefficente di clusterizzazione

la distribuzione del grado dei nodi

...
E‘ importante stabilire le regole per la generazione degli archi della overlay
network in modo tale che la struttura della rete definita garantisca le
proprietà desiderate
Dipartimento di Informatica
Università degli Studi di Pisa
Laura Ricci
Power Law Scale Free Networks
70