Leggi di potenza e di Zipf
Social Networks
Distribuzione di parametri
• Esempio: supponendo di avere a
disposizione i dati sul numero di accessi
a un certo insieme S di n siti Web,
studiare la distribuzione di A(x) rispetto a
x, dove:
– x = # accessi nell’ultimo mese
– A(x) = # di siti ai quali sono stati fatti x
accessi nell’ultimo mese
Social Networks
Piu’ formalmente…
• Interessa il seguente problema: data una
popolazione S di n individui e un
parametro P (reale o intero) di interesse,
determinare l’andamento di A(x), dove
– x = valore del parametro
– A(x) = # individui per cui P = x
Social Networks
Esempio: distribuzione degli
accessi a siti Web
• x = # accessi, A(x) = # siti a cui sono stati fatti x
accessi
• A(x) = (1/x), dove  > 2
Social Networks
Esempio: distribuzione del
numero di link entranti
• x = # di link entranti, A(x) = # pagine Web con x link
entranti
• A(x) = (1/x), dove  ≈ 2.1
• Scala logaritmica
Social Networks
Legge di potenza
• A(x) segue una legge di potenza su una
popolazione di N individui se:
A(x) = A
N
, do ve A = 1/

x
X
1
 i
i=1
e X e’ il va lo re m assim o o sservat o per x .
• Per semplicita’ xmin = 1
• Si osservi che x  {1, … , X} e che ∑xA(x) = N perche’
A(x) e’ una distribuzione
• La legge di potenza e’ anche detta distribuzione heavytailed o a coda larga
Social Networks
Andamento
A(x)
1
 cresce
2 > 1
x
Social Networks
Invarianza di scala
• Una funzione f(x) esibisce invarianza di scala se
f(ax) = bf(x), dove a e b sono costanti
• Per una distribuzione A(x), invarianza di scala
significa che, per ogni x e per ogni costante a, #
individui che esibiscono il valore ax del
parametro e’ ~ # individui che esibiscono il
valore x del parametro
• Proprieta’ fondamentale: le leggi di potenza
sono le uniche soluzioni di f(ax) = bf(x)
Social Networks
Esempio/dimensioni dei file
• Si osserva che il numero di file di
dimensione 2x e’ all’incirca 1/4 del numero
di file di dimensione x
– Ad esempio, # file di dimensione 2 KB ≈ (1/4)
# file di dimensione 1 KB
• La distribuzione A(x) soddisfa dunque la
seguente proprieta’:
– A(2x) = (1/4)A(x) e dunque e’ una legge di
potenza
Social Networks
Invarianza di scala/2
• A(x) = # siti cui sono stati fatti x accessi
• A(x) segue una distribuzione del tipo:
N
A(x) = A  , do ve A = 1/
x
X
1
 i ,
i=1
Dove X e’ di nuovo il valore max. osservato per x. Dunque:
N
A N
A(ax) = A
=   ,  a c o stante .

(ax)
a x
Social Networks
Invarianza di scala/3
• A/x e’ la frazione di siti ai quali sono stati
fatti x accessi durante il periodo di
osservazione
Social Networks
Esempio
• Supponiamo di sapere che
A(2x) = (1/4)A(x). Determinare

Social Networks
Esempio/2
• Sappiamo che A(x) deve seguire una
legge di potenza, quindi A(x) sara’ del tipo:
N
A(x) = A  , do ve A = 1/
x
• N e’ il numero di individui
Social Networks
X
1
 i ,
i=1
Esempio/3
• Questo significa che A(x)/A(2x) = 2 = 1/4
• Cio’ implica  = 2
Social Networks

Rappresentazione in scala
logaritmica
• Le leggi di potenza diventano lineari se
rappresentate in scala logaritmica:
ln(A(x)) = lnA + lnN
- lnx
• Le leggi di potenza sono le uniche a
godere di tale proprieta’
– Nota: si osservi che A ed N sono costanti per
una particolare popolazione osservata
Social Networks
Esempio: distribuzione degli
accessi a siti Web
• Si osservi che il parametro  e’ la tangente (< 0)
della retta di interpolazione
Social Networks

Legge di Zipf
• Si ha quando studiamo il problema
seguente: qual e’ il # accessi all’i-esimo
sito piu’ popolare?
X
Z(i) = B  , do ve B = 1/
i
N
1
 j ,
j=1
dove N e’ il numero di siti considerati e 0 <  <= 1
• Si osservi che ∑iZ(i) = X, il numero complessivo di
accessi a tutti i siti
Social Networks
Andamento al variare di 
Z(i)
 cresce
Andamento secondo legge di potenza ma la
distribuzione studiata e’ diversa
Social Networks
i
Esempio: distribuzione degli
accessi a siti Web
• L’i-esimo elemento dell’asse delle ascisse rappresenta
l’i-esimo sito piu’ popolare
• Siti con uguale numero di accessi ordinati a piacere
Social Networks
Relazione tra leggi di potenza
e di Zipf
• Proprieta’: legge di potenza implica legge di Zipf
e viceversa
Social Networks
Relazione tra leggi di potenza e
di Zipf
• Si puo’ dimostrare che se A(x) segue una
legge di potenza con parametro  allora
Z(i) segue una legge di Zipf con parametro
 = 1/(-1)
• La legge di Zipf rappresentata in
coordinate logaritmiche corrisponde a una
retta con pendenza -
Social Networks

Esempio/1
• Si supponga di considerare N siti Web e si
supponga che l’i-esimo sito piu’ popolare
abbia ricevuto R(i) richieste, dove
X
R(i) = B  , do ve B = 1/
i
N
1
 j ,
j=1
• Troviamo un limite inferiore a Rj, il numero complessivo
di accessi ai j siti piu’ popolari
Social Networks
Esempio/2
j
j+1
1
R j = BX    BX 1
i=1 i
1
i
di =
BX
BX 1
1

(( j  1) 1) 
j
1- 
1- 
• Si approssima la somma con un integrale
• x1--1 ≥ (x-1)1- per x ≥ 1
– Vero per x = 1
– Derivata di f(x) = x1--1 - (x-1)1- e’ > 0 per x ≥ 1
Social Networks
Esempio/3
N
1
B = 1/   .
i=1 i
N
1
 i  1 +
i=1
=1+

N+1
2
1
(i-1 )
di = 1 +

N
1

1 i
1
1 1- 
1- 
(N -1) <
N .
1- 
1- 
1- 
B>
N1- 
Social Networks
di
Esempio/4
Dunque:
1- 
 j 
BX 1
Rj 
j
>   X.
N 
1- 
• Ad esempio, per  = 0.9, Rj > 0.8X non
appena j/N ≥ (0.8)10 ≈ 0.11
 • Cio’ significa che l’ 11% dei siti piu’
popolari riceve piu’ dell’ 80% degli accessi
Social Networks
Somme e integrali
Z(i)
1
2
j
3
j+1 i
• La sommatoria corrisponde alla somma delle aree dei
rettangoli
Social Networks
Riferimenti
• L. Adamic. Zipf, Power-laws, and Pareto - a
ranking tutorial
– http://www.hpl.hp.com/research/idl/papers/ranking/ran
king.html
• M. E. Newman. Power laws, Pareto distribution
and Zipf’s law
– http://arxiv.org/abs/cond-mat/0412004
• Anche: M. Mitzenmacher. A Brief History of
Generative Models for Power Law and
Lognormal Distributions
– http://www.eecs.harvard.edu/~michaelm/NEWWORK/
postscripts/history-revised.pdf
Social Networks