1 Modelos de Conectividad Redes de mundo pequeño Carlos Aguirre Maeso Escuela Politécnica superior

2 Redes de mundo pequeño ● En muchas redes reales se puede observar que – Los caminos medios entre nodos son cortos (del mismo orden de los de un grafo aleatorio). – Los nodos estan altamente clusterizados (del mismo orden que un grafo regular).

3 Redes de mundo pequeño ● En 1998 Watts y Strogatz (Nature, 1998) proponen un modelo de red dependiente de un paramétro p. ● Este modelo interpola entre un grafo regular y un grafo aleatorio.

4 Método de construcción (i) ● Se colocan inicialmente los nodos en un anillo y cada nodo se conecta con los 2k vecinos a izquierda y derecha. ● Para cada rama de este grafo, con probabilidad p se decide si la rama se modifica o no.

5 Método de construcción (ii) ● Si la rama se modifica, se elige un nuevo nodo al azar con probabilida uniforme. ● Se evitan ramas dobles y autoconexiones. ● Este proceso produce pNk atajos en el grafo.

6 Método de construcción (iii)

7 Sustrato inicial. ● Como sustrato inicial se suele tomar un grid monodimensional cumpliendo las siguientes condiciones. – N >> k >> log(N) – Cada nodo esta conectado con sus 2k vecinos a izquierda y derecha.

8 Sustratos bi-conexos. ● El modelo de red original de Watts y Strogatz tiene el mismo numero de componentes biconexas que los grafos regulares. ● Las redes reales suelen tener un numero mayor de componentes biconexas (redes de comunicaciones).

9 Sustratos bi-conexos.

10 ● El modelo anterior permite crear redes de tipo Mundo-pequeño con un numero elevado de componentes bi-conexas. ● El sustrato inicial es un grafo regular pero con un numero elevado de componentes biconexas. ● Presenta una transicion a aleatorio similar a la de los anillos.

11 Sustratos dirigidos y ponderados. ● El modelo original de Watts y Strogatz no contempla la posibilidad de grafos con direccion y peso. ● Existen redes en la naturaleza donde aparecen la direccionalidad y el peso (redes neuronales, redes sociales, etc)

12 Sustratos dirigidos y ponderados.

13

14 Parámetros. ● El procedimiento de Watts y Strogatz sobre el sustrato inicial produce una transición en el comportamiento del camino carácteristico y del indice de clusterizacion. ● Ambos dos han de pasar de valores altos propios del grafo regular a valores pequeños propios del grafo aleatorio

15 Parámetros. ● En una malla monodimensional – L = N(N+k-2)/2k(N-1) = O(N) – C = 3(k-2)/2(k-1) = O(1) ● En un grafo aleatorio – L=O(log(N)) – C=0

16 Parámetros. ● Watts y Strogatz observaron que la transición en el comportamiento de los valores era diferente para el caso de camino caracteristico L y para el indice de clusterización C. ● El camino característico presentaba la transición de régimen mucho antes que el indice de clusterización

17 Parámetros.

18 ● Cuando se consideran otros sustratos tales como grafos bi-conexos o grafos con dirección peso también se puede observar el mismo fenomeno en el comportamiento de C y L. ● Además las propiedades iniciales del grafo (bi- conectividad, dirección, peso) no se pierden durante la transición

19 Parámetros. Grafos bi-conexos

20 Parámetros. Grafos con dirección y peso

21 Parámetros. ● L no empieza a decrecer hasta que p > 1/Nk (es decir hasta que no aparece al menos un atajo). ● Por tanto, el valor de p para el cual se entra en la zona de mundo pequeño es dependiente de N y k.

22 Parámetros. ● Para una probabilidad fija p, existe un valor N' tal que L = O(N) si N N' ● Se puede demostrar el valor de p que para un valor fijo de N y k produce la transición de L es – p = 1/kN

23 Parámetros. ● Para el camino característico de puede demostrar que: ● Donde

24 Parámetros. ● Para el indice de clusterización se puede demostrar que:

25 Parámetros. ● La distribución del grado de los nodos debe pasar de una delta en el grado medio de cada nodo 2k a una distribución de Poisson.

26 Parámetros.

27 ● La distribución espectral tambien sufre una transición en funcion de p.

28 Algunas redes de mundo pequeño