PDF de programación - Tema 5-2 - Mundos Pequeños

Redes y Sistemas Complejos

Cuarto Curso del Grado en Ingeniería Informática

Tema 5: Modelos de Redes

5.2. Mundos Pequeños

Oscar Cordón García

Dpto. Ciencias de la Computación e Inteligencia Artificial

[email protected]

EXPERIMENTO DE MILGRAM:

Las primeras cartas en cadena… Orígenes: Omaha, Nebraska y
Wichita, Kansas, EEUU. Destino: Boston y Sharon, Massachusetts, EEUU

Se enviaron 296 cartas. La primera llegó en pocos días, pasando sólo
por 2 enlaces. Al final llegaron 64 con un máximo de 12 intermediarios

SEIS GRADOS DE
SEPARACIÓN:
La media de
intermediarios
fue de entre

5.5 y 6

Travers y Milgram, Sociometry 32, 425 (1969)

INTERPRETACIÓN DEL EXPERIMENTO DE MILGRAM

• ¿Es 6 un resultado sorprendente para el experimento?

• ¿En los 60? ¿Hoy en día? ¿Por qué?

• Si la red social mundial fuera una red puramente aleatoria…

• Pool y Kochen (1978): Cada persona tiene unos 1000 amigos, variando en 500-1500

• Mínimo ~ 500 elecciones para el primer enlace

• ~ 5002 = 250,000 vecinos potenciales para el segundo grado

• ~ 5003 = 125,000,000 vecinos potenciales para el tecer grado

• ¿Y si las redes complejas fueran completamente “cliquish” (subgrafos totalmente

conectados (clique): coeficiente medio de clustering → 1)?

• Todos los amigos de mis amigos serían mis amigos

• ¿Qué ocurriría?

EL VOLUMEN EXPONENCIAL DE LAS REDES COMPLEJAS (1)

El secreto que subyace al efecto de mundos pequeños se
encuentra en el volumen de la red

dS

(

)

=

4

d

EL VOLUMEN EXPONENCIAL DE LAS REDES COMPLEJAS (2)

El secreto que subyace al efecto de mundos pequeños se
encuentra en el volumen de la red

dN

(

)

=

d

∑

x

=

1

4

x

=

(2

dd

+

~)1

d

2

Crecimiento polinomial

EL VOLUMEN EXPONENCIAL DE LAS REDES COMPLEJAS (3)

El secreto que subyace al efecto de mundos pequeños se
encuentra en el volumen de la red

dN

(

)

=

d

∑

x

=

1

4

x

=

(2

dd

+

~)1

d

2

Crecimiento polinomial

EL VOLUMEN EXPONENCIAL DE LAS REDES COMPLEJAS (4)

El secreto que subyace al efecto de mundos pequeños se
encuentra en el volumen de la red

dN

(

)

=

d

∑

x

=

1

k

x

=

k

d

+

1

−

1

k

−

1

d

~

k

dN

(

)

=

d

∑

x

=

1

4

x

=

(2

dd

+

~)1

d

2

Crecimiento exponencial

Crecimiento polinomial

EL VOLUMEN EXPONENCIAL DE LAS REDES COMPLEJAS (5)

El secreto que subyace al efecto de mundos pequeños se
encuentra en el volumen de la red

dN

(

)

=

d

∑

x

=

1

k

x

=

k

d

+

1

−

1

k

−

1

d

~

k

dN

(

)

=

d

∑

x

=

1

4

x

=

(2

dd

+

~)1

d

2

Crecimiento exponencial

Crecimiento polinomial

d

k

≈

N

d

≈

log

N

k

⇓

d

≈

ln

N

ln

k

LAS REDES COMPLEJAS NO SON ÁRBOLES (1)

Crecimiento exponencial:

d

≈

ln

N

ln

k

El clustering inhibe la propiedad de mundos pequeños, reduce el volumen exponencial

Algunos de los vecinos de tus vecinos también son tus vecinos

