Modelo Erdös–Rényi

Modelo Erdös–Rényi
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]

Contenido

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 enlzados 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

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 pc de que una pareja elegida al azar esté enlazada entre sí. Para elllo se calcula el número total de posibles parejas en un ared de N nodos, a ese número total lo denominamos Np 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 pc como:

p_c = \frac{N}{N_p} = \frac{2M}{N(N-1)}

si tomamos en la red generada un nodo particular al azar y lo denominamos vj, el número de nodos enlazados a pares que contuvieran a vj sería N-1, ya que vj se puede enlazar con exactamente N-1 nodos restantes de la red. Pero sin embargo en los M enlaces generados, puede que no estuviera vj. Suponemos entonces que que estuviera en k de ellas. La probabilidad en este caso de que estuviera vj 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

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

  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


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Modelo Watts y Strogatz — Red de 20 nodos construida según el modelo Watts y Strogatz (N=20, k=4, β=0.2). El modelo Watts y Strogatz en teoría de redes se emplea para la construcción de algunas redes de mundo pequeño. Genéricamente se trata de un modelo de generación de… …   Wikipedia Español

  • Modelo Barabási–Albert — Red de 1000 nodos generada con el modelo de Modelo de Barabási–Albert En teoría de redes se denomina Modelo de Barabási–Albert (es posible encontrarlo en la literatura abreviadamente como modelo BA) como un algoritmo empleado para generar redes… …   Wikipedia Español

  • Alfréd Rényi — (20 de marzo de 1921 – 1 de febrero de 1970) fue un matemático húngaro que hizo importantes contribuciones a la teoría de combinatoria y de teoría de grafos sobre grafos aleatorios.[1] [2] …   Wikipedia Español

  • Red de mundo pequeño — Saltar a navegación, búsqueda Las redes de mundo pequeño permiten conectar dos nodos con relativamente pocos saltos entre ellos. En la ilustración puede verse una red que sigue el modelo Watts Strogatz En matemática y física una red de mundo… …   Wikipedia Español

  • Grafo aleatorio — Los grafos aleatorios poseen estructuras típicas de los procesos aleatorios. En Matemáticas se denomina grafo aleatorio a un grafo que es generado por algún tipo de proceso aleatorio. La teoría de los grafos aleatorios cae en la intersección… …   Wikipedia Español

  • Distribución de grado — Saltar a navegación, búsqueda Comparación entre dos distribuciones de grado en redes libres de escala y redes aleatorias. En el estudio de grafos y redes complejas, el gra …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”