1 Redes Aleatorias

2 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto dado (ensamble, familia) de grafos Adaptado de Peter Dodds Applications of Random Networks Complex Networks CSYS/MATH 303, Spring, 2011 Ejemplo: grafos de n=3 nodos 𝑃 𝐺 = si G tiene 3 nodos en otro caso

3 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto dado (ensamble, familia) de grafos Ejemplo: grafos de n=3 nodos Dado un ensamble de grafos, vamos a querer calcular valores medios de propiedades de interés 𝑓 = 𝐺 𝑃 𝐺 𝑓(𝐺)

4 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto dado (ensamble, familia) de grafos Ω 3 = = 2 3! 2! = 2 3 G(N=n) ensamble de grafos de n nodos 𝑃 𝐺 = Ω 𝑛 si G tiene n nodos en otro caso Cuantos hay en total? Cuanto vale Ωn? Si hay n nodos, hay 𝑛 2 = 𝑛 (𝑛−1) 2 posibles pares (enlaces) Cada uno puede estar o no-estar Entonces Ω 𝑛 = 2 𝑛 2 ~ 𝑒 ln 𝑛 2

5 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto dado (ensamble, familia) de grafos G(N) ensamble de grafos de n nodos G(N=n,M=m) conjunto formado por grafos de n vértices y m enlaces 𝑃 𝐺 = Ω 𝑛,𝑚 si G tiene n nodos y m vértices si no Ω 𝑛,𝑚 = 𝑛 2 𝑚 nro de maneras de elegir 2 elementos de n (i.e. nro maximo de posibles enlaces) nro de maneras de elegir m enlaces del nro maximo de posibles enlaces

6 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto (ensamble, familia) dado de grafos G(N) ensamble de grafos de n nodos G(N=n,M=m) conjunto formado por grafos de n vértices y m enlaces 𝑃 𝐺 = Ω 𝑛,𝑚 si G tiene N nodos y M vértices si no Dado un ensamble de grafos, es posible calcular valores medios de propiedades de interés 𝑓 = 𝐺 𝑃 𝐺 𝑓(𝐺) = 1 Ω 𝐺𝜖𝐺(𝑁,𝑀) 𝑓(𝐺) 𝑘 = 𝐺 𝑃 𝐺 𝑘 𝐺 = 𝐺 𝑃 𝐺 2𝑚 𝑛 = 2𝑚 𝑛

7 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto (ensamble, familia) dado de grafos G(N) ensamble de grafos de n nodos G(n,m) conjunto formado por grafos de n vértices y m enlaces G(n,p) conjunto formado por grafos de n vértices tal que la probabilidad de que exista un enlace entre cualquier par de nodos resulta p Entre 1950’1960 Paul Erdos y Alfred Renyi desarrollaron la teoria de grafos aleatorios estudiando las propiedades de este tipo de ensambles m=108 m=90 m=96 n=100, p=0.02 Entre Paul Erdos y Alfred Renyi desarrollaron la teoria de grafos aleatorios estudiando las propiedades de este tipo de ensambles

8 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto (ensamble, familia) dado de grafos G(n) ensamble de grafos de n nodos G(n,m) conjunto formado por grafos de n vértices y m enlaces G(n,p) conjunto formado por grafos de n vértices tal que la probabilidad de que exista un enlace entre cualquier par de nodos resulta p Prob de observar en este ensamble un dado grafo G con n vertices y m enlaces 𝑃 𝐺 = 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 Prob de no tener los enlaces restantes Prob de tener m enlaces

9 Teoría de redes aleatoriasGrafo aleatorio: es un grafo obtenido muestreando un conjunto (ensamble, familia) dado de grafos G(n) ensamble de grafos de n nodos G(n,m) conjunto formado por grafos de n vértices y m enlaces G(n,p) conjunto formado por grafos de n vértices tal que la probabilidad de que exista un enlace entre cualquier par de nodos resulta p Prob de observar en este ensamble un dado grafo G con n vertices y m enlaces 𝑃 𝐺 = 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 nro grafos con n vertices y m enlaces Prob de observar en este ensamble un grafo con n vertices y m enlaces 𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 La probabilidad de ver un grafo con exactamente m vertices en este ensamble, sigue una distribucion Binomial de probabilidades

10 Repaso matematico… G(n,p)Supongamos que en una prueba exito/fracaso la probabilidad de éxito es p. La probabilidad de tener x exitos en N pruebas independientes : ……..10 N pruebas (con x 1´s) 𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 𝑃 𝑥 = 𝑁 𝑥 𝑝 𝑥 (1−𝑝) 𝑁−𝑥 N=5 N=20 N=50 p=0.5 𝑥 = 𝑥𝑃 𝑥 = 𝑁𝑝 𝑥 2 =𝑝 1−𝑝 𝑁+ 𝑝 2 𝑁 2 𝜎= 𝑥 2 − 𝑥 2 = 𝑝 1−𝑝 𝑁

