Sección 3 Redes Aleatorias

library(reticulate)

Ya hemos analizado cómo medimos la estructura de las redes y los métodos matemáticos, estadísticos y computacionales para dar sentido a los datos que obtenemos de nuestras mediciones. Hemos visto, por ejemplo, cómo medir la estructura de Internet y, una vez que la hemos medido, cómo determinar su distribución de grados, su diámetro o la centralidad de sus nodos.

Una pregunta evidente que surge es: ``Si sé que una red tiene alguna propiedad particular, como una distribución de grados específica, ¿qué efecto tendrá eso en el comportamiento más amplio del sistema?’’ Resulta que propiedades como las distribuciones de grado pueden, de hecho, tener enormes efectos en los sistemas en red, lo cual es una de las principales razones por las que estamos interesados en ellas.

Y una de las mejores maneras de entender y adquirir intuición sobre estos efectos es construir modelos matemáticos.

Vamos a ver algunos de los modelos más utilizados de estructura de redes, modelos que imitan los patrones de conexiones en redes. Estos modelos nos permiten crear redes artificiales con parámetros conocidos, lo cual es útil por dos razones: primero, nos proporcionan comprensión sobre preguntas fundamentales de estructura, por qué las redes tienen la forma que tienen y cómo cambian al modificar los parámetros, y segundo, proporcionan una base sobre la cual construir una comprensión de los procesos que tienen lugar en las redes, como la propagación de enfermedades en redes sociales o la búsqueda de información en la Web.

3.1 El Modelo de Erdös Renyi para construir redes aleatorias

Vamos a construir una función donde generemos un modelo \(G(N,p)\): cada par de los \(N\) vértices está conectado con probabilidad \(p\).

import random
import networkx as nx
import matplotlib.pyplot as plt

def grafo_erdos_renyi(N, p):
    G = nx.Graph()
    G.add_nodes_from(range(N))
    
    # agregar aristas con probabilidad p
    for i in range(N):
        for j in range(i+1, N):
            if random.random() < p:
                # U~Unif(0,1), P(U<p)=p
                G.add_edge(i, j)
                
    return G

Con está función, podemos definir los parámetros y realizar una red aleatoria.

# parámetros
N = 12
p = 1/6

# generar grafo
G = grafo_erdos_renyi(N, p)

# layout (posición de nodos)
pos = nx.spring_layout(G, seed=42)

# dibujar
plt.figure(figsize=(6,6))
nx.draw(G, pos, with_labels=True, node_color="lightblue", edge_color="gray")

# guardar imagen
plt.savefig("grafo_erdos_renyi.png", dpi=300)

# mostrar
plt.show()

Networkx ya tiene implementada la función de un grafo de Erdös Renyi.

N = 20   # número de nodos
p = 0.2  # probabilidad de conexión

G = nx.erdos_renyi_graph(n=N, p=p)

# visualizar
nx.draw(G, with_labels=True)
plt.show()

3.1.1 Distribución de grado

from scipy.stats import binom, poisson

# Parámetro: grado medio deseado
k_mean = 50

# Valores de N
Ns = [10**2, 10**3, 10**4]

# Rango de k para graficar
k_vals = np.arange(20, 81)

plt.figure(figsize=(8, 5))

# --- Curva Poisson teórica ---
poisson_pmf = poisson.pmf(k_vals, mu=k_mean)
plt.plot(k_vals, poisson_pmf, '--', lw=2, label='POISSON')

# --- Curva binomial teórica ---
# Para comparar, usamos N grande (por ejemplo 10^4)
N_ref = 10**4
p_ref = k_mean / (N_ref - 1)
binom_pmf = binom.pmf(k_vals, N_ref - 1, p_ref)
plt.plot(k_vals, binom_pmf, '-', lw=2, label='BINOMIAL')

# --- "Datos" para distintos N ---
markers = ['^', 'o', 'v']

