Publicado el 30 de Octubre del 2019
705 visualizaciones desde el 30 de Octubre del 2019
11,5 MB
55 paginas
Creado hace 11a (17/03/2014)
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
ocordon@decsai.ugr.es
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
+
Comentarios de: Tema 5-3 - Redes Libres de Escala (0)
No hay comentarios