PDF de programación - Tema 5-3 - Redes Libres de Escala

Redes y Sistemas Complejos

Cuarto Curso del Grado en Ingeniería Informática

Tema 5: Modelos de Redes
5.3. Redes Libres de Escala

Oscar Cordón García

Dpto. Ciencias de la Computación e Inteligencia Artificial

[email protected]

VALIDEZ DE LOS MODELOS EXISTENTES PARA REDES REALES

<

d

>

aleatoria

=

log

N

log

k

Distancias

medias

Redes
regulares

Redes ER
(aleatorias)

Mundos
pequeños

d

≈

/1

DN

d aleatoria

≈

d aleatoria

≈

log

N

log

k

log

N

log

k

Distribución de los grados

P(k) ~ k-γ

Clustering

C ~

const

C ~

const

C aleatoria

=

p

=

k

N

C ~

const

P(k)=δ(k-kd)

P(k) = e−< k> < k >k
k!

Exponencial

LA RED COMPLEJA DE LA WORLD WIDE WEB (1)

Nodos: documentos WWW
Enlaces: hiperenlaces URL

En torno a 1 billón (N≈1012) de documentos

ROBOT: recopila todas las URLs encontradas en una
página web y las sigue recursivamente

En 1998 se pensaba que era una red aleatoria:

P(k) ~ k-γ

O
b
s
e
r
v
a
d
a

Mapa de la web (dominio nd.edu) con 325,725 páginas (1998)

Nodos rojos → grado≥50; nodos morados → grado≥500

H. Jeong, R. Albert, A-L Barabasi, Nature, 401:130-131 (1999)

DIFERENCIA ENTRE UNA LEY DE LA POTENCIA Y UNA EXPONENCIAL (1)

La distribución de los grados observada en la WWW sigue la llamada Ley de la Potencia

1

0.6

0.2

)x(f

=

cx

−

50.

)x(f

=

−
1cx

)x(f

−=
xc

20

40

60

80

100

Por encima de un cierto umbral x, la ley de la potencia es siempre mayor que la exponencial

DIFERENCIA ENTRE UNA LEY DE LA POTENCIA Y UNA EXPONENCIAL (2)

La diferencia es muy clara si se representa en una escala logarítmica para el eje Y: para valores
grandes de x existen diferencias de varios órdenes de magnitud entre las dos funciones

0
10

-1

10

-2

10

-3

10

-4

10

0
10

1
10

2
10

3
10

)x(f

=

cx

−

50 .

)x(f

=

cx

−

50 .

)x(f

=

cx

−

1

)x(f

−=
xc

loglog

)x(f

=

cx

−

1

semilog

)x(f

−=
xc

→ Log pk depende linealmente de log k

La pendiente de la recta viene dada por el exponente de grado γ

¿QUÉ SIGNIFICA REALMENTE ESTA DIFERENCIA?

Representación Visual (1)

l

a

i

c
n
e
n
o
p
x
E

a

i

c
n
e
t
o
P
a



Red de nacional de autovías

P(k) ~ k-γ

l

e
d

Red de tráfico aéreo



d
e
R



y
e
L
n
o
c
d
e
R



¿QUÉ SIGNIFICA REALMENTE ESTA DIFERENCIA?

Representación Visual (2)

LA RED COMPLEJA DE LA WORLD WIDE WEB NO ES ALEATORIA

DEFINICIÓN DE REDES LIBRES DE ESCALA

Las redes cuya distribución de grados sigue la ley de la potencia se
denominan “redes libres de escala” (scale-free)

Estas redes presentan una distribución de grados de larga estela o larga cola (heavy-
tailed, long-tailed or power-law-tailed distributions)

http://es.wikipedia.org/wiki/Larga_cola

La larga estela, en color amarillo, puede
comprender un área incluso mayor que
la de la primera parte de la función

• Distribuciones de Pareto: regla 80/20

• Modelos económicos: Amazon.com

Si la red es dirigida, se puede analizar por separado la “propiedad de libertad de escala” sobre
las distribuciones de grados de entrada y salida

Se pueden emplear dos formulaciones matemáticas distintas para estudiar las propiedades de
estas redes aunque la propiedad en sí es independiente del formalismo considerado

FORMULACIÓN

Formalismo discreto (1)

Considera que los grados son valores enteros positivos. Captura la
probabilidad pk >0 de que un nodo tenga exactamente k enlaces:

p k

= Ck

γ−

C es una constante que se calcula a partir de la condición de normalidad:

∞

=∑

kp

=k

1

1

C

∞

∑

k

=

1

−

γ

k

=

1

C

=

1

−

k

∞

∑

k

=

1

=

γζγ

(

1

)

p k

=

γ−

k
(γζ

)

para k>0

(se asume que no hay nodos desconectados en la
red, p0 se calcula aparte)

función Zeta de Riemann

FORMULACIÓN

Formalismo discreto (2)

En algunas aplicaciones, sólo se tiene en cuenta la cola de la distribución de grados:

p k

=

Ck

−

γ

k

=

[ min ∞
k

,

)

∞

=∑

kp

k

= k

min

p k

=

1

C

=

∞

1
∑

k

=

γζγ

(

−

1

,

k

min

)

k

=

k

min

función Zeta generalizada o incompleta

γ−

mink

)