for N, marker in zip(Ns, markers):
    p = k_mean / (N - 1)

    # Muestreamos grados directamente de Binomial(N-1, p)
    # Esto representa los grados de los nodos en G(N,p)
    grados = np.random.binomial(N - 1, p, size=50000)

    # Histograma normalizado
    probs = np.array([(grados == k).mean() for k in k_vals])

    plt.plot(
        k_vals, probs,
        linestyle='None',
        marker=marker,
        markersize=5,
        label=fr'N=$10^{int(np.log10(N))}$'
    )

plt.xlabel('k', fontsize=12)
plt.ylabel(r'$p_k$', fontsize=12)
plt.xlim(20, 80)

## (20.0, 80.0)

plt.ylim(0, 0.10)

## (0.0, 0.1)

plt.legend(frameon=False)
plt.tight_layout()
plt.savefig("distribucion_grado_red_aleatoria.png", dpi=300)
plt.show()

3.1.2 Número de Aristas

Veamos que para mismos parámetros, las realizaciones de una red aleatoria nos dan distintos números de aristas.

def grafo_erdos_renyi(N, p, seed=None):
    """
    Genera una realización del grafo aleatorio G(N,p).
    """
    if seed is not None:
        random.seed(seed)

    G = nx.Graph()
    G.add_nodes_from(range(N))

    for i in range(N):
        for j in range(i + 1, N):
            if random.random() < p:
                G.add_edge(i, j)

    return G


def dibujar_realizaciones(N, p, n_realizaciones=3, layout="spring", seed_base=10):
    """
    Dibuja varias realizaciones de G(N,p) con los mismos parámetros.
    """
    fig, axes = plt.subplots(1, n_realizaciones, figsize=(5 * n_realizaciones, 5))

    if n_realizaciones == 1:
        axes = [axes]

    for k, ax in enumerate(axes):
        G = grafo_erdos_renyi(N, p, seed=seed_base + k)

        # Elegir layout
        if layout == "circular":
            pos = nx.circular_layout(G)
        else:
            pos = nx.spring_layout(G, seed=seed_base + k)

        L = G.number_of_edges()

        nx.draw_networkx_nodes(
            G, pos, ax=ax,
            node_size=300,
            node_color="#7a4fa3"
        )
        nx.draw_networkx_edges(
            G, pos, ax=ax,
            edge_color="limegreen",
            width=1.5
        )

        ax.set_title(f"Realización {k+1}\nN={N}, p={p}, L={L}", fontsize=12)
        ax.set_axis_off()

    plt.tight_layout()
    plt.show()


# Ejemplo con 3 realizaciones
dibujar_realizaciones(N=12, p=1/6, n_realizaciones=3, layout="circular")

Un ejemplo más grande:

dibujar_realizaciones(N=100, p=0.1, n_realizaciones=3, layout="spring")

Podríamos aumentarle que nos de el número esperado de aristas.

import math

def dibujar_realizaciones_con_esperanza(N, p, n_realizaciones=3, layout="spring", seed_base=10):
    fig, axes = plt.subplots(1, n_realizaciones, figsize=(5 * n_realizaciones, 5))

    if n_realizaciones == 1:
        axes = [axes]

    L_esperado = p * N * (N - 1) / 2

    for k, ax in enumerate(axes):
        G = grafo_erdos_renyi(N, p, seed=seed_base + k)

        if layout == "circular":
            pos = nx.circular_layout(G)
        else:
            pos = nx.spring_layout(G, seed=seed_base + k)

        L = G.number_of_edges()

        nx.draw_networkx_nodes(G, pos, ax=ax, node_size=250, node_color="#7a4fa3")
        nx.draw_networkx_edges(G, pos, ax=ax, edge_color="limegreen", width=1.2)

        ax.set_title(
            f"Realización {k+1}\nL = {L}\nE[L] = {L_esperado:.2f}",
            fontsize=12
        )
        ax.set_axis_off()

    plt.tight_layout()
    plt.show()


dibujar_realizaciones_con_esperanza(N=12, p=1/6, n_realizaciones=3, layout="circular")

Para hablar específicamente del número de aristas, también conviene hacer muchas simulaciones y graficar la distribución de L:

def simular_numero_aristas(N, p, n_sim=1000):
    valores_L = []

    for s in range(n_sim):
        G = grafo_erdos_renyi(N, p, seed=s)
        valores_L.append(G.number_of_edges())

    return valores_L


