Percolación. Introducción a los procesos estocásticos.

• Teoría: Fenómenos críticos. Procesos estocásticos.
• Técnica numérica: Simulación Monte Carlo. Análisis de tamaño finito.
• Programación: Fortran, C, dynamiclattice.

Modelo:

Sea una conjunto de N ordenadores interconectados entre si de forma que cualquier usuario de uno de ellos puede comunicarse con cualquier otro ordenador. Por simplicidad (sin que ello afecte a los fenómenos que queremos estudiar) supondremos que cada ordenador está situado en un nodo de un retículo cuadrado de lado L. Además supondremos que un ordenador solo está conectado con sus vecinos más próximos de la red. De esta forma, si un usuario del ordenador A envia un mensaje a otro usuario del ordenador B, para que éste llegue, debe de existir al menos un camino de ordenadores interconectados entre A y B. En el caso de que todos los nodos de la red estén ocupados por ordenadores que funcionan la comunicación entre A y B está garantizada. Sin embargo, supongamos que en un cierto momento hay una proporción 1-p de ordenadores estropeados y/o apagados y que éstos se distribuyen aleatoriamente por la red. Es obvio que si p = 0 (i.e. todos estropeados) es imposible que cualquier usuario de A se conecte con cualquier otro en B. Si p tiene valores cercanos a cero, tampoco esperamos que sea posible esa interconectividad si A y B están muy alejados. De hecho, se sabe que existe un valor crítico de p que llamaremos p_c de forma que si p > p_c existe al menos un conjunto de ordenadores interconectados que se extiende por toda la red. Si p < p_c tendremos zonas de ordenadores interconectados pero que no se extienden por toda la red. Lo que hace interesante a este modelo es comprender lo que ocurre alrededor de p_c y en p_c. En particular para p = p_c la estructura geométrica del agrupamiento de ordenadores interconectados más grande tiene estructura fractal. Esta propiedad asi como muchas otras es debida a que p = p_c es un punto crítico y el sistema tiene un cambio de fase: de fase conexa p > p_c a fase no conexa p < p_c.

Problemas:

• Obligatorio: Diseñar y escribir el programa que construye agrupamientos de ordenadores interconectados dado un p.

• Voluntario (1): Para cada tamaño de la red L = 16, L = 32, L = 64 y L = 128:

  • (a) Obtener p_c.
  • (b) Distribución del número de ordenadores que pertenecen al agrupamiento para varios valores de p < p_c, para p = p_c y para varios valores de p > p_c.

  Nota: para tener suficiente estadística hacer M = 10⁵ realizaciones para cada tamaño.

• Voluntario (2): Para p = p_c hallar la dimensión fractal del agregado. Para ello tomar el lado del cuadrado L = 512. Generar una configuración. Contar el número de ordenadores M(l) funcionando en cajas (centradas) de tamaños: l = 10, l = 20, l = 50, l = 100, l = 200. Promediar sobre muchas configuraciones para tener una buena estadística. Sabemos que si un objeto no es fractal la masa que ocupa en un volumen tiene una relación directa M(l)/l² = d donde d es la densidad. Si el objeto es fractal se cumple que M(l)/l^d_f = cte. En nuestro caso M es el número de ordenadores funcionando en la caja de lado l. d_f se denomina dimensión fractal.

Método numérico:

Lo más directo para generar una configuración de ordenadores donde la proporción 1-p de ellos no funciona sería el barrer secuencialmente la red (i,j) donde i,j Î (1,2,...,L). Con probabilidad p daríamos valor a N(i,j) = 1 y con probabilidad 1-p valor N(i,j) = 0 donde N(i,j) representa que el ordenador en (i,j) está funcionando o no respectivamente. El problema del anterior algoritmo es que generamos una configuración donde conviven agrupamientos grandes y pequeños mezclados entre si, de forma que para detectar la distribución de tamaños y/o el agrupamiento más grande hemos de (posteriormente) recurrir a algoritmos sofisticados para su detección. Nosotros vamos a utilizar un método alternativo que genera agrupamientos típicos para un p dado. Para ello utilizamos un proceso de crecimiento:

• (0) Etiquetar todos los puntos de la red como no definidos: N(i,j) = 2 i,j Î (1,2,...,L). Ocupar un punto del centro del retículo: N(L/2,L/2) = 1.
• (1) Generar y/o modificar la lista de puntos adyacentes y no definidos al agregado. Si la lista no contiene puntos entonces FIN.
• (2) Elegir aleatoriamente uno de los puntos de la red adyacentes y no definidos al agregado: (m,n).
• (3) Generar un número aleatorio uniforme v Î [0,1]. Si v < p entonces N(m,n) = 1, Si v > p entonces N(m,n) = 0.
• (4) Ir a (1).