41
Leyes de potencia Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. •Típicamente, en la distribución de grados •Cuando hay modularidad jerárquica, en la distribución de clustering en función del grado •A veces en la distribución de betweenness. •También aparecen en tamaños de cascadas de fallas, tamaños de

Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Embed Size (px)

Citation preview

Page 1: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potenciaLeyes de potenciaLeyes de potenciaLeyes de potencia

Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas.

•Típicamente, en la distribución de grados

•Cuando hay modularidad jerárquica, en la distribución de clustering en función del grado

•A veces en la distribución de betweenness.

•También aparecen en tamaños de cascadas de fallas, tamaños de componentes conexas, distribución de pesos, etc etc etc.

Page 2: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potenciaLeyes de potenciaLeyes de potenciaLeyes de potencia

Ergo: es importante saber distinguirlas, estimar su exponente, y (por si sirve) conocer algunos mecanismos que las generan.

Lo básico: x e y están relacionadas por una ley de potencia, si se cumple

αxy

Una variable aleatoria [continua] sigue una ley de potencia si su densidad de probabilidad es

αCxf(x)

Page 3: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potenciaLeyes de potenciaLeyes de potenciaLeyes de potencia

αCxf(x)

y por lo tanto tenemos la recta en log-log:

xa C f(x) logloglog

La función acumulada será

