Modelo Erdös–Rényi

En teoría de grafos el modelo Erdős–Rényi (a veces nombrado en la literatura abreviado como modelo ER), nombrado así por ser un estudio que realizaron los matemáticos Paul Erdős y Alfréd Rényi,^[1] es uno de los métodos empleados en la generación de grafos aleatorios. En este modelo se tiene que un nuevo nodo se enlaza con igual probabilidad con el resto de la red, es decir posee una independencia estadística con el resto de nodos de la red. Hoy en día se emplea como una base teórica en la generación de otras redes.^[2]^[3]

Concepto

Si consideramos N nodos de una red sin conectar y distribuidos de forma aleatoria, podemos imaginar que en un instante inicial enlazamos dos cualesquiera, de esta forma en pasos sucesivos vamos enlazando aleatoriamente de dos a dos nodos. Los nodos que se encuentren enlazados se descartan. Si repetimos el proceso M veces eligiendo un par de nodos en cada turno al final habremos establecido como máximo M enlaces entre parejas de nodos. Si M es un valor pequeño con respecto al valor total de nodos muchos de los nodos estarán desconectados, mientras que por el contrario otros nodos estarán formando pequeñas islas.

Por el contrario, si M es grande en comparación con N el número total de nodos, es muy posible que casi todos los nodos estén enlazados entre sí. Cuando se enlazan los nodos de esta forma aparecen propiedades específicas en la distribución de grado $P(k)$ ya que posee propiedades de distribución de Poisson. Durante muchas décadas a partir de los años 1950 se pensó que las redes con esta característica eran las más adecuadas para describir ciertas redes complejas y pronto se vio que no era del todo cierto.

Propiedades

Para calcular la probabilidad $P(k)$ (distribución de grado) de que un nodo tenga k conexiones en la red aleatoria generada con el modelo Erdös–Rényi, primero se intenta calcular la probabilidad $p_{c}$ de que una pareja elegida al azar esté enlazada entre sí. Para ello se calcula el número total de posibles parejas en una red de N nodos, a ese número total lo denominamos $N_{p}$ y su expresión es:

N_{p}={\dbinom {N}{2}}={\frac {N(N-1)}{2}}

como el número de parejas enlazadas por el modelo es M, se tiene por lo tanto la expresión analítica de la probabilidad $p_{c}$ como:

p_{c}={\frac {M}{N_{p}}}={\frac {2M}{N(N-1)}}

si tomamos en la red generada un nodo particular al azar y lo denominamos $v_{j}$ , el número de nodos enlazados a pares que contuvieran a $v_{j}$ sería N-1, ya que $v_{j}$ se puede enlazar con exactamente N-1 nodos restantes de la red. Sin embargo en los M enlaces generados, puede que no estuviera $v_{j}$ . Suponemos entonces que estuviera en k de ellas. La probabilidad en este caso de que estuviera $v_{j}$ contenido en k parejas de las N-1 posibles es:

P(k)={N-1 \choose k}(p_{c})^{k}(1-p_{c})^{N-1-k}

Esta fórmula corresponde a una distribución binomial para M y N de valor finito. Si se tiene en consideración ahora que la red empieza a crecer hasta llegar a valores grandes del número de nodos (N) y de enlaces (M) hasta llegar al punto en que: $\textstyle N\to \infty$ y $\textstyle M\to \infty$ . De esta forma se tiene que la cantidad:

z={\frac {2M}{N}}

permanece en valores completamente finitos y la distribución de grado P (k) se convierte en una distribución de Poisson de la forma

P(k)=e^{-z}{\frac {z^{k}}{k!}}

que como se ha mencionado es una distribución de Poisson de promedio en z. En los papers posteriores del año 1960 Erdös y Rényi empezaron a estudiar la dinámica de las redes en crecimiento^[4] llegando a estudiar transiciones de fase en las redes en función de p.

Aplicaciones

Las aplicaciones de este modelo son muy limitadas debido a que pocas redes reales se comportan tal y como se describe en el modelo Erdös–Rényi,^[3] no obstante existen aproximaciones en teoría de redes sobre todo en el campo de las redes sociales (redes de afiliación y grafos bipartitos). Una diferencia clara entre las redes reales y las generadas por este modelo es la distribución de grado, que en el caso de las generadas por este modelo son poissonianas, mientras que en la realidad tienden a ser más exponenciales.^[5] En las redes con distribuciones poisonianas se concentra la probabilidad en torno a un valor de k (grado nodal) y decrece a una razón de 1/k! cuando se aleja del valor central. En las redes exponenciales no existe un valor preferente y la probabilidad decae a lo largo del espectro de k a medida que éste crece (véase red libre de escala).

Referencias

↑ Erdős, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae 6: 290–297
↑ West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 0-13-014400-2
↑ ^a ^b "Random graph models of social networks", M. E. J. Newman, D. J. Watts, S. H. Strogatz, 2566–2572, PNAS, February 19, 2002, vol. 99, suppl. 1
↑ Erdős, P.; Rényi, A. (1960). "The Evolution of Random Graphs". Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61
↑ Albert, R., Jeong, H. and Barabási, A.-L., 2000. Attack and error tolerance of complex networks. Nature 406, 378–382

Véase también

Modelo Watts y Strogatz

Datos: Q605807

[1] Erdős, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae 6: 290–297

[2] West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice Hall, ISBN 0-13-014400-2

[social-3] "Random graph models of social networks", M. E. J. Newman, D. J. Watts, S. H. Strogatz, 2566–2572, PNAS, February 19, 2002, vol. 99, suppl. 1

[4] Erdős, P.; Rényi, A. (1960). "The Evolution of Random Graphs". Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61

[5] Albert, R., Jeong, H. and Barabási, A.-L., 2000. Attack and error tolerance of complex networks. Nature 406, 378–382

[1]

[2]

[3]

[4]

[5]