Leis de Potncia, Lei de Zipfs
e distribuies de cauda pesada
Reviso do Artigo:
M. E. J. Newman, Power laws, Pareto distributions
and Zipf's
Zipf s law,
Contemporary Physics 46, 323-351 (2005)
Tpicos
Distribuies do tipo Power law: caractesticas
estatsticas
Fitting
Dados para os projetos do curso
Expectativa: que ns tenhamos uns 4 ou 5 bons papers
p
para
submissao em conferencias internacionais Qualis
A, como resultado do projeto.
Datasets
Web data from Panayiotis Tsaparas.
Tsaparas There are a number of interesting network
datasets available on the Web; they form a valuable resource for trying out algorithms
and models across a range of settings. Collaboration and citation networks: For the
2003 KDD Cup competition, Johannes Gehrke, Paul Ginsparg, and I provided a
dataset based on the arXiv pre-print database, which allows one to study the networks
of co-authorships and citations among a large community of physicists. Here is the
KDD Cup dataset and a paper describing the competition in more detail.
KDD C
Cup d
dataset.
t
t
P. Ginsparg, J. Gehrke, J. Kleinberg. Overview of the 2003 KDD Cup. SIGKDD
Explorations, 2004.
Internet topology: The network structure of the Internet can be studied at several
levels of resolution. Here is a dataset at the autonomous system (AS) level.
AS graphs.
Web subgraphs: There are many such datasets available for download
download. One set is
maintained by Panayiotis Tsaparas; the experiments that used this data are described
in his Ph.D. thesis, and in other papers linked from his home page
P. Tsaparas, Link Analysis Ranking, Ph.D. Thesis, Department of Computer
Science, University of Toronto, 2004.
Semantic networks: Free association datasets for words have been collected by
cognitive scientists; these are constructed by compiling the free responses of test
subjects when presented with cue words. (For example, a test subject presented with
the cue word `ice' might react with the word `cold,' `cream,' or `water.')
University of South Florida Free Association Norms.
O que uma distribuio de cauda pesada
(heavy tailed)?
(heavy-tailed)?
Inclinao para a direita
Distribuio normal (no heavy tailed)
Ex: altura de homens centrada em torno de 180cm
Zipfs
Zipf s ou power-law distribution (heavy tailed)
e.g. Tamanho das populaes das cidades: So Paulo tem 14
milhes, mas existem centenas de cidades no interior de menos de
1 mil habitantes
habitantes. (diferena de ordens de grandeza)
Razo alta entre o mximo e mnimo
Alturas humanas
Homen-gigante: 272cm, homen-ano: 57 cm razo: 4.8
Guinness Book of world records
Tamanho das cidades
So Paulo: pop.
pop 17 milhes,
milhes Serra Nova Dourada
Dourada, em Mato Grosso
com 562 hab. razo: 300.000
Distribuies com tamanho tpico ou escala de referncia
Distribuio Normal (tb chamada de Gaussiana)
da altura humana
Porcentag
gem
Valor medio proximo
A mais
Ao
i t
tpico
i
Distribuio prxima
De simtrica em torno
Da mdia
Altura de homens
Distribuio Power-law
E
Escala
l linear
li
Populao de cidades
Altamente inclinada (assimetria)
Linha reta no grfico log-log
E
Escala
l log-log
l l
Power laws esto em muitos lugares
(histogramas... Mais explicaes)
Moby Dick
bestsellers 1895-1965
scientific papers 1981-1997 AOL users visiting sites 97
AT&T customers on 1 day
California 1910-1992
Continuando com as power laws em outros fenmenos...
Moon
richest individuals 2003
Solar flares
US family names 1990
wars (1816-1980)
US cities 2003
Distribuio de uma Funo de Potncia (Power law)
Linha reta em um grfico log-log
p ( x) = cx
ln(
l ( p ( x)) = c ln(
l ( x)
Funo de probabilidade p(x), em funo do tamanho de
p ( x) = Cx
Constante
C
t t de
d
normalizao
(probabidades para
todos x devem
de em somar
1)
Expoente da lei de potncia
Estimativa de Expoentes
p
()
( )p
para Algumas
g
Distribuies
Influncia do Expoente
Qual o significado
do valor de na
distribuio dos
valores da populao?
Eixos Logaritmicos
Potncias de um nmero sero uniformemente
espaadas
10
20
30
100
200
20=1,
1 21=2,
2 22=4,
4 23=8,
8 24=16,
16 25=32,
32 26=64,.
64
Determinando o fitting em distribuies power laws
Mtodo mais comum, sem muita preciso:
Coloque em Bins os diferentes valores de x e crie um histograma de
f
frequncia
i
ln(# de vezes
x ocorreu)
ln(x) logaritmo
natural de x,
Pode-se usar qq
base,
log10(x) = ln(x)/ln(10)
ln(x)
X ppode representar
p
vrias qquantidades,, o indegree
g
de um nodo de uma rede,, a
densidade de sensores em vrias reas geogrficas, a frequncia de palavras num
texto, etc.
Exemplo: um dataset gerado articialmente
Use 1 milho de nmeros randomicos de uma
distribuio com = 2.5
25
Para gerar os nmeros pode
pode-se
se usar o mtodo da
funo inversa CDF F(x) u = F(x) x = F-1(u)
Gere nmeros aleatrios no intervalo 0r<1
Ento x = (1-r)1/(1) um nmero aleatrio real
distribuido segundo uma power
power law
law no intervalo 1 x
<
Histogramas do conjunto de 1 milho de nmeros aleatrios
Grficos em escala linear de bins de dados
Quantas vezes os nmeros 1 ou 3843 ou 99723 ocorrem?
Relao Power-law no aparente;
S faz sentido olhando nos menores bins
x 10
x 10
4.5
4.5
4
3.5
frequencyy
freque
ency
3.5
3
3
2.5
2
1.5
25
2.5
1
0.5
1.5
1000
2000
3000
4000
5000
6000
7000
8000
9000 10000
integer value
Intervalo integral
0.5
0
10
12
integer value
14
16
18
20
Os primeiros bins
Escala Log-log
Mesmo bins, mas plotados em uma escala log-log
6
10
Aqui tem-se dezenas de milhares de ocorrncias
quando x < 10
10
frequenccy
10
10
Ruidos (Noise) na cauda:
Aq i tem-se
Aqui
tem se 0,
0 1 or 2 ocorrncias
de valores de x qdo x> 500
10
10
10
0
10
10
10
integer value
10
10
Na verdade no se v todos
Valores 0 pois log(0) =
Log-log do binning dos dados
Fitting uma linha reta atravs da regresso dos MMQ, levar a
valores de muito baixos
6
10
fitted
t
true
10
10
fre
equency
10
10
10
10
0
10
10
10
integer value
10
10
O que d errado na aplicao direta de binning?
O ruido na cauda enviesa o resultado da regresso
= 2.5
10
0
data
Tem poucos
Bins aqui
10
= 1.6 fit
10
10
Tem muito mais bins aqui
q
10
10
10
0
10
10
10
10
10
Primeira Soluo: binning logaritmico
agrupe dados em bins exponencialmente mais largos:
1, 2, 4, 8, 16, 32,
= 2.5
25
normalize by pela largura do bin
6
10
data
= 2.41 fit
Pontos de
dados
espaados
igualmente
10
10
Menos ruido
na cauda da
distribuio
10
-2
10
-4
10
10
10
10
10
10
desvantagem: perda de informao no processo de suavizar os bins
Segunda soluo: binning cumulativo
Sem perda de informao
No so necessrios bins, h valor para cada valor de
ocorrncia de x
Mas, tem-se uma distribuio acumulada
i.e.
i Quantos
Q
t valores
l
de
d x so
no mnimo
i
iiguais
i a X
A probabilidade acumulada de uma distribuio power law
tambm power law, mas com expoente
cx
-1
c ( 1)
=
x
1
P ( X > x ) = k = x P ( k ) = k = x c k
Cx
( 1)
Fitting
g via regresso
g
para
p
probabilidade
p
acumulada
Expoente fitted (2.43) bem prximo do real (2.5)
6
10
data
-1 = 1.43 fit
frequenccy samplle > x
10
10
10
10
10
10
0
10
10
10
10
10
Onde deve-se comear o o fitting?
Algumas massas de dados somente exibem uma power law na
cauda;
Depois de fazer o binning or a distribuio acumulada, voce pode
fazer o fit para a cauda;
Ento necessrio seleionar um xmin o valor de x onde voce
considera que a power-law comea;
certamente xmin necessita ser maior que 0, pois x em x = 0
Exemplo
Distribuio das citaes a artigos
p
power law est evidente somente na cauda ((xmin > 100
citaes)
xmin
Estimativa de Expoentes
p
()
( )p
para Algumas
g
Distribuies
Maximum likelihood fitting (melhor)
Voce necessita estar certo que tem uma distribuio
power-law (o mtodo lhe dar simplesmente o expoente,
mas quo bom o fit)
n
xi
= 1 + n ln
l
i =1 xmin
xi so todos po
pontos
tos de dados, e voce
oce te
tem n po
pontos!
tos
Para o dataset exemplo = 2.503 bem prximo!
= 2.5
25
Muitas redes reais so power law
Exemplos de redes recentes
expoente
(in/out degree)
Redes de email
R d d
Redes
de contatos
t t sexuais
i
WWW
Internet
peer-to-peer
1.5/2.0
32
3.2
2.3/2.7
2.5
2.1
Cuidado!... nem tudo no mundo uma power law
Exemplo de um dataset real: nmero de visitantes a um
site
simple binning on a linear
scale
simple binning on a log-log scale
Ao tentar fazer o fit diretamente
Fit direto muito baixo: = 1.17
Binning os dados logaritimicamente pode ajudar
Selecionando bins exponencialmente mais largos
1, 2, 4, 8, 16, 32, .
Ou pode-se tentar o fit da distribuio acumulada
Mostra talvez 2 regimes separados de power-law que foi escondido
pelo binning exponencial
Cauda
C d d
da Power-law
P
l
pode
d estar
t prxima
i
d
de 2.4
24
Another common distribution: power-law
with an exponential
p
cutoff
p(x) ~ x-a e-k/
starts out as a power law
0
10
-5
ends up as an exponential
p(x)
10
-10
10
-15
10
10
10
10
10
but could also be a lognormal or double exponential
Zipf & Pareto:
q
qual
a relao
com p
power-laws?
Zipf
George Kingsley Zipf, um professor de lingstica de Harvard,
procurou determinar o tamanho' da 3a ou 8a ou 100a palavra
mais comum.
Tamanhosignifica a frequencia de uso da palavra em ingles em
um texto em ingles e no o comprimento da palavra
propriamente.
Zipf's law afirma que o tamanho (i
(i.e.,
e frequncia = y) da rr
sima maior ocorrncia do evento inversamente proporcional
a sua posio no rank:
y ~ r - , com
prximo de 1.
Rank distribution in the Web
Zipfs law & visitas ao site
Desvio da Zipfs law
pouquissimos websites com um grande nmero de visitante:
Expoentes e Mdias
Em geral, distribuies power law no tem valor mdio se < 2
(mas amostras tem!)
Isso
I
porque a mdia
di d
dada
d por (para
(
valores
l
iinteiros
t i
d
de k)
k (k ) = kk
kp
k = k min
k = k min
k = k min
1
k
Para uma amostra finita
Isso vai at o maior
valor observado.
1 1 1
1+ + + +K
2 3 4
A srie harmonica diverges
O mesmo vale para valores contnuos de k
Regra 80/20
A frao
W da riqueza
q
nas mos os P mais ricos da
populao dada por:
(
)/(
)
W = P(2)/(1)
Exemplo: riqueza nos EUA: = 2.1
20% mais ricos da populao detm 86% da riqueza
Processos Geradores de Power-laws
Muitos processos diferentes podem levar a power laws
No existe um nico mecanismo q
que explique
p q todos
processos.
Prximas aulas: preferential attachment em redes, como
Web e Internet.
Internet