COMPLEXA · Ciencias de la Complejidad y Teoría del Caos
Módulo 20. Procesos colectivos sobre redes y transiciones
194.1. De enlaces locales a una región conectada
Una red puede conservar muchas conexiones y, sin embargo, estar dividida en regiones pequeñas. Otra puede sostener una componente que contiene una fracción importante de todos sus nodos. La percolación estudia cómo aparece o desaparece esa conectividad colectiva cuando se activan, retienen o eliminan elementos según una regla probabilística.
Según la aplicación, el modelo puede representar enlaces disponibles, nodos operativos o posibilidades de transmisión. Una arista abierta puede permitir circulación, pero no especifica cuánto flujo transporta ni con qué velocidad. La conectividad establece una posibilidad estructural; el desempeño dinámico exige reglas adicionales.
En percolación de enlaces, cada arista de una red de base se conserva con cierta probabilidad. En percolación de sitios, se conservan nodos y solo permanecen enlaces entre nodos retenidos. Ambos modelos pueden usar decisiones independientes o incorporar dependencias. La distinción entre ellos cambia probabilidades conjuntas y fracciones de población.
La pregunta clásica trata del límite de tamaño creciente. ¿Existe una componente cuya cantidad de nodos crece proporcionalmente al sistema? Esa componente se denomina gigante en muchos modelos de redes. En una red finita podemos medir el tamaño de la mayor componente, pero no observamos literalmente un límite infinito.
La conectividad completa es una exigencia diferente. Una red puede tener una componente gigante y mantener muchos nodos aislados o pequeños grupos fuera de ella. Al interpretar la cobertura de una infraestructura o el alcance de una propagación, hay que distinguir entre que la red percole y que esté completamente conectada.
Desarrollaremos primero un ejemplo finito que puede enumerarse exactamente. Después usaremos la exploración por ramas para derivar umbrales y tamaños de componente en redes aleatorias. Finalmente examinaremos eliminaciones selectivas, restricciones espaciales y formas de observación que modifican la interpretación.
194.2. Un cuadrado permite separar varias probabilidades
Tomemos un ciclo de cuatro nodos, con una arista por lado. Conservamos cada enlace independientemente con probabilidad . Hay dieciséis subconjuntos posibles de enlaces, aunque no tienen igual probabilidad salvo cuando la retención es un medio.
Para que la red completa permanezca conexa deben sobrevivir tres o cuatro enlaces. Cualquier conjunto de tres forma un camino que alcanza los cuatro nodos. Por tanto, la probabilidad de conectividad completa es
Si la pregunta es conectar dos vértices opuestos, hay dos rutas de dos enlaces que no comparten aristas. Basta que sobreviva una de ellas. La probabilidad resulta
Con retención de un medio, la primera probabilidad vale cinco dieciseisavos y la segunda siete dieciseisavos. Conectar una pareja concreta es menos exigente que conservar conectados los cuatro nodos. Ambas cantidades se calculan sobre el mismo diseño de pérdida.
En este ciclo, el número de componentes es cuatro menos el número de aristas retenidas más un término que vale uno cuando sobreviven las cuatro y se forma el ciclo completo. Su esperanza es
Con retención de un medio vale 2,0625, un promedio sobre los resultados posibles que no coincide con el número de componentes de ninguna realización.
Estas expresiones son polinomios suaves. En un sistema finito no hay una singularidad matemática en un valor especial de retención. Podemos definir un umbral operacional, por ejemplo donde una probabilidad cruza un valor elegido, pero dependerá del criterio. La transición crítica se define mediante el comportamiento de familias de sistemas al aumentar su tamaño.
El ejemplo muestra por qué debemos formular el resultado de interés antes de calcular robustez. Conectividad completa, alcance de una pareja y tamaño de la mayor componente pueden responder de manera diferente a un mismo porcentaje de enlaces retenidos.
Podemos calcular además el alcance esperado desde un nodo elegido como origen. Cada uno de sus dos vecinos es alcanzable si sobrevive el enlace directo o, cuando este falta, si sobreviven los tres enlaces de la ruta alternativa. Esa probabilidad es p más p al cubo menos p a la cuarta. El nodo opuesto tiene la probabilidad calculada antes, dos veces p al cuadrado menos p a la cuarta. Al sumar las tres posibilidades y contar el origen, obtenemos el tamaño medio de su componente.
Con retención de un medio, el resultado es 2,5625 nodos. Esa cifra difiere tanto del número esperado de componentes como de la probabilidad de conectividad completa. Describe cuántos nodos son accesibles en promedio desde el origen, bajo un modelo donde toda ruta abierta puede usarse. No informa cuánto tardaría en alcanzarlos un proceso dinámico ni cuántos recibirían realmente un recurso limitado.
La linealidad de la esperanza permite sumar indicadores de accesibilidad aunque sean dependientes. Si el origen queda aislado, todos valen cero simultáneamente; si la red permanece conexa, todos valen uno. No necesitamos su independencia para calcular la media, pero sí debemos tener en cuenta su dependencia al calcular la varianza o probabilidades conjuntas.
194.3. Explorar una red por sus conexiones restantes
En una red aleatoria grande con estructura local aproximadamente arborescente, seguir un enlace permite descubrir nuevos nodos sin encontrar enseguida rutas ya visitadas. Esta exploración se aproxima mediante un proceso de ramificación. El grado del nodo alcanzado está sesgado por sus oportunidades de ser encontrado.
Si la distribución original de grados es , el grado medio encontrado al seguir una arista se calcula con pesos proporcionales a . Una arista se empleó para llegar y quedan grado menos uno oportunidades nuevas. El número medio de esas oportunidades es
En percolación independiente de enlaces, cada oportunidad sobrevive con probabilidad . La reproducción media de la exploración es . El umbral de la aproximación, donde esa cantidad cruza uno, es
La expresión necesita un denominador positivo y un umbral dentro del intervalo admisible. Si el grado excedente es demasiado pequeño, ninguna retención inferior a uno puede producir una exploración supercrítica de este tipo. Los casos críticos degenerados, como ciertas familias de ciclos de grado dos, deben examinarse por separado.
Molloy y Reed (1995) estudiaron la aparición de componentes grandes para secuencias de grado bajo condiciones asintóticas. Callaway y colaboradores (2000) desarrollaron resultados de percolación sobre redes aleatorias con heterogeneidad de grados y ocupación. La fórmula se apoya en esa clase de organización y puede fallar en otros grafos con los mismos momentos.
Los triángulos y otras dependencias locales pueden invalidar la contabilidad de ramas independientes. Una exploración puede usar varias aristas para llegar al mismo nodo y sobrecontar nuevos destinos. Las comunidades fuertes o las restricciones espaciales también pueden limitar la expansión de maneras que los momentos marginales no describen.
El segundo momento aparece en el denominador porque los nodos de alto grado se encuentran con mayor frecuencia y ofrecen más continuaciones. Esa doble ponderación puede reducir el umbral bajo pérdida uniforme. Sin embargo, la conclusión vale para un modelo de retención específico y puede cambiar mucho cuando se eliminan preferentemente esos nodos.
Si el grado medio original es cero, todos los nodos están aislados y las expresiones que dividen por ese promedio no están definidas. El problema puede resolverse directamente, porque no hay ninguna ruta entre nodos distintos, sea cual sea la retención de enlaces. En percolación de sitios solo cambia cuántos aislados permanecen. Reconocer este caso evita usar una fórmula fuera de su dominio. También conviene separar las redes con algunos aislados de la red vacía completa; los aislados cuentan en la distribución de grados y en el denominador de población, aunque nunca continúen una exploración por aristas.
194.4. Calcular el tamaño de la componente gigante
Definamos las funciones generadoras de grados y de grado excedente
Sea la probabilidad de que una arista candidata no conduzca a la componente gigante durante la exploración. Puede fallar porque no fue retenida o porque, al llegar al otro extremo, todas sus continuaciones fallan. Para percolación de enlaces se tiene
La solución relevante es la menor en el intervalo unitario. La cantidad es la fracción de todos los nodos que pertenece a la componente gigante, ya que en este diseño los nodos no se eliminan. La independencia de ramas sostiene el producto implícito en las funciones generadoras.
Consideremos una red aleatoria regular de grado tres, en el régimen donde esa descripción local es adecuada. Entonces y . El umbral es un medio. Por encima de él, la raíz no trivial es .
Con retención de tres cuartos, la raíz es un tercio y la fracción gigante es
La cifra es una predicción asintótica del conjunto aleatorio. Una red concreta pequeña puede mostrar desviaciones y una red regular organizada en módulos débilmente conectados no tiene por qué responder igual. Un grado constante no determina cómo se distribuyen los enlaces.
Por debajo del umbral, la raíz pertinente es uno y la fracción gigante es cero en el límite. Aun así, pueden existir componentes finitas grandes para el tamaño observado, especialmente cerca de la transición.
La ecuación también muestra cómo crece la componente al superar el umbral. En este modelo regular, una expansión cerca de un medio produce crecimiento inicial lineal de la fracción gigante. Ese comportamiento pertenece a una clase de modelos; otras estructuras y reglas pueden modificar la forma o la continuidad de la transición.
Por debajo del umbral también puede calcularse el tamaño esperado de la componente de un nodo uniforme. La primera generación tiene como media el grado medio multiplicado por la retención de enlaces. Cada generación posterior se multiplica por la reproducción de la exploración. Sumar la serie geométrica da uno más el producto de retención y grado medio dividido por uno menos la reproducción, bajo las mismas hipótesis de estructura local arborescente.
En una red regular de grado tres y retención de cuatro décimas, la primera generación tiene media 1,2 y las siguientes se multiplican por ocho décimas. El tamaño esperado es siete, aunque no exista una componente gigante en el límite. Con retención de 0,49, el tamaño esperado sube a 74,5. Una gran respuesta media puede anticipar la transición sin que haya aparecido todavía una fracción macroscópica conectada.
La divergencia del cálculo al aproximarse al umbral expresa una propiedad del límite ideal. En redes finitas, el tamaño de cualquier componente está acotado por la población y las ramas terminan encontrándose. Por eso el crecimiento del tamaño esperado se redondea y depende de la población disponible. Comparar esa dependencia entre varias redes informa más que atribuir a una sola observación grande una transición ya establecida.
194.5. Retener nodos cambia el denominador de la respuesta
En percolación uniforme de sitios, cada nodo se conserva con probabilidad . La probabilidad de que una exploración no alcance la componente gigante satisface una ecuación formalmente parecida
En cambio, la fracción gigante respecto de la población original incluye la probabilidad de que el nodo inicial haya sido retenido
La fracción entre los nodos retenidos es , cuando la retención es positiva. Comunicar una de estas cantidades como si fuera la otra puede exagerar la cobertura. Una componente puede contener casi todos los nodos supervivientes y ser una parte mucho menor de la población inicial.
En el ejemplo regular de grado tres y retención de tres cuartos, la raíz vuelve a ser un tercio. La fracción gigante sobre todos los nodos originales es trece dieciochoavos, aproximadamente 0,72222. Entre los retenidos es veintiséis veintisieteavos, igual a la cifra que obtuvimos antes para percolación de enlaces.
La coincidencia de raíces y de algunas expresiones no hace idénticos ambos diseños. En uno desaparecen enlaces y todos los nodos siguen presentes; en el otro desaparecen nodos con todas sus conexiones. En el segundo, los enlaces incidentes en un mismo nodo quedan correlacionados por la supervivencia de ese nodo.
En un grafo finito, eliminar un nodo puede romper simultáneamente varias rutas y cambiar la población sobre la que se calcula una media. Comparar robustez requiere decidir si interesa servir a todos los nodos originales, a los supervivientes o a una demanda externa. El denominador es parte del objetivo.
También pueden combinarse la retención de nodos y la de enlaces. Bajo independencia y condiciones apropiadas, la exploración incorpora ambas probabilidades, pero el factor de población inicial sigue requiriendo atención. Una reducción de cobertura y una pérdida de funcionamiento no son necesariamente la misma variable.
El capítulo anterior mostró una distinción equivalente en observación parcial, donde conservar nodos con probabilidad dada produce probabilidades conjuntas diferentes de las que da retener enlaces de manera independiente. Aquí esa diferencia se interpreta como disponibilidad estructural; las ecuaciones deben seguir el diseño concreto.
194.6. Una componente gigante no conecta a todos
En una red aleatoria de tipo Erdős–Rényi con grado medio finito, aparece una componente gigante cuando el grado medio efectivo supera uno. Bajo retención uniforme de enlaces, ese grado efectivo es el original multiplicado por la probabilidad de retención. La ecuación de su fracción es
donde es el grado medio de la red de base en el régimen considerado. La solución positiva aparece cuando el producto supera uno. Esta descripción supone independencia y el límite aleatorio pertinente.
La conectividad de todos los nodos exige mucho más. Con grado medio fijo, una fracción aproximadamente exponencialmente pequeña pero positiva puede quedar aislada, de modo que el número esperado de aislados crece con el tamaño.
En el modelo clásico de aristas independientes, la escala de conectividad completa corresponde a un grado medio del orden del logaritmo del número de nodos. Esa escala difiere del umbral de aparición de la componente gigante. Los dos resultados no deben mezclarse al describir cuándo una red se vuelve conectada.
En una infraestructura, una gran componente puede atender la mayor parte de la demanda y dejar fuera grupos pequeños pero importantes. El indicador global debe acompañarse de la distribución de tamaños y de la identidad o ubicación de quienes quedan desconectados.
También importa cómo se elige un nodo o una componente. Si hay dos componentes de tamaños uno y nueve, la media al escoger una componente uniformemente es cinco. Si escogemos un nodo uniformemente y medimos el tamaño de su componente, la media es 8,2, porque la componente grande tiene más oportunidades de ser encontrada.
Las medidas de susceptibilidad en percolación suelen ponderar por el tamaño y excluir la componente gigante cuando se estudia la distribución de componentes finitas. Otras convenciones producen cantidades distintas. Informar solo un «tamaño medio de componente» deja incompleta la definición.
El resumen debe elegirse según la pregunta (tamaño de un brote iniciado en una fuente uniforme, disponibilidad para una pareja de nodos, alcance desde un punto específico o cobertura total). Una misma distribución de componentes permite calcular varias respuestas, pero ninguna reemplaza a las demás.
194.7. Eliminación selectiva y heterogeneidad
Supongamos que la probabilidad de conservar un nodo depende de su grado original y se denota . En una red de configuración bajo las condiciones habituales, la reproducción media de la exploración incorpora esa selección
El grado medio del denominador es el de la red original, cuyos extremos se siguen en la exploración. Sustituir la fracción media de nodos retenidos en una fórmula uniforme da, en general, otro resultado, porque los grados altos pesan más en la continuidad de ramas.
Consideremos una población ideal con mitad de nodos de grado dos y mitad de grado seis. El grado medio original es cuatro. Si retenemos el sesenta por ciento de los nodos de grado dos y ninguno de grado seis, conservamos el treinta por ciento de la población. La reproducción de exploración vale 0,15 y queda por debajo de uno.
Si retenemos el sesenta por ciento de los nodos de grado seis y ninguno de grado dos, conservamos también el treinta por ciento de la población. Ahora la reproducción vale 2,25 y supera uno. La misma cobertura de nodos puede situar al modelo a lados diferentes del umbral.
El ejemplo supone retención aleatoria dentro de cada clase y una red de base sin organización adicional relevante. En una red concreta, el efecto de una eliminación dirigida puede depender de algo más que los grados; los puentes, las comunidades y las dependencias espaciales también pueden dominar la conectividad.
Si se incorporan probabilidades de retención en cada grado, las funciones generadoras permiten calcular una distribución de resultados bajo el diseño selectivo. La interpretación debe distinguir el grado original usado para decidir la retención del grado residual después de eliminar nodos.
Si las decisiones de eliminación se actualizan según grados residuales, aparece un proceso adaptativo diferente. Retirar primero un nodo modifica qué otros quedan clasificados como grandes o pequeños. Una fórmula derivada para selección independiente según grados originales no describe necesariamente esa secuencia.
En aplicaciones, el diseño de pérdida debe responder al mecanismo plausible. Fallas aleatorias, desgaste por carga y pérdida por un peligro espacial generan correlaciones diferentes. Compararlos ayuda a comprender la vulnerabilidad, siempre que quede claro qué escenario produce cada resultado.
194.8. Espacio, ciclos y fallas compartidas
La geometría puede limitar la exploración aunque todos los nodos tengan el mismo número de vecinos. En una red espacial, muchas rutas conducen a zonas cercanas y vuelven a encontrarse. El grado excedente cuenta oportunidades locales, pero puede sobrestimar cuántas regiones nuevas se alcanzan.
Los ciclos cortos son una señal de ese encuentro entre ramas. Dos caminos que parecían independientes pueden compartir un destino o una región vulnerable. La aproximación arborescente deja de describir exactamente la probabilidad de expansión. Su utilidad debe evaluarse con la arquitectura concreta y la escala de observación.
Una falla ambiental puede eliminar simultáneamente nodos próximos. Si tratamos esas pérdidas como sorteos independientes con la misma fracción media, podemos sobrestimar la dispersión del daño y la disponibilidad de rutas alternativas. Un sistema puede resistir muchas pérdidas dispersas y fragmentarse al perder una región pequeña pero estratégicamente situada.
La correlación también puede ser funcional. Varios enlaces con trazos distintos en el grafo pueden depender de una misma instalación, una fuente de energía o un procedimiento administrativo. La percolación independiente no conserva esa dependencia.
Para incorporar estos mecanismos pueden definirse grupos de falla, campos espaciales de retención o modelos explícitos de recursos compartidos. Cada extensión modifica la distribución conjunta. La fracción marginal de supervivencia de cada elemento no determina el efecto de perderlos conjuntamente.
El análisis de escala debe precisar qué significa distancia. En una red geográfica puede medirse una longitud de correlación espacial. En una red abstracta, la distancia por pasos y el crecimiento de vecindarios tienen otra geometría. No corresponde trasladar automáticamente exponentes o relaciones de una retícula regular a cualquier red de contactos.
La comparación con datos puede examinar tamaños de componentes, localización de cortes y respuestas a perturbaciones documentadas. Reproducir solo la fracción de nodos supervivientes deja sin evaluar la organización del daño. El modelo debe explicar qué regiones quedan conectadas y cuáles pierden acceso bajo el mecanismo considerado.
Hay una comparación exacta que muestra el efecto de la geometría. Un árbol infinito regular de grado cuatro tiene umbral de percolación independiente de enlaces igual a un tercio, porque después de llegar a un nodo quedan tres ramas nuevas. En la retícula cuadrada infinita, donde cada nodo también tiene cuatro vecinos, el umbral es un medio. Kesten (1980) demostró este último resultado.
Ambos sistemas tienen el mismo grado local, pero sus vecindarios crecen de manera distinta. En el árbol, las ramas no vuelven a encontrarse y el número de nodos a distancia dada crece exponencialmente. En la retícula, muchas rutas conducen a posiciones ya accesibles y el volumen de un entorno crece de manera polinómica. Los dos primeros momentos de los grados no registran esa diferencia.
Con retención de cuatro décimas, el árbol está por encima de su umbral y la retícula cuadrada por debajo del suyo. Aplicar la fórmula del árbol a la retícula produciría una conclusión cualitativamente equivocada. Se trata de una comparación entre dos arquitecturas definidas, con resultados conocidos, de la que no se deduce que los ciclos desplacen siempre un umbral en una cantidad fija.
En una red espacial empírica, donde pueden coexistir conexiones locales y atajos, el comportamiento puede situarse fuera de cualquiera de estos modelos ideales. La evaluación debe considerar las longitudes, el crecimiento de los vecindarios y las dependencias relevantes; el grado medio y la apariencia del dibujo son insuficientes para decidir la clase del sistema.
194.9. Cómo estudiar una transición con redes finitas
Una simulación de percolación suele variar la probabilidad de retención y generar varias realizaciones en cada valor. Para cada una se calcula la mayor componente y otros resúmenes. La media y la dispersión permiten distinguir tendencias de fluctuaciones; una sola curva obtenida con una secuencia de sorteos puede ocultar variabilidad considerable.
El tamaño de la red debe variar si se quiere estudiar un comportamiento crítico. Un cambio abrupto en una red particular puede proceder de un puente o de una realización específica. La transición asintótica requiere analizar cómo cambian curvas, fluctuaciones y escalas al aumentar el sistema dentro de una familia definida.
También importa si se usa una red de base fija o se generan nuevas redes en cada repetición. El primer diseño mide incertidumbre por retención condicionada a esa arquitectura. El segundo incorpora variabilidad del modelo generativo. Mezclar ambos sin indicarlo dificulta interpretar los intervalos.
La localización de un máximo de fluctuaciones puede tomarse como umbral operacional en sistemas finitos. Su posición puede desplazarse con el tamaño y con el indicador elegido. No debe presentarse como una constante exacta del sistema sin evaluar esa dependencia.
La inferencia de exponentes requiere rangos suficientes y correcciones de tamaño finito. Un ajuste visual sobre pocos puntos puede confundir una zona de transición con una ley de escala. Los criterios del capítulo sobre leyes de potencia siguen siendo pertinentes, junto con la dependencia entre componentes de una misma realización.
La observación parcial puede imitar pérdida por percolación. Si no sabemos qué enlaces están inactivos y cuáles simplemente no fueron registrados, la mayor componente observada mezcla funcionamiento y cobertura. Un modelo de medición permite separar ambas interpretaciones cuando hay información de validación.
Un análisis reproducible conserva red de base, regla de retención, semillas de simulación, definición de componente y denominadores. También registra qué conclusiones se refieren a una realización, a un conjunto de redes o a un límite de tamaño. Esa distinción evita atribuir universalidad a una observación local.
Una implementación puede usar los mismos números aleatorios para comparar distintos valores de retención. Se asigna a cada enlace un número uniforme entre cero y uno y se conserva cuando ese número no supera la probabilidad elegida. Al aumentar la retención, las redes quedan anidadas y ningún enlace previamente disponible desaparece. Este acoplamiento facilita comparar cambios dentro de una misma realización de umbrales aleatorios.
Bajo ese diseño, el tamaño de la mayor componente no puede disminuir al añadir enlaces sobre un conjunto fijo de nodos. Si disminuye, hay un error en el cálculo o se ha cambiado otra parte del problema. La probabilidad de conectar una pareja y la de conectar toda la red también son no decrecientes.
Las curvas obtenidas con ese acoplamiento no son independientes entre valores de retención. Esa dependencia es deliberada y puede reducir ruido en comparaciones, pero debe considerarse al estimar incertidumbre. Para medir variabilidad entre realizaciones, se repite la asignación completa de números aleatorios. Si además se quiere incorporar incertidumbre de la red de base, esa red debe variar en un nivel separado del experimento.
194.10. Qué permite concluir la conectividad colectiva
La percolación traduce una regla de disponibilidad local en probabilidades de conexión a gran escala. El proceso revela umbrales y distribuciones que no pueden deducirse únicamente del porcentaje de elementos conservados. La posición de esos elementos y las dependencias entre sus pérdidas forman parte del resultado.
El cuadrado mostró que alcanzar una pareja, conservar conectividad completa y contar componentes son preguntas diferentes. En las redes aleatorias vimos cómo el grado excedente organiza una exploración aproximadamente arborescente. La comparación entre sitios y enlaces dejó ver que incluso ecuaciones semejantes pueden usar denominadores de población distintos.
Una componente gigante abre una posibilidad estructural de alcance. Para convertirla en transporte efectivo, propagación de una infección o coordinación funcional hacen falta reglas adicionales. Los tiempos, capacidades y dependencias de transmisión pueden modificar qué parte de esa posibilidad se realiza.
La conclusión debe identificar el diseño de retención, el tipo de red y el nivel de aproximación. Con esas condiciones visibles, la percolación permite comparar mecanismos de fragmentación e indicar qué conexiones sostienen el acceso colectivo. El siguiente capítulo añadirá una dificultad distinta, la de los procesos donde una conexión disponible no basta y la activación exige varias exposiciones.
Referencias
- Callaway, D. S., Newman, M. E. J., Strogatz, S. H., y Watts, D. J. (2000). Network robustness and fragility: Percolation on random graphs. Physical Review Letters, 85, 5468–5471. DOI.
- Kesten, H. (1980). The critical probability of bond percolation on the square lattice equals 1/2. Communications in Mathematical Physics, 74, 41–59. DOI.
- Molloy, M., y Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2–3), 161–180. DOI.