k
γζ

(

,

FORMULACIÓN

Formalismo continuo

En cálculos analíticos conviene asumir que los grados pueden tomar cualquier valor real
positivo. En ese caso, la distribución de grados de la ley de la potencia toma la forma:

kP

(

)

=

Ck

−

γ


;

k

=

[

k

min ∞

,

)

∞

∫

kP

(

)
dk

=

1

C

=

K

min

=

γ
(

−

)1

k

−
γ
1
min

1

∞

∫

k

−

γ

dk

K

min

kP

(

)

=

γ
(

−

)1

k

−

γ

−
γ
1
min

k

kmin es el menor valor de grado para el que se cumple que:

p k

=

γ−

k
(γζ

)

LOS HUBS EN LAS REDES LIBRES DE ESCALA (1)

Las diferencias principales entre una red aleatoria
y otra libre de escala se encuentran en la cola de
la distribución:

• Para valores pequeños de k, la ley de la potencia está

por encima de la de Poisson: la red libre de escala
tiene un número alto de nodos con grado pequeño

• Para k‘s cercanos a <k>, la distribución de Poisson

está por encima de la ley de la potencia: en una red
aleatoria hay muchos nodos con grado k ≈ <k>

• Para valores altos de k, la ley de la potencia vuelve a

estar por encima de la de Poisson: la posibilidad de
encontrar un nodo de grado alto, un hub, es varios
órdenes de magnitud mayor en una red libre de escala

Ejemplo (WWW): paleatoria(100)=10-30 ; plibre-escala(100)= 10-4

LOS HUBS EN LAS REDES LIBRES DE ESCALA (2)

¿Cómo afecta el tamaño de la red N al tamaño de sus hubs?

Para cualquier distribución de grados pk es posible calcular el grado máximo esperado kmax:

• Red aleatoria, distribución exponencial pk=Ce-λk :

Depende de ln N, crece suavemente y hay poca diferencia entre kmin y kmax. No hay hubs

• Red aleatoria, distribución de Poisson: crece aún más suavemente.

• Red libre de escala, distribución de larga cola:

Depende de N. Cuanto mayor es el tamaño de la red, mayor es el grado del hub más
grande. Hay diferencias significativas entre kmin y kmax

Ejemplo (muestra WWW N=3·105): kmax(red aleatoria) ≈ 13 ; kmax(red libre de escala) ≈ 85,000

LOS HUBS EN LAS REDES LIBRES DE ESCALA (3)

ORIGEN DEL TÉRMINO “LIBRE DE ESCALA” (1)

El término “libre de escala” está relacionado con los momentos de la distribución de
probabilidad de grados:

• n=1: el primer momento es el grado medio <k>

• n=2: el segundo momento <k2> es la varianza σ2 = <k2> - <k>2 que mide la dipersión

de los grados. Su raíz cuadrada σ es la desviación típica

• n=3: el tercer momento <k3> determina la asimetría, indicando cómo de simétrica es

pk alrededor de la media (en distribuciones simétricas, vale 0)

ORIGEN DEL TÉRMINO “LIBRE DE ESCALA” (2)

En una red libre de escala, el n-ésimo momento de la distribución de grados es:

Como kmax crece con el tamaño de la red, hay que analizar su comportamiento en el
límite kmax → ∞ para determinar las propiedades de las redes muy grandes:

n

<

k

>=

γ
(

−

)1

k

γ
−
1
min

∞

∫

k

min

k

n

−

λ

dk

=

γ
(
−

n

−
γ

(

)1
+

)1

k

γ
−
1
min

[
k

n

γ

]∞+−

1

k

min

• Si n-γ+1 ≤ 0, el n-ésimo momento está acotado. Todos los momentos en los que n

≤ γγγγ+1 son finitos

• Si n-γ+1 ≥ 0, el n-ésimo momento tiende a infinito según la red crece. Todos los

momentos en los que n ≥ γγγγ+1 divergen

ORIGEN DEL TÉRMINO “LIBRE DE ESCALA” (3)

La mayoría de los exponentes de grado γ están entre 2 y 3: <k> es finito pero <k2> y el
resto de momentos tienden a infinito. Eso implica que:

2

kσ

=

(

k

−

k

2/12
)

∞→

k

=

k

σ±
k

WWW:

<k> = 7 ±∞

Internet:

<k> = 3.5 ±∞

Redes metabólicas:

<k> = 7.4 ±∞

Llamadas telefónicas: <k> = 3.16 ±∞

¡Los valores medios no tienen sentido al ser las fluctuaciones demasiado grandes!
La escala interna no es coherente. La red es “libre de escala”

ORIGEN DEL TÉRMINO “LIBRE DE ESCALA” (4)

Esta divergencia de las redes libres de escala es el origen de muchas de las propiedades
más interesantes de estas redes, como su robustez a fallos/ataques aleatorios y su
comportamiento anómalo en la propagación de virus

PROPIEDADES DE LAS REDES LIBRES DE ESCALA

Robustez

PROPIEDADES DE LAS REDES LIBRES DE ESCALA

Implicaciones

¿Cómo de general es el descubrimiento de una

distribución de grados que sigue la ley de la potencia?

RED COMPLEJA DEL BACKBONE DE INTERNET

Nodos:
Enlaces:

ordenadores, routers
conexiones físicas

Faloutsos, Faloutsos y Faloutsos, Comput. Commun. Rev. 29:251-262 (1999)

REDES CIENTÍFICAS

Science Citation Index

Nodos: artículos científicos
Enlaces: citas

1736 PRL papers (1988)

S. Redner, Eur. Phys. J. B 4:131 (1998)

25

578...

H.E. Stanley,...

P(k) ~k-γγγγ
(γγγγ = 3)

REDES CIENTÍFICAS

Coautoría científica

Nodos: científicos (autores)
Enlaces: publicaciones conjuntas

M: Math
NS: neuroscience

M.E.J. Newman, PNAS 98(2):404-409 (2001)
A.-L- Barabasi et al. Physicia A 311:590-614 (2002)

EL NÚMERO ERDOS

(Juego de Bacon para cerebritos ☺☺☺☺ )

Número de enlaces requeridos para conectar los
investigadores a Erdős via la co-autoría de artículos
científicos

Erdős escribió más de 1500 artículos con 507 co-
autores

La web de Jerry Grossman (Oakland Univ.) permite
a los matemáticos calcular su número Erdos:

http://www.oakland.edu/enp/

Conectando las longitudes de los caminos entre los
matemáticos únicamente :

– La longitud media es 4.65

– La longitud máxima es 13

Paul Erdős (1913-1996)

Erdos tiene un mayor valor de
centralidad en su red que
Kevin Bacon en la suya

COMUNIDADES VIRTUALES (1)

Nodos:
Enlaces: contactos por e-mail

usuarios

Comunidad on-line Pussokram.com
512 días, N=25,000 usuarios

Ficheros de log de la Universidad de Kiel
112 días, N=59,912 nodos

Ebel, Mielsch y Bornholdtz, Physical Reviews E
66:035103(R), (2002)

Holme, Edling y Liljeros, Social Networks
26(2):155-174 (2004)

COMUNIDADES VIRTUALES (2)

Nodos:
Enlaces: relaciones en redes sociales

usuarios

Todas las distribuciones muestra un comportamiento
de cola amplia: hay desviaciones de varios órdenes
de magnitud en los grados

Mislove et al., Measurement