Post on 01-May-2015
Social Networks
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
• 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
heavy-tailed o a coda larga
€
( ) = A x ANx , do = 1/ve A
1i=1i
X
∑ ’ e X e ilvalo re massimo osservat o per x.
• A(x) segue una legge di potenza su una popolazione di N individui se:
Social Networks
Andamento
cresce
x
A(x)1
2 > 1
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:
€
( ) = A x ANx , do = 1/ve A
1i=1i
X
∑ ,
Dove X e’ di nuovo il valore max. osservato per x. Dunque:
€
( ) = A ax AN
( )ax = Aa
Nx , ∀ a co stante.
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:
€
( ) = A x ANx , do = 1/ve A
1i=1i
X
∑ ,
• N e’ il numero di individui
Social Networks
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?
€
( ) = Z i BXiα, do = 1/ve B
1jα=1j
N
∑ ,
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 α
α cresce
i
Z(i)
Andamento secondo legge di potenza ma la distribuzione studiata e’ diversa
Social Networks
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
€
( ) = R i BXiα, do = 1/ve B
1jα=1j
N
∑ ,
• Troviamo un limite inferiore a Rj, il numero complessivo di accessi ai j siti piu’ popolari
Social Networks
Esempio/2
• 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
€
Rj = BX1
iαi=1
j
∑ ≥ BX 1iα
di = 1
j+1
∫
= BX
1- α(( j +1)1−α −1) ≥
BX
1- αj1−α
Social Networks
Esempio/3
€
= 1/B1iα=1i
N
∑ .
1iα=1i
N
∑ ≤ 1 + 1(i-1 )α
di2
N+1
∫ = 1 + 1iα
di1
N
∫
= 1 + 1
1- α(N1- α -1) <
1
1- αN1- α .
B > 1- α
N1- α
Social Networks
Esempio/4
Dunque:
€
Rj ≥ BX
1- αj1−α >
j
N
⎛
⎝ ⎜
⎞
⎠ ⎟
1- α
X.
• 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
• La sommatoria corrisponde alla somma delle aree dei rettangoli
i
Z(i)
1 2 3 j j+1
Social Networks
Riferimenti • L. Adamic. Zipf, Power-laws, and Pareto - a
ranking tutorial – http://www.hpl.hp.com/research/idl/papers/
ranking/ranking.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