N = 12
p = 1/6
valores_L = simular_numero_aristas(N, p, n_sim=1000)

L_esperado = p * N * (N - 1) / 2

plt.figure(figsize=(8, 5))
plt.hist(valores_L, bins=range(min(valores_L), max(valores_L)+2), edgecolor="black")
plt.axvline(L_esperado, linestyle="--", linewidth=2, label=f"E[L]={L_esperado:.2f}")
plt.xlabel("Número de aristas L")
plt.ylabel("Frecuencia")
plt.title(f"Distribución del número de aristas en G({N},{p})")
plt.legend()
plt.show()

Lo que podemos concluir de esto es que:

el número de aristas no es fijo,
varía de realización a realización,
pero oscila alrededor de su valor esperado.

Aunque fijemos \(N\) y \(p\), el grafo que obtenemos no es único. Cada par de nodos decide independientemente si se conecta o no. Por eso, distintas realizaciones del mismo modelo tienen distinta forma y distinto número de aristas.

3.1.3 Ejercicios: Grafos aleatorios de Erdős–Rényi

Ejercicio 1. Número de aristas en una realización

Considere un grafo aleatorio \(G(N,p)\) con \(N=20\) y \(p=0.2\).

Genere una realización del grafo.
Calcule el número de aristas observadas \(L\).
Calcule el número esperado de aristas: \[ \langle L \rangle = p \frac{N(N-1)}{2}. \]
Compare el valor observado con el valor esperado.
Dibuje la red obtenida.

Pregunta conceptual.
¿Por qué el número de aristas observado no tiene por qué coincidir exactamente con \(\langle L \rangle\)?

Ejercicio 2. Variabilidad del número de aristas

Fije \(N=30\) y \(p=0.1\).

Genere 100 realizaciones independientes del grafo aleatorio \(G(N,p)\).
Para cada realización, calcule el número de aristas \(L\).
Construya un histograma de los valores obtenidos.
Calcule el promedio muestral de \(L\).
Compare este promedio con el valor teórico: \[ \langle L \rangle = p \frac{N(N-1)}{2}. \]

Pregunta conceptual.
Explique por qué, aun cuando los parámetros \(N\) y \(p\) son los mismos, distintas realizaciones pueden tener diferente número de aristas.

Ejercicio 3. Grado promedio

Considere un grafo aleatorio \(G(N,p)\) con \(N=100\) y \(p=0.05\).

Genere una realización del grafo.
Calcule el grado de cada nodo.
Obtenga el grado promedio observado.
Compare con el valor teórico: \[ \langle k \rangle = p(N-1). \]
Verifique numéricamente que \[ \langle k \rangle_{\text{obs}} = \frac{2L}{N}, \] donde \(L\) es el número de aristas observadas.

Pregunta conceptual.
¿Por qué el promedio de grados está relacionado con el número de aristas mediante la expresión \(\frac{2L}{N}\)?

Ejercicio 4. Distribución de grados

Considere un grafo aleatorio \(G(N,p)\) con \(N=100\) y \(p=0.05\).

Genere una realización del grafo.
Calcule la secuencia de grados.
Haga un histograma de la distribución de grados.
Calcule el grado promedio observado.
Compare visualmente la distribución obtenida con una distribución binomial.

Pregunta conceptual.
¿Por qué en el modelo de Erdős–Rényi la distribución de grados se modela mediante una distribución binomial?

Ejercicio 5. Efecto de la probabilidad de conexión

Fije \(N=50\) y considere los valores \[ p=0.01,\;0.05,\;0.1,\;0.2. \]

Genere una realización del grafo aleatorio \(G(N,p)\) para cada valor de \(p\).
Para cada grafo, calcule:
- el número de aristas \(L\),
- el grado promedio observado,
- el número de componentes conexas.
Dibuje las cuatro redes obtenidas.
Organice los resultados en una tabla.

Pregunta conceptual.
Describa cómo cambia la estructura de la red al aumentar el valor de \(p\).

Ejercicio 6. Exploración del número de aristas y del grado promedio