11 Propiedades de G(N,p) 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝 G(n,p)𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝 𝜎= 𝑚 2 − 𝑚 2 = 𝑝 1−𝑝 𝑛 2 𝑃 𝑥 = 𝑁 𝑥 𝑝 𝑥 (1−𝑝) 𝑁−𝑥 𝑥 =𝑁𝑝 𝑥 2 =𝑝 1−𝑝 𝑁+ 𝑝 2 𝑁 2 𝜎 𝑚 ~ 𝑛 2 ~ 1 𝑛 𝜎= 𝑥 2 − 𝑥 2 = 𝑝 1−𝑝 𝑁 Aunque el ensamble admite grafos con cualquier número de enlaces la mayor parte de los grafos poseen m~ si n>>1

12 Propiedades de G(N,p) 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝 Razonable: nro total de pares posibles por la probabilidad p de que se establezca un enlace Razonable: maximo nro de posibles enlaces de un nodonro por la probabilidad p de que se establezca un enlace 𝑘 = 2 𝑚 𝑛 = 𝑛−1 𝑝 𝜎 𝑘 = 𝑛−1 (1−𝑝)𝑝 𝜎 𝑘 𝑘 ~ 1 𝑛 La distribución de grado se angosta para redes gdes.

13 Propiedades de G(N,p) 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝 Coeficiente de Clustering: 𝐶 ∆ =3 #𝑡𝑟𝑖𝑎𝑛𝑔𝑢𝑙𝑜𝑠 #𝑡𝑟𝑖𝑝𝑙𝑒𝑡𝑒𝑠 = 𝑁 𝑁−1 𝑁−2 𝑝 𝑁 𝑁−1 𝑁−2 𝑝 2 =𝑝 𝑘 = 2 𝑚 𝑛 = 𝑛−1 𝑝 𝐶 𝑖 = 2 #𝑣𝑒𝑐 𝑒𝑛𝑙𝑎𝑧𝑎𝑑𝑜𝑠 𝑘 𝑖 ( 𝑘 𝑖 −1) = 2 𝑘 𝑖 ( 𝑘 𝑖 −1) 𝑝 𝑘 𝑖 ( 𝑘 𝑖 −1) 2 =𝑝

14 Propiedades de G(N,p) 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝𝑃 𝑀=𝑚 = 𝑛 2 𝑚 𝑝 𝑚 (1−𝑝) 𝑛 2 −𝑚 𝑚 = 𝑚=0 𝑛 2 𝑃 𝑚 𝑚 = 𝑛 2 𝑝 = 𝑛 𝑛−1 2 𝑝 𝑘 = 2 𝑚 𝑛 = 𝑛−1 𝑝 Para redes muy gdes, 𝑛→∞, en las que se mantiene finito, 𝑝→0 𝐶→0 Redes presentan pocos loops Localmente se parecen a arboles 𝐶=𝑝

15 Distribución de grado Quiero estimar Pk probabilidad de que un nodo tomado al azar de una red G(N,p) tenga k vecinos 𝑃 𝑘 = 𝑛−1 𝑘 𝑝 𝑘 (1−𝑝) 𝑛−1−𝑘 Nro posible de maneras de elegir k vecinos de los n-1 disponibles Pk sigue una distribución binomial Si 𝑛→∞ y p se mantiene fijo, tiende a una distribución Gaussiana Si 𝑛→∞ y =(n-1)p se mantiene finito, entonces 𝑝→0. Vamos a analizar Pk en éste limite

16 Distribución de grado Quiero estimar Pk probabilidad de que un nodo tomado al azar de una red G(N,p) tenga k vecinos 𝑃 𝑘 = 𝑛−1 𝑘 𝑝 𝑘 (1−𝑝) 𝑛−1−𝑘 Analizo los diferentes factores cuando 𝑛→∞,𝑝→0 y c≡=(n-1)p se mantiene finito (1−𝑝) 𝑛−1−𝑘 log (1−𝑝) 𝑛−1−𝑘 =(𝑛−1−𝑘) log (1−𝑝) ~− 𝑛−1−𝑘 𝑝=− 𝑛−1−𝑘 𝑐 𝑛−1 ~−𝑐 log (1−𝑝) ~−𝑝 (1−𝑝) 𝑛−1−𝑘 ~ 𝑒 −𝑐

