G03 - Redes Aleatorias
Redes Complejas
19-09-24
Redes Aleatorias
Entrega: 27-09
Ejercicio 3
Los primeros intentos de estudiar las redes aleatorias estuvieron centrados en estudiar el ensamble G(N,p).
Es decir, las redes que surgen de tomar N nodos y enlazarlos con probabilidad p.
Redes Aleatorias
Los primeros intentos de estudiar las redes aleatorias estuvieron centrados en estudiar el ensamble G(N,p).
Es decir, las redes que surgen de tomar N nodos y enlazarlos con probabilidad p.
Tomo un par de nodos
Redes Aleatorias
Los primeros intentos de estudiar las redes aleatorias estuvieron centrados en estudiar el ensamble G(N,p).
Es decir, las redes que surgen de tomar N nodos y enlazarlos con probabilidad p.
Tomo un par de nodos
Genero un número aleatorio
Lo comparo con p
Redes Aleatorias
Los primeros intentos de estudiar las redes aleatorias estuvieron centrados en estudiar el ensamble G(N,p).
Es decir, las redes que surgen de tomar N nodos y enlazarlos con probabilidad p.
Tomo un par de nodos
Genero un número aleatorio
Lo comparo con p
Establezco o no el enlace
Valores medios del ensamble
Número medio de enlaces
Estimemos el número medio de enlaces, <L>:
pL
con el total de pares posibles en la red
(1 - p)m - L
Número medio de enlaces
Para estimar el número medio de enlaces, <L>, debemos tener en cuenta:
donde es el total de pares posibles en la red
Entonces, la probabilidad de tener L enlaces será :
Y <L> no es otra cosa que tomar el valor medio:
Grado medio
Teniendo en cuenta el número medio de enlaces, podemos rápidamente inferir el grado medio
Esto nos permite saber qué probabilidad necesitamos en función del grado medio con el que queremos trabajar
Distribución de grado
Distribución de Grado
Para estudiar la probabilidad de que un nodo tenga grado k, debemos considerar :
Distribución de Grado
Para estudiar la probabilidad de que un nodo tenga grado k, debemos considerar :
Por lo tanto, la probabilidad de que un nodo tenga grado k no es otra cosa que :
una distribución binomial
Distribución de Grado - Aproximación N >> <k>
Para la condición N >> <k>, puede tomarse el límite de la binomial tendiendo a una distribución de Poisson :
Generalmente, esto se hace para poder trabajar de manera más sencilla con las cuentas.
Clustering
Coeficiente de Clustering Local
Para abordar el problema del clustering de la red aleatoria, primero, debemos pensar en la probabilidad de que se generen Li enlaces entre los ki vecinos del nodo i-ésimo. Siguiendo los mismo razonamientos que para el resto de los valores medios, obtenemos que :
Y el coeficiente de clustering local será :
Coeficiente de Clustering Global
Para esto, necesitamos calcular el número de triángulos y el número de tripletes de la red.
La idea general, es tratar de trabajar con la matriz de adyacencia, basándonos en que el grado medio de la red es c.
Necesitaremos calcular : la cantidad de triángulos en la red y la cantidad de tripletes.
Coeficiente de Clustering Global
Evolución de la Red - Criticidad
¿Cómo varía el tamaño de la CG en función de p?
Pensemos ahora que partimos de N nodos pero vamos aumentando p.
A grandes rasgos, podemos decir que:
¿Cómo varía el tamaño de la CG en función de p?
Pensemos ahora que partimos de N nodos pero vamos aumentando p.
A grandes rasgos, podemos decir que:
Intuitivamente, si barremos p deberíamos tener un comportamiento continuo para el tamaño de la CG.
Pero esto no es así, encontramos una pc a partir de la cual el tamaño de la CG se dispara.
Tamaño de la Componente Gigante
Trabajando con el grado medio en vez de con p, tendremos cuatro regímenes:
Más allá de lo empírico
Podemos encontrar la relación del tamaño de la componente gigante en función del grado medio. Tomemos la fracción de nodos que no pertenecen a la CG :
Pensemos cómo puede ocurrir que un nodo i no pertenezca a CG :
Más allá de lo empírico
Por lo tanto, la probabilidad total de que el nodo i no forme parte de la GC a través de estar conectado con j es :
Considerando todos los posibles nodos:
Lo que nos lleva a decir que :
Más allá de lo empírico
Por lo tanto, la probabilidad total de que el nodo i no forme parte de la GC a través de estar conectado con j es :
Considerando todos los posibles nodos:
Lo que nos lleva a decir que :
Trabajando esta expresión :
Más allá de lo empírico
Por lo tanto, la probabilidad total de que el nodo i no forme parte de la GC a través de estar conectado con j es :
Considerando todos los posibles nodos:
Lo que nos lleva a decir que :
Trabajando esta expresión :
Por lo tanto :
Con y
Más allá de lo empírico
Lo que nos lleva a que
Y por lo tanto, tomando S = 0 (nos paramos a la izquierda de la transición
Tenemos entonces la ecuación que define S como :
la cual tiene un punto de inflexión si derivamos con respecto a S :
Más allá de lo empírico
Lo que nos lleva a que
Y por lo tanto, tomando S = 0 (nos paramos a la izquierda de la transición
Tenemos entonces la ecuación que define S como :
la cual tiene un punto de inflexión si derivamos con respecto a S :
Graficamente
Más conectades de lo que creemos
¿Cómo podemos explicar la existencia de estas distancias cortas en redes tan grandes?
Red aleatoria donde cada nodo tiene ⟨k⟩ (en promedio)
Más conectades de lo que creemos
El número esperado de nodos a distancia d o menor desde el nodo inicial es:
‹k›i nodos a distancia i
Más conectades de lo que creemos
El número esperado de nodos a distancia d o menor desde el nodo inicial es:
el número de nodos alcanzables dentro de una distancia dmax es parecida al número total de nodos en la red:
Más conectades de lo que creemos