Fije \(N=100\) y considere una colección de valores de \(p\) en el intervalo \([0.01,0.20]\).

Para cada valor de \(p\), genere una realización del grafo aleatorio \(G(N,p)\).
Calcule para cada caso:
- el número de aristas \(L\),
- el grado promedio observado.
Grafique el número de aristas observado en función de \(p\).
Grafique el grado promedio observado en función de \(p\).
Compare los resultados con las expresiones teóricas: \[ \langle L \rangle = p \frac{N(N-1)}{2}, \qquad \langle k \rangle = p(N-1). \]

Pregunta conceptual.
¿De qué manera dependen el número esperado de aristas y el grado promedio esperado del parámetro \(p\)?

3.1.4 Ejercicios: componente gigante, clustering y regímenes en grafos de Erdős–Rényi

Ejercicio 1. Componentes conexas al variar la probabilidad de conexión

Fije \(N=100\) y considere los valores \[ p = 0.001,\;0.005,\;0.01,\;0.02,\;0.03,\;0.05. \]

Para cada valor de \(p\):

Genere una realización del grafo aleatorio \(G(N,p)\).
Calcule el número de componentes conexas.
Calcule el tamaño de la componente conexa más grande.
Dibuje la red obtenida.
Organice los resultados en una tabla.

Pregunta conceptual.
¿Cómo cambia la estructura de la red al aumentar \(p\)? ¿En qué rango parece emerger una componente gigante?

Ejercicio 2. Tamaño relativo de la componente gigante

Fije \(N=200\) y considere valores de \(p\) en el intervalo \([0.001,0.03]\).

Para cada valor de \(p\), genere una realización del grafo aleatorio \(G(N,p)\).
Calcule el tamaño de la componente conexa más grande, denotado por \(S_{\max}\).
Calcule la fracción \[ \frac{S_{\max}}{N}. \]
Grafique \(\frac{S_{\max}}{N}\) en función de \(p\).

Pregunta conceptual.
¿En qué rango de valores de \(p\) comienza a crecer rápidamente la componente más grande?

Ejercicio 3. Aparición de la componente gigante y grado promedio

Fije \(N=200\) y considere los valores \[ p = \frac{0.5}{N-1},\;\frac{1}{N-1},\;\frac{1.5}{N-1},\;\frac{2}{N-1},\;\frac{3}{N-1}. \]

Para cada valor de \(p\):

Calcule el grado promedio esperado \[ \langle k \rangle = p(N-1). \]
Genere una realización del grafo.
Calcule el tamaño de la componente conexa más grande.
Compare los resultados obtenidos.

Pregunta conceptual.
¿Qué relación observa entre la aparición de una componente gigante y el valor del grado promedio esperado?

Ejercicio 4. Coeficiente de clustering en una realización

Considere un grafo aleatorio \(G(N,p)\) con \(N=100\) y \(p=0.05\).

Genere una realización del grafo.
Calcule el coeficiente de clustering local de cada nodo.
Calcule el coeficiente de clustering promedio de la red.
Compare el valor observado con el valor teórico esperado \[ C \approx p. \]

Pregunta conceptual.
¿Por qué en el modelo de Erdős–Rényi el coeficiente de clustering esperado es aproximadamente igual a \(p\)?

Ejercicio 5. Clustering promedio al variar \(p\)

Fije \(N=100\) y considere valores de \(p\) en el intervalo \([0.01,0.20]\).

Para cada valor de \(p\), genere una realización del grafo aleatorio \(G(N,p)\).
Calcule el coeficiente de clustering promedio observado.
Grafique el clustering promedio observado en función de \(p\).
Compare con la recta teórica \[ C = p. \]

Pregunta conceptual.
¿Cómo depende el clustering promedio del parámetro \(p\)?

Ejercicio 6. Componente gigante y clustering

Fije \(N=200\) y considere valores de \(p\) en un intervalo que incluya el umbral de aparición de la componente gigante.

Para cada valor de \(p\):

Genere una realización de \(G(N,p)\).
Calcule:
- el tamaño relativo de la componente más grande, \[ \frac{S_{\max}}{N}, \]
- el coeficiente de clustering promedio \(C\).
Grafique ambas cantidades en función de \(p\).

