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