Modelo Erdös–Rényi

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Un grafo generado por el modelo binomial de Erdos and Renyi (se empleó un valor de p=0.01).

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] se denomina 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[editar]

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 descarta. 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 contraio 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[editar]

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 elllo 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. Pero sin embargo en los M enlaces generados, puede que no estuviera v_j. Suponemos entonces que 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}

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 enclaces (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 distribuió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 distribucicó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[editar]

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 se distinguen en la distribuciones de grado, que en el caso de las generadas por este modelo son poisonianas, 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[editar]

  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
  3. 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
  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

Véase también[editar]