Pregunta conceptual.
¿Qué diferencia hay entre una propiedad global, como el tamaño de la componente gigante, y una propiedad local, como el clustering?

Ejercicio 7. Conectividad total de la red

Fije \(N=100\) y considere valores de \(p\) cercanos a \[ \frac{\log N}{N}. \]

Calcule el valor aproximado de \(\frac{\log N}{N}\).
Elija varios valores de \(p\) por debajo y por encima de ese umbral.
Para cada valor de \(p\), genere varias realizaciones del grafo.
Determine en cada caso si el grafo es conexo o no.
Estime la proporción de grafos conexos para cada valor de \(p\).
Grafique esa proporción en función de \(p\).

Pregunta conceptual.
¿Cuál es la diferencia entre que exista una componente gigante y que toda la red sea conexa?

3.2 Ejercicios: efecto de mundo pequeño

Networkx tiene la función watts_strogatz_graph(N, k, p), donde \(N\) son la cantidad de vértices, \(k\) con cuantos vecinos más cercanos se conecta cada vértice y \(p\) la probabilidad. Deberán usar esa gráfica en algunos de los siguientes ejercicios.

Ejercicio 1. Red regular y distancias

Considere una red regular en anillo con \(N=100\) nodos, donde cada nodo está conectado con sus \(k=4\) vecinos más cercanos.

Genere la red.
Dibuje la red obtenida.
Calcule el coeficiente de clustering promedio.
Calcule la longitud media de camino entre nodos.
Interprete los resultados.

Pregunta conceptual.
¿Cómo describiría la estructura local y global de esta red?

Ejercicio 2. Efecto de reconectar algunas aristas

Considere redes de Watts–Strogatz con \(N=100\), \(k=4\) y distintos valores de la probabilidad de reconexión \[ \beta = 0,\;0.01,\;0.05,\;0.1,\;0.5,\;1. \]

Para cada valor de \(\beta\):

Genere una realización de la red.
Calcule el coeficiente de clustering promedio.
Calcule la longitud media de camino.
Organice los resultados en una tabla.

Pregunta conceptual.
¿Cómo cambian el clustering y la longitud media de camino al aumentar \(\beta\)?

Ejercicio 3. Régimen de mundo pequeño

Considere el modelo de Watts–Strogatz con \(N=100\) y \(k=4\).

Para varios valores de \(\beta\), calcule: \[ C(\beta), \qquad L(\beta). \]
Normalice estos valores respecto al caso regular \(\beta=0\): \[ \frac{C(\beta)}{C(0)}, \qquad \frac{L(\beta)}{L(0)}. \]
Grafique ambas cantidades en función de \(\beta\).
Identifique el rango de valores de \(\beta\) en el que la red presenta efecto de mundo pequeño.

Pregunta conceptual.
¿Por qué se dice que una red está en el régimen de mundo pequeño cuando la longitud media de camino disminuye mucho, pero el clustering permanece relativamente alto?

Ejercicio 4. Comparación entre Watts–Strogatz y Erdős–Rényi

Considere una red de Watts–Strogatz con \(N=100\), \(k=4\) y un valor pequeño de \(\beta\), y compárela con una red de Erdős–Rényi con número de nodos similar y grado promedio comparable.

Genere ambas redes.
Calcule en cada caso:
- el coeficiente de clustering promedio,
- la longitud media de camino.
Dibuje ambas redes.
Compare los resultados.

Pregunta conceptual.
¿Por qué una red de Watts–Strogatz puede presentar efecto de mundo pequeño de forma más clara que una red de Erdős–Rényi?

3.3 Ejercicios: Redes libres de escala y distribuciones de grado

Para los siguientes ejercicios, se propone el uso de la siguiente función:

def distribucion_grado(grados):
    k, conteos = np.unique(grados, return_counts=True)
    pk = conteos / len(grados)
    return k, pk

Ejercicio 1. Comparación de distribuciones

Genera dos conjuntos de datos de tamaño grande (por ejemplo, \(N = 10^4\)):

