El objetivo de esta sección es rescatar las características centrales de las redes aleatorias y simular la red de Erdos-Renyi en Netlogo. Los primeros estudios importantes sobre la modelación de las redes aleatorias fueron iniciados por Rapoport (1949), una década más tarde, Paul Erdos (1959) y Alfred Renyi (1960) estudiaron exhaustivamente estos grafos. Algunas características generales de la red Erdos-Renyi (ER) es que un nuevo nodo se enlaza con igual probabilidad con el resto de la red, además, se dice que cuando los nodos y aristas adoptan un valor finito corresponde a una distribución binomial, y cuando el número de nodos y aristas tienden a infinito, adoptan una distribución Poisson.

Keywords: distribución de grado, red aleatoria, red Erdos-Renyi, distribución Poisson, distribución de grado Poisson.

¿Qué es una red aleatoria?

Es un grafo no dirigido cuyas aristas están conectadas aleatoriamente con una probabilidad \(p\), por tanto, siguen una distribución aleatoria. Los grafos aleatorios son muy útiles para modelar sistemas muy grandes.

La red aleatoria Erdös-Rényi (1960)

La red aleatoria más representativa es la Erdós-Rényi. En esta red se tiene que un nuevo nodo que se enlaza con igual probabilidad con el resto de la red, es decir, posee independencia estadística con el resto de nodos de la red (Newman y Watts Strogatz, 2002).

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 de \(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 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 de la distribución de grado p ya que posee propiedades de distribución Poisson.

Propiedades de la red ER

Para calcular la probabilidad distribución de grado \(p\) de que un nodo tenga \(k\) conexiones en la red aleatoria Erdös–Rényi, primero se intenta calcular la probabilidad 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 y su expresión es, \[N_p=\displaystyle\binom{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 \[N_p=\frac{2M}{N(N-1)}\] Si tomamos en la red generada un nodo particular al azar y le denominamos , el número de nodos enlazados a pares que contuvieran a sería \(N-1\), ya que se puede enlazar con exactamente \(N-1\) nodos restantes de la red. Sin embargo, en los \(M\) enlaces generados, puede que no estuviera. Suponemos entonces que estuviera en \(k\) de ellas. La probabilidad en este caso de que estuviera contenido en \(k\) parejas de las \(N-1\) posibles es, \[N_p=\displaystyle\binom{N-1}{2}(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 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)= \frac{e^{-z}z^{k}}{k!}\] que como se ha mencionado es una distribución de Poisson de media z. En los escritos posteriores del año 1960 Erdös y Rényi empezaron a estudiar la dinámica de las redes en crecimiento profundizando en las transiciones de fase en las redes.

De hecho, siguiendo a Newman (2008), en la década de los años sesenta Erdos y Renyi demostraron que muchas propiedades del gráfico aleatorio se pueden resolver exactamente tomando el límite de n grande. Demostraron que la red aleatoria posee una distribución de grado Poisson, en donde la presencia o ausencia de aristas es independiente. De modo que la probabilidad de que un vértice tenga grado \(k\) es, \[P(k)=\displaystyle\binom{n}{k}p^{k}(1-p)^{(n-k)}\cong\frac{z^{k}e^{-z}}{k!}\] con la última igualdad aproximada volviéndose exacta en el límite de \(n\) grande y \(k\) fijo. Esta es la razón del nombre "Gráfico aleatorio de Poisson".

1. ¿Qué pasa con la distribución de la red y los grados de los nodos conforme aumenta el tamaño de la red?
2. ¿Qué ocurre con el grado medio de la red conforme k aumenta, se mantiene constante, aumenta o disminuye?
3. Con \(N=100\), \(k=200\) y \(p=0.20\), grafique la distribución de grado en el espacio \((k,P_k)\).
4. Graficar la distribución cuando \(N=100\) y \(k=200\). ¿Se distribuye como una función de distribución Poisson?

De los experimentos antes mencionados se percibe que conforme aumenta el tamaño de la red, cuando k es muy grande se tiene una red con distribución aleatoria. De tal manera que podemos pasar de una red desconectada a una red aleatoria, esto es, la red pasa de una fase desconectada a una fase aleatoria, aspecto que tiene que ver con el modelo.

Además, se dice que en una red aleatoria tienen valores de grado similares. Cuanto mayor es el tamaño de la red aleatoria, más parecidos son los grados de los nodos. También se puede mostrar que la probabilidad de hallar un nodo con un grado muy alto o muy bajo es exponencialmente pequeña. Lo que sí es determinante es que la estructura de la red aleatoria varía con el valor de \(p\).

En cuanto a su relación con las redes del mundo real, se afirma que sus propiedades no coinciden con él. Su construcción tiene un sentido más analítico, tienen un coeficiente de agrupamiento bajo.

• Erdös, P.; Rényi, A. (1959). "On Random Graphs. I.". Publicationes Mathematicae 6: 290–297
• Erdös, P.; Rényi, A. (1960). "The Evolution of Random Graphs". Magyar Tud. Akad. Mat. Kutató Int. Közl. 5: 17–61.
• Neuman, M. E. (2008). The Structure and Function of Complex Networks, SIAM REVIEW, Society for Industrial and Applied Mathematics, Vol. 45,No . 2, pp . 167–256.
• Sayama, Hiroki (2015). Introduction to Modeling and Analysis of Complex Systems. Open SUNY textbooks, Milne Library, State University of New York at Geneseo, 485 pages, Print ISBN: 1942341083.
• Solé, Ricard (2009). Redes Complejas, del genoma al internet. Grupo Editorial Planeta, 235 páginas, Barcelona, España.
• Wilensky, U., Rand, W. (2008). NetLogo Random Network model. http://ccl.northwestern.edu/netlogo/models/RandomNetwork Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.Wilensky,
• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/ Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL..
• Wilensky, U. & Rand, W. (2015). Introduction to Agent-Based Modeling: Modeling Natural, Social and Engineered Complex Systems with NetLogo. Cambridge, MA. MIT Press