Un grafo aleatorio se genera mediante reglas probabilísticas. En lugar de estudiar una única estructura, analizamos qué propiedades aparecen normalmente al variar el tamaño y la probabilidad de conexión.
Muchas redes reales contienen incertidumbre: conexiones que aparecen, fallan o todavía no conocemos. Los grafos aleatorios ofrecen modelos para experimentar con esa variabilidad.
Una realización individual puede ser irregular, pero al repetir el experimento emergen patrones sobre grados, componentes, distancias y conectividad.
El modelo describe una distribución de probabilidad sobre un conjunto de grafos. Cada ejecución produce una realización concreta.
Dos realizaciones con los mismos parámetros pueden tener cantidades diferentes de aristas y componentes.
El modelo G(n,p) contiene n vértices. Cada una de las posibles aristas no dirigidas aparece de forma independiente con probabilidad p.
Con p = 0 se obtiene un grafo vacío; con p = 1, el grafo completo Kn.
En un grafo simple no dirigido hay una posible arista por cada par no ordenado de vértices.
La cantidad real de aristas en G(n,p) sigue una distribución binomial con N ensayos y probabilidad p.
El valor esperado se obtiene sumando la probabilidad de aparición de cada arista.
Es un promedio de muchas realizaciones; una muestra particular no tiene por qué coincidir exactamente con él.
Modifica n y p, y genera varias realizaciones. Los colores representan componentes conexas; la componente más grande aparece primero en el resumen.
Parámetros
Medidas observadas
Diagnóstico
El grado de un vértice cuenta éxitos entre sus n − 1 posibles vecinos, por lo que sigue una distribución binomial.
La suma de grados continúa siendo 2|E| en cada realización.
En G(n,m) se elige uniformemente un grafo con n vértices y exactamente m aristas.
| Modelo | Se fija | Varía |
|---|---|---|
| G(n,p) | Probabilidad p | Cantidad de aristas |
| G(n,m) | Cantidad m | Qué pares aparecen |
Para probabilidades muy pequeñas predominan componentes diminutas. Al crecer el grado medio alrededor de 1, comienza a aparecer una componente gigante que contiene una fracción importante de los vértices.
No es un límite exacto para una realización pequeña, sino un cambio probabilístico observado al crecer n.
La conectividad completa requiere una probabilidad mayor que la necesaria para formar una componente gigante.
Cerca del umbral, pequeñas variaciones de p producen cambios grandes en la probabilidad de obtener un grafo conectado.
Un vértice queda aislado si fallan sus n − 1 conexiones posibles.
La desaparición de los últimos vértices aislados está estrechamente relacionada con el umbral de conectividad.
Cada terna de vértices forma un triángulo cuando aparecen sus tres aristas, evento de probabilidad p³.
En G(n,p), el coeficiente de agrupamiento esperado es aproximadamente p, porque dos vecinos se conectan con esa probabilidad.
function generarGnp(n, p) {
const grafo = Array.from({ length: n }, () => []);
for (let u = 0; u < n; u++) {
for (let v = u + 1; v < n; v++) {
if (Math.random() < p) {
grafo[u].push(v);
grafo[v].push(u);
}
}
}
return grafo;
}Recorrer solo u < v evita probar dos veces el mismo par y evita bucles.
Para estimar una probabilidad se generan muchas realizaciones, se mide cada una y se calcula la proporción de éxitos.
let conectados = 0;
for (let ensayo = 0; ensayo < repeticiones; ensayo++) {
const grafo = generarGnp(n, p);
if (esConectado(grafo)) conectados++;
}
const probabilidadEstimada = conectados / repeticiones;Más repeticiones reducen el ruido de muestreo, aunque aumentan el tiempo de cálculo.
Math.random() no permite fijar una semilla de forma estándar. Para experimentos reproducibles conviene usar un generador pseudoaleatorio que acepte semilla.
Se deben registrar semilla, parámetros, cantidad de repeticiones y versión del procedimiento de generación.
La independencia de aristas simplifica el análisis, pero muchas redes reales muestran grados muy desiguales, agrupamiento alto y comunidades.
G(n,p) es un buen modelo nulo: ayuda a decidir si una propiedad observada es más intensa de lo esperable por azar independiente.
Los grafos aleatorios permiten estudiar cómo propiedades globales emergen de decisiones locales probabilísticas. Repetir experimentos revela transiciones que una realización aislada puede ocultar.
En el próximo tema aplicaremos conceptos de grafos al análisis de redes sociales, donde grados, comunidades y difusión adquieren interpretaciones concretas.