S

)1(

=

k

S

1)0(

=

S

)2(

<

k

2

S

)1(

=

k

M

dS
)(

<

k

d

S

)2(

=

k

2






kN

−

−

1

N



≈


2

(
1

−

)

p

k

S

)3(

=

Sk



)2(



2

kN

−

1(

−

p

)

−

k

N



≈


3

k

1(

−

pk

)

M

dS
)(

=

dSk

(

−



1)1


−

dS

(

+−

)1

dS

(

−

)2

N


≈


d

(
1

k

−

k

d

−

2

)p

LAS REDES COMPLEJAS NO SON ÁRBOLES (2)

Crecimiento exponencial:

d

≈

ln

N

ln

k

El crecimiento exponencial continúa mientras N(d) < N

dS
)(

≈

k

d

(
1

−

k

d

−

2

)

p

d

=

k






1

−

d

1
−

k

N






LAS REDES COMPLEJAS NO SON ÁRBOLES (3)

Crecimiento exponencial:

d

≈

ln

N

ln

k

El crecimiento exponencial continúa mientras N(d) < N

dS
)(

≈

k

d

(
1

−

k

d

−

2

)

p

d

=

k






1

−

d

1
−

k

N






LAS REDES COMPLEJAS NO SON ÁRBOLES (4)

Crecimiento exponencial:

d

≈

ln

N

ln

k

El crecimiento exponencial continúa mientras d ≤ <d>

dS
)(

≈

k

d

(
1

−

k

d

−

2

)

p

d

=

k






1

−

d

1
−

k

N






CLUSTERING versus ALEATORIEDAD

Concepto

Una red puede ser un mundo pequeño en tanto en cuanto el clustering pueda ignorarse

¿Dónde se localizaría la red social?

Red clusterizada

Red aleatoria

CLUSTERING versus ALEATORIEDAD

Interpretación del Clustering (1)

El coeficiente de
clustering vale cero

Localmente estructurada

Puramente aleatoria

CLUSTERING versus ALEATORIEDAD

Interpretación del Clustering (2)

El Clustering implica localidad

La aleatoriedad permite atajos

Localmente estructurada

Puramente aleatoria

CLUSTERING versus ALEATORIEDAD

¿Son reconciliables? (1)

¿Puede una red con una estructura local muy fuerte ser a la vez un
mundo pequeño?

CLUSTERING versus ALEATORIEDAD

¿Son reconciliables? (2)

•

Fenómeno de mundo pequeño = distancias medias pequeñas:

<d>red ≈ ln(N)

• Clustering:

<C>red >> <C>aleatoria

Ejemplos de redes reales con ese comportamiento:

• Red neuronal del C. elegans

• Redes semánticas de los idiomas

• Red de actores de Hollywood

• Redes alimentarias

• Red eléctrica de EEUU

MODELO DE WATTS Y STROGATZ (1)

La solución para reconciliar mundos pequeños y clustering es
mezclar estructura y aleatoriedad

Modelo Watts-Strogatz para
la generación de mundos
pequeños:

1. Construir una red de retículo en

anillo con N nodos, cada uno con
<k> vecinos, con L=N· <k>/2
enlaces (N >> <k> >> ln N)

2.

Reasignar cada enlace con
probabilidad p (en sentido
horario) → <k>/2 vueltas para
cubrir los N· <k>/2 enlaces

0

No permitir auto-enlaces ni enlaces
repetidos (múltiples)

N

=

20

;



<

k

>=

4

p

1

D.J. Watts y S.H. Strogatz. Collective dynamics of
'small-world' networks. Nature 393: 440-442 (1998)

MODELO DE WATTS Y STROGATZ (2)

• Cada nodo tiene <k> ≥ 4 vecinos (estructura local fuerte)

• Cada nodo tiene <k>/2 vecinos a cada lado

• Modelo ajustable: se puede variar la probabilidad 0 ≤ p ≤ 1 de

reasignar un nodo

• Con un p pequeño se mantiene una red retículo regular

• Con un p grande se transforma en una red totalmente aleatoria

MODELO DE WATTS Y STROGATZ (3)

Pregunta

¿Cuál de las dos salidas siguientes del modelo corresponde a una
mayor probabilidad de reasignación de enlaces?

MODELO DE WATTS Y STROGATZ (4)

La solución para reconciliar mundos pequeños y clustering es
mezclar estructura y aleatoriedad

Mundo grande
fuertemente
clusterizado: <d>
es función de N

d

retículo

=

N

2

k

C

retículo

=

3

4

0

p

Mundo pequeño
débilmente
clusterizado: <d> es
función de ln N

d

aleatoria

=

ln

N

ln

k

C

=

aleatoria

k

N

1

MODELO DE WATTS Y STROGATZ (5)

¿Qué ocurre en la zona intermedia?

El algoritmo introduce p· N· <k>/2 enlaces no regulares. Mediante
simulación numérica, podemos observar que:

• Hay una reducción muy rápida de la distancia media <d> por la aparición

de los enlaces “atajo”

• Hay una reducción muy suave del coeficiente de clustering <C>

d

d

MODELO DE WATTS Y STROGATZ (6)

La solución para reconciliar mundos pequeños y clustering es
mezclar estructura y aleatoriedad

d

d

1% de enlaces

reasignados

10% de enlaces

reasignados

Modelo Watts-Strogatz:
Para eliminar el clustering hace
falta una alta aleatoriedad pero
para debilitar la localidad basta
una poca

MODELO DE WATTS Y STROGATZ (7)

¿Puede una red con una estructura local muy fuerte ser a la vez un
mundo pequeño?
¡SI! Basta con unos pocos enlaces aleatorios

MODELO DE WATTS Y STROGATZ (8)

Red de Facebook

¿Puede una red con una estructura local muy fuerte ser a la vez un
mundo pequeño?
¡SI! Basta con unos pocos enlaces aleatorios

MODELO DE WATTS Y STROGATZ (9)

Otras redes reales

Albert and Barabási, Reviews of Modern Physics 74,47 (2002)

MODELO DE WATTS Y STROGATZ (10)

Otras redes reales (2)

Mapa de colaboraciones científicas

MODELO DE WATTS Y STROGATZ (11)

Conclusiones (1)

¿Puede una red con una estructura local muy fuerte ser a la vez un
mundo pequeño?
¡SI! Basta con unos pocos enlaces aleatorios

Modelo Watts-Strogatz:
o Alternativamente se puede considerar otra variante del modelo
que añade enlaces aleatorios con probabilidad p, manteniendo
el retículo inicial

MODELO DE WATTS Y STROGATZ (12)

Conclusiones (2)

¿Puede una red con una estructura local muy fuerte ser a la vez un
mundo pequeño?
¡SI! Basta con unos pocos enlaces aleatorios

Modelo Watts-Strogatz:
o Proporciona conocimiento sobre la interrelación entre el

clustering y la topología de mundos pequeños

o Captura la esencia estructural de muchas redes reales
o Tiene en cuenta el alto coeficiente de clustering observado en las

redes reales

o No representa una distribución de los grados realista (hubs)
o Los enlaces largos son menos frecuentes que los cortos

MODELO DE WATTS Y STROGATZ (13)

Modelo Netlogo

http://www.ladamic.com/netlearn/NetLogo4/SmallWorldWS.html

EXPERIMENTO DE MILGRAM:

Actualización (1)

Experimento basado en e-mails:

Dodds, Muhamad, Watts (2003).
Science 301

• 18 objetivos
• 13 países distintos

• Más de 60,000 participantes
• 24,163 cadenas de mensajes
• 384 alcanzaron el objetivo

Distancia media = 4.0

Fuente de la imagen: NASA

http://visibleearth.nasa.gov/view_rec.php?id=2429

EXPERIMENTO DE MILGRAM:

Actualización (2)

Experimento basado en e-mails:

Dodds, Muhamad, Watts (2003).
Science 301

• 18 objetivos
• 13 países distintos

• Más de 60,000 participantes
• 24,163 cadenas de mensajes
• 384 alcanzaron el objetivo

Distancia media = 4.0

EXPERIMENTO DE MILGRAM:

Actualización (3)

Experimento basado en Facebook:

Backstrom, L., Boldi, P., Rosa, M., Ugander, J. & Vigna,
S. (2011). Four degrees of separation. CoRR,
abs/1111.4570

El experimento de Milgram no disponía
de un mapa adecuado de la red social
mundial. Hoy en día, FB es una buena
aproximación

Mapa FB Mayo 2011: 721 millones de
usuarios activos, 68 billones de
relaciones: distancia media = 4.74

Este valor más cercano a la distancia
media teórica: 3.90

MUNDOS PEQUEÑOS:

Red social mundial

d

=

log

N

log

k

En sociología, una persona cualquiera conoce directamente a otras mil,