17 Distribución de grado Quiero estimar Pk probabilidad de que un nodo tomado al azar de una red G(N,p) tenga k vecinos 𝑃 𝑘 = 𝑛−1 𝑘 𝑝 𝑘 (1−𝑝) 𝑛−1−𝑘 Analizo los diferentes factores cuando 𝑛→∞,𝑝→0 y c≡=(n-1)p se mantiene finito (1−𝑝) 𝑛−1−𝑘 ~ 𝑒 −𝑐 𝑛−1 𝑘 = 𝑛−1 ! 𝑛−1−𝑘 !𝑘! = 𝑛−1 𝑛−2 …(𝑛−1−𝑘+1) 𝑘! ~ (𝑛−1) 𝑘 𝑘! 𝑃 𝑘 ~ (𝑛−1) 𝑘 𝑘! 𝑝 𝑘 𝑒 −𝑐 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 Distribución de Poisson

18 Repaso matemático 𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 𝑘 = 𝑘=0 𝑘 𝑃 𝑘 = 𝑒 −𝑐 𝑘=0 𝑘 𝑐 𝑘 𝑘! = 𝑐 𝑒 −𝑐 𝑘=1 𝑐 𝑘−1 (𝑘−1)! = 𝑐 𝑒 −𝑐 𝑗=0 𝑐 𝑗 𝑗! =𝑐 𝑘 2 = 𝑘=0 𝑘 2 𝑃 𝑘 = 𝑘 2 + 𝑘 𝜎 2 = 𝑘 2 − 𝑘 2 = 𝑘 La varianza es igual a la media (!) 𝜎 𝑘 = 1 𝑘

19 G(N,p): Distribución de gradoResultado exacto Límite N>>1, finito

20 Conectividad de G(N,p) p ~ 0 p ~ 1 Grafo disconexoComo se produce esta transición? p ~ 0 p ~ 1 Grafo disconexo Tamaño componente gigante es una cantidad intensiva: o(1) Grafo completamente conexo Tamaño componente gigante es una cantidad extensiva: o(N)

21 La transición Como es el cambio de régimen |CG| intensivo/extensivo?Qué sucede con lo que no es componente gigante…?

22 Tamaño de la Componente GiganteSea u la fracción de la red que no pertenece a la CG (u=1 si no hay componente gigante) Un nodo-i no pertenece a la CG si no está conectado a ningún vértice que pertenezca. Es decir, para todo nodo-j: i no está conectado a j. Esto ocurre con probabilidad : (1-p) i está conectado a j, pero j no pertenece a la CG. Esto ocurre con probabilidad: p*u Por (a) y (b), la probabilidad de que nodo-i no pertenezca al CG, vía el nodo-j resulta : (1-p) + p u 𝑢= 1−𝑝(1−𝑢) 𝑛−1 = 1− 𝑐 𝑛−1 (1−𝑢) 𝑛−1 Entonces, la probabilidad de que nodo-i no pertenezca al CG resulta : (1- p + p u)n-1 log 𝑢 = 𝑛−1 log 1− 𝑐 𝑛−1 1−𝑢 ~ −𝑐 1−𝑢 log (1−𝑥) ~−𝑥

23 Tamaño de la Componente GiganteSea u la fracción de la red que no pertenece a la CG (u=1 si no hay componente gigante) Un nodo-i no pertenece a la CG si no está conectado a ningún vértice que pertenezca. Es decir, para todo nodo-j: i no está conectado a j. Esto ocurre con probabilidad : (1-p) i está conectado a j, pero j no pertenece a la CG. Esto ocurre con probabilidad: p*u Por (a) y (b), la probabilidad de que nodo-i no pertenezca al CG, vía el nodo-j resulta : (1-p) + p u 𝑢= 1−𝑝(1−𝑢) 𝑛−1 = 1− 𝑐 𝑛−1 (1−𝑢) 𝑛−1 Entonces, la probabilidad de que nodo-i no pertenezca al CG resulta : (1- p + p u)n-1 𝑢 ~ 𝑒 −𝑐 1−𝑢

24 Tamaño de la Componente Gigante𝑐= 𝑘 =𝑝 𝑛−1 𝑢 ~ 𝑒 −𝑐 1−𝑢 1−𝑆 ~ 𝑒 −𝑐 𝑆 S = 1-u , fracción de nodos en la CG 𝑆= 1−𝑒 −𝑐 𝑆 (ER 1959)

25 Tamaño de la Componente Gigante𝑆= 1−𝑒 −𝑐 𝑆 𝑐= 𝑘 =𝑝 𝑛−1 𝑦= 1−𝑒 −𝑐 𝑆 y(S) es monotona creciente y tiene curvatura negativa Hay un cambio cualitativo en las soluciones S*=y(S*) para los casos en que la pendiente en el origen toma valor uno 𝑑𝑦 𝑑𝑆 𝑆=0 = 𝑐𝑒 −𝑐𝑆 𝑆=0 =𝑐 c<1 S*=0 c≥1 S*>0 ademas de la trivial