Uno que siga una distribución de Poisson.
Otro que siga una distribución de ley de potencia con exponente \(\gamma\).

Calcula la distribución de grado \(p_k\) en ambos casos.

Tareas:

Grafica ambas distribuciones en escala lineal.
Grafícalas en escala log-log.
Compara visualmente ambas gráficas.

Preguntas:

¿Qué diferencias observas entre ambas distribuciones?
¿En cuál aparecen nodos con grados muy grandes (hubs)?

Ejercicio 2. Efecto de la escala log-log

Usando una muestra con distribución de ley de potencia:

Tareas:

Grafica la distribución de grado en escala lineal.
Grafícala en escala log-log.

Preguntas:

¿Qué información se pierde en la escala lineal?
¿Por qué la gráfica log-log permite observar mejor la cola de la distribución?

Ejercicio 3. Linear binning vs log-binning

Genera un conjunto de grados con distribución de ley de potencia.

Tareas:

Construye un histograma usando bins lineales.
Construye un histograma usando bins logarítmicos.
Grafica ambos en escala log-log.

Preguntas:

¿Aparece una meseta en la cola con bins lineales?
¿Qué cambia al usar bins logarítmicos?
¿Cuál método representa mejor la distribución?

Ejercicio 4. Distribución acumulada

Dada una muestra de grados con ley de potencia:

Tareas:

Calcula la distribución acumulada complementaria: \[ P(k) = P(K \geq k) \]
Grafícala en escala log-log.

Preguntas:

¿Qué ventaja tiene la distribución acumulada respecto al histograma?
¿Qué sucede con el ruido en la cola?

Ejercicio 5. El papel del exponente \(\gamma\)

Genera distribuciones de ley de potencia con distintos valores de \(\gamma\), por ejemplo:

\[ \gamma = 2.1, \; 2.5, \; 3.0, \; 4.0 \]

Tareas:

Grafica todas las distribuciones en escala log-log.

Preguntas:

¿Cómo cambia la forma de la distribución al variar \(\gamma\)?
¿Para qué valores aparecen hubs más grandes?
¿Cuándo la distribución empieza a parecerse a una red aleatoria?

Ejercicio 6. Tamaño de la red y hubs

Para distintos tamaños de red:

\[ N = 10^2, 10^3, 10^4, 10^5 \]

genera muestras con distribución de ley de potencia.

Tareas:

Para cada \(N\), calcula el grado máximo \(k_{\max}\).
Grafica \(k_{\max}\) como función de \(N\).

Preguntas:

¿Cómo crece el hub más grande con el tamaño de la red?
¿Es el crecimiento rápido o lento?

Ejercicio 7. Redes aleatorias vs redes libres de escala

Genera dos redes con el mismo número de nodos:

Una red de Erdős–Rényi.
Una red de Barabási–Albert, esto simula la red libre de escala.

Tareas:

Calcula la distribución de grado en ambas redes.
Grafícalas en escala log-log.
Calcula:
- grado promedio
- grado máximo

Preguntas:

¿En cuál red aparecen hubs?
¿En cuál red los grados son más homogéneos?

Ejercicio 8. Distancias en redes

Usando las redes del ejercicio anterior:

Tareas:

Calcula la distancia promedio entre nodos (en la componente gigante si es necesario).

Preguntas:

¿Cuál red tiene menor distancia promedio?
¿Cómo se relaciona esto con la presencia de hubs?

Ejercicio 9. Robustez de la red

Considera una red libre de escala.

Tareas:

Elimina nodos de forma aleatoria y mide el tamaño de la componente gigante.
Elimina nodos en orden decreciente de grado (primero los hubs).
Compara ambos casos.

Preguntas:

¿Qué tipo de eliminación afecta más a la red?
¿Qué nos dice esto sobre la importancia de los hubs?

Ejercicio 10. Análisis de una red real o simulada

Selecciona una red (real o generada).

Tareas:

Calcula su distribución de grado.
Grafícala en escala log-log.
Decide si:
- es exponencialmente acotada, o
- tiene cola pesada.

Preguntas:

¿Hay evidencia de hubs?
¿El promedio describe bien a la red?