1)(αx1α

CxXP

y la invarianza de escala:

)()()() xfxfλCxλλx Cxf( aaaa

Page 4: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potenciaLeyes de potenciaLeyes de potenciaLeyes de potencia

Problema: la densidad explota cuando x0.

Solución: por lo general se asume un valor mínimo xmin. En tal caso,

1aminx1αC

y la función de densidad pasa a ser

α

minmin xx

x1)-(α

f(x)

Page 5: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potenciaLeyes de potenciaLeyes de potenciaLeyes de potencia

Cuando la variable es discreta:

•La densidad es nuevamente proporcional a x-a.

•La distribución acumulada ahora es simplemente la suma.

•El xmin suele ser 1 (ojo: no puede ser 0).

•Con frecuencia sirve, pero no es riguroso: tratar la variable como si fuera una muestra de una v.a. continua (y usar la fórmula para la acumulada, etc.)

Page 6: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”

Ley de Zipf

•Georges Zipf, lingüista, intentó determinar el “tamaño” (en realidad, frecuencia) de la 3ª, 8ª o 100ª palabra más común del inglés.

•Lo que encontró (su “ley”) indica que la frecuencia es inversamente proporcional al ranking: rf(r)con el exponente muy cerca de 1.

Luego se confirmó en otros idiomas.

Page 7: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”

Ley de Pareto

•Vilfredo Pareto, economista, estudió la distribución del ingreso.

•La ley de Pareto se expresa en términos de la distribución acumulada (probabilidad de que alguien gane x o más):

kx x)P(Xen la notación de leyes de potencia, ese k es k = a-1, donde a es el exponente de la ldp.

Page 8: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”

Relación entre ambas:

•Si despreciamos los “empates”, decir “el r-ésimo tiene x” es equivalente a decir “r tienen x o más”.

•Ergo, Zipf y Pareto describen la misma cosa, pero con los ejes invertidos.

Zipf hubiese dicho: “el ingreso de la r-ésima persona con mayor ingreso es x~r-”

mientras que Pareto dice “la fracción de gente que gana x o más es r~x-1/ ”

Page 9: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”

Para distribuciones de Pareto suele mencionarse el “principio de Pareto” o “regla de 80 y 20”.

•Pareto observó que el 80% de la tierra en Italia pertenecía al 20% de la gente.

•No hay nada mágico en el nº 80; es simplemente una regla mnemotécnica. Se aplica en negocios: el 80% de las ventas viene del 20% de los clientes.

•A nivel mundial, hoy, se cumple en la distribución de ingreso.

Page 10: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”Leyes de potencia “célebres”

•Microsoft: eliminando el 20% de bugs más frecuentes, se evita el 80% de las BSD.

•El 80% de los crímenes los comete el 20% de los criminales.

•Etc, etc.

Page 11: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de Leyes de potencia por potencia por todos ladostodos lados

Leyes de Leyes de potencia por potencia por todos ladostodos lados

Page 12: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Ejemplos de algunos mecanismos que producen LDP:

Si Y tiene distribución exponencial,

fY(y)~ eay

y otra variable X depende exponencialmente de Y,

X ~ ebY

entonces X sigue una LDP,

fX(x) ~ x-(1+a/b)

Page 13: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Monos tipeando al azar (Miller, 1957).

•Supongamos que aprietan el espacio con probabilidad q.

•El resto de las teclas son equiprobables, (1-q)/m.

La frecuencia de las palabras generadas sigue una LDP.

No es aplicable al lenguaje, pero sirve como modelo nulo.

Page 14: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Minimización de esfuerzo.

•El costo de enviar la palabra j-ésima en ranking de frecuencia es (bajo una codificación razonable) jlog~C mj

•El costo medio de la comunicación será

n

1j jjCpC

•El contenido promedio de información en un mensaje es

n

1j j2j plogpH

•Al minimizar el costo por unidad de información, C/H, -α

j j~p

Page 15: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Fenómenos críticos:

•En las cercanías de un punto crítico (donde se produce un cambio de fase), las cantidades por lo general escalan como leyes de potencia.

Probabilidad p de que una celda este ocupada. ¿Cuál es el tamaño medio de los clusters?

Page 16: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

•Si p < pc, el tamaño medio es independiente del tamaño de la grilla.•Si p > pc, el tamaño medio diverge (es del tamaño de la grilla).•Para p=pc, hay LDP de tamaños de clusters.

pc = 0.5927462…

Page 17: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Criticalidad auto-organizada:

•Supongamos que en cada instante t=0,1,..., puede aparecer un árbol en cada celda con probabilidad p.•Supongamos además que con probabilidad q, aparecen incendios (y queman todo el cluster).

El sistema se estabiliza en un punto crítico, así que la distribución de tamaño de los incendios sigue una LDP.

Page 18: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Otro mecanismo, que es el que ya vimos (via Barabasi-Albert): rich get richer.

Sugerido por primera vez por Yule para la distribución de la cantidad de especies, dentro de los géneros biológicos.

•Supone que un genero adquiere especies nuevas con probabilidad proporcional a su tamaño.•Cada m especies nuevas, la m+1-ésima crea un nuevo género.•El resultado es que el tamaño de los géneros sigue

m12k k~p

Page 19: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

Price, en 1965, sugiere algo equivalente para citaciones de papers:

•Cada paper nuevo cita (en promedio) m papers.

•La probabilidad de citar un paper es proporcional a la cantidad de citas que tiene, k.

•En realidad es proporcional a k+1: se agrega una “cita por defecto” para que los recién llegados puedan competir.

•El resultado también es m12k k~p

Page 20: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Leyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos ladosLeyes de potencia por todos lados

El modelo de Barabasi-Albert aplica básicamente la misma idea, al hacer preferential attachment (“enlace preferencial”).

Aprovechemos de ver un modelo que también genera un grafo tipo BA: modelo LCD (linearized chord diagram) de Bollobas-Riordan.

Consideremos 2n nodos puestos en orden lineal:

Page 21: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Modelo LCDModelo LCDModelo LCDModelo LCD

Generamos un matching al azar entre los nodos

Page 22: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Modelo LCDModelo LCDModelo LCDModelo LCD

De izquierda a derecha, identificamos todos los extremos izquierdos hasta que topemos el primer extremo derecho; ahí cortamos. Luego aplicamos lo mismo sobre lo que sigue.

Page 23: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Modelo LCDModelo LCDModelo LCDModelo LCD

•El resultado son grafos equivalentes a los del modelo de enlace prefencial.

•Agregar un nuevo nodo: sería agregar un nuevo match.

Page 24: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

¿Cómo estimar el exponente de una LDP?

Caso ideal:

Page 25: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

100

101

102

103

104

100

101

102

103

104

105

106

integer value

fre

qu

en

cy

EstimaciónEstimaciónEstimaciónEstimación

Hay muchas observaciones con valores pequeños… pero no tantas como podría haber

Ruido en la cola

En un sistema finito, tenemos muy pocas observaciones con valores de verdad grandes

Caso real:

Page 26: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

100

101

102

103

104

100

101

102

103

104

105

106

integer value

fre

qu

en

cy

fitted true

Page 27: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Primera idea: juntar los valores en intervalos (binning).

Page 28: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Refinamiento del binning: usar bins de tamaño exponencial. Los intervalos serán de tamaños (p.ej.) 2, 4, 8, 16, 32...

•Se obtienen puntos equiespaciados en el log-log.

100

101

102

103

104

10-4

10-2

100

102

104

106

data = 2.41 fit

Menos ruido en la cola

•Problema: se pierde información.

Page 29: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Segundo truco: pasar a la acumulada, usando el hecho de que 1)(αxxXP

100

101

102

103

104

100

101

102

103

104

105

106

x

fre

qu

en

cy s

am

ple

> x

data-1 = 1.43 fit

Page 30: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Cantidad de visitantes a sitios de AOL, 1997

Datos en bruto:

Page 31: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Binning lineal, escala log log

Recta de exponente 1.17. Claramente mala.

Page 32: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Binning exponencial

Page 33: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Pasando a acumulada

•Puede que sean dos LDP de exponente distinto, según rango.•La cola cae con exponente más bien cercano a 2.4.

Page 34: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Pero además: ¿desde dónde rige la ley de potencia?

xmin

Page 35: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Moby Dick scientific papers 1981-1997 AOL users visiting sites ‘97

bestsellers 1895-1965 AT&T customers on 1 day California 1910-1992

Page 36: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

Moon Solar flares wars (1816-1980)

richest individuals 2003 US family names 1990 US cities 2003

Page 37: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

¿Cómo calcular el exponente?

Naïve: mínimos cuadrados (después de aplicar log/log).

NO ES bueno.

Mucho mejor: máxima verosimilitud1

n

1i min

i

xx

lnn1α

Page 38: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

¿Cómo elegir el punto de corte (el xmin)?

Para efectos prácticos, suele ser “a ojo”, o bien probando con varios y viendo cuál da el mejor ajuste.

¿El mejor ajuste?

Es necesario comparar qué tan bueno es el ajuste con distintos xmin.La forma de hacerlo es también la que se necesita para comparar la LDP con otras posibles distribuciones (exponencial, lognormal, etc.)

Page 39: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Para evaluar si una muestra viene o no de una cierta distribución, se usa Kolmogorov-Smirnov.

•Se compara la función de distribución de la supuesta ley, con la empírica.

•Se evalúa la máxima diferencia (en módulo).

))()((max

))()((max

xFxFD

xFxFD

XYx

YXx

donde FX es la del modelo, FY es la de los datos.Se calcula D = max(D+,D-).

Page 40: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Kolmogorov-Smirnov

Page 41: Leyes de potencia Hemos visto que las leyes de potencia (power laws) suelen aparecer en redes complejas. Típicamente, en la distribución de grados Cuando

EstimaciónEstimaciónEstimaciónEstimación

Si de verdad uno quiere ser serio para estimar una LDP, leer

“Power-law distributions in empirical data”A. Clauset, C. Shalizi y M. Newmanhttp://arxiv.org/abs/0706.1062

Preview en http://cscs.umich.edu/~crshalizi/weblog/491.html

“So You Think You Have a Power Law — Well Isn't That Special?”

y usar el software disponible enhttp://www.santafe.edu/~aaronc/powerlaws/