26 Tamaño de la Componente Gigante𝑆= 1−𝑒 −𝑐 𝑆 Es posible distinguir 4 regimenes 𝑘 =1 𝑘 ~ ln 𝑛 𝑦= 1−𝑒 −𝑐 𝑆 S y(S) es monotona creciente y tiene curvatura negativa Hay un cambio cualitativo en las soluciones S*=y(S*) para los casos en que la pendiente en el origen toma valor uno c<1 S*=0 c≥1 S*>0 𝑑𝑦 𝑑𝑆 𝑆=0 = 𝑐𝑒 −𝑐𝑆 𝑆=0 =𝑐

27 Conectividad G(N,p). Régimen sub-crítico𝑘 =1 𝑘 ~ ln 𝑛 no hay componente gigante componente más gde de tamaño ~ ln n componentes aislados con distribución de tamaños exponencial régimen subcrítico 𝑝 𝑠𝑖𝑧𝑒 ~ 𝑠 −3/2 𝑒 − 𝑐−1 𝑠+(𝑠−1) ln 𝑐

28 Conectividad G(N,p). Régimen crítico𝑘 =1 𝑘 ~ ln 𝑛 componente gigante nCG~n2/3 componente gigante incipiente SCG~n-1/3 igual…comparar con regimen subcritico: n=1000: ln n ~ 7 vs n2/3 ~ 95 n= : ln n ~ 14 vs n2/3 ~ 10000 componentes no-gigantes sin loops distribución de tamaños de exponentes sigue ley de potencias régimen crítico 𝑝 𝑠𝑖𝑧𝑒 ~ 𝑠 −3/2

29 Conectividad G(N,p). Régimen supercrítico𝑘 =1 𝑘 ~ ln 𝑛 componente gigante único 𝑛 𝐶𝐺 ~(𝑝− 𝑝 𝑐 )𝑛 componente gigante tiene loops otros componentes aislados con distribución de tamaños exponencial régimen supercrítico 𝑝 𝑠𝑖𝑧𝑒 ~ 𝑠 −3/2 𝑒 − 𝑐−1 𝑠+(𝑠−1) ln 𝑐

30 Conectividad G(N,p). Régimen conectado𝑘 =1 𝑘 ~ ln 𝑛 > ln n p>ln n/n la probabilidad de que un nodo no pertenezca a la CG se anula exponencialmente una única componente en el grafo régimen conectado

31 Las demás se quedan piolasVeamos que cuando existe, sólo existe una única componente gigante Supongamos que existen 2 CG de tamaños: S1.n y S2.n Nro de posibles pares de vértices (i,j) con i en CG1 y j en CG2: S1 S2 n2 Cada uno se conecta con prob: p no se conecta con prob: (1-p) Para que haya 2 CGs la probabilidad, q, de que algunos de esos pares no se conecte debe ser nula 𝑞= 1−𝑝 𝑆 1 𝑆 2 𝑛 2 = 1− 𝑐 𝑛−1 𝑆 1 𝑆 2 𝑛 2 ~ 𝑒 −𝑛𝑐 𝑆 1 𝑆 2 La probabilidad de que no exista vínculo entre S1 y S2 decae exponencilmente log 𝑞 = 𝑆 1 𝑆 2 lim 𝑛→∞ 𝑛 2 1− 𝑐 𝑛−1 =𝑐 𝑆 1 𝑆 2 −𝑛 𝑐−1 ~−𝑛𝑐 𝑆 1 𝑆 2

32 Redes Aleatorias 𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 Familias de redes: G(N,M) , G(N,p)𝐶= 𝑐 𝑛 𝑘 =𝑝 𝑛−1 grado medio 𝑚 =𝑝 𝑛 𝑛−1 2 nro enlaces distribucion de grado coef. clustering 𝑃 𝑘 = 𝑛−1 𝑘 𝑝 𝑘 (1−𝑝) 𝑛−1−𝑘 𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 𝑛 𝐶𝐺 = ln 𝑛 𝑐<1 𝑛 2/3 1≤𝑐< ln 𝑛 (𝑝− 𝑝 𝑐 )𝑛 𝑐> ln 𝑛 𝑑 ~ ln 𝑛 𝑛 diametro

33 Redes Aleatorias 𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 Familias de redes: G(N,M) , G(N,p)𝐶= 𝑐 𝑛 𝑘 =𝑝 𝑛−1 grado medio 𝑚 =𝑝 𝑛 𝑛−1 2 nro enlaces distribucion de grado coef. clustering 𝑃 𝑘 = 𝑛−1 𝑘 𝑝 𝑘 (1−𝑝) 𝑛−1−𝑘 𝑃 𝑘 = 𝑐 𝑘 𝑘! 𝑒 −𝑐 𝑛 𝐶𝐺 = ln 𝑛 𝑐<1 𝑛 2/3 1≤𝑐< ln 𝑛 (𝑝− 𝑝 𝑐 )𝑛 𝑐> ln 𝑛 𝑑 ~ ln 𝑛 𝑛 diametro

34