En la física , la teoría de probabilidades , la teoría de grafos , etc. el modelo de clúster azar es un grafo aleatorio que generaliza y unifica el modelo Ising , modelo Potts , y modelo de percolación . Se utiliza para estudiar estructuras combinatorias aleatorias , redes eléctricas , etc. [1] [2] También se le conoce como el modelo RC o, a veces, la representación FK en honor a sus fundadores Kees Fortuin y Piet Kasteleyn . [3]
Definición
Dejar ser un gráfico , yser una configuración de enlace en el gráfico que asigna cada borde a un valor de 0 o 1. Decimos que un enlace está cerrado en el borde Si y abrir si. Si dejamosser el conjunto de enlaces abiertos, entonces un clúster abierto es cualquier componente conectado en. Tenga en cuenta que un cúmulo abierto puede ser un único vértice (si ese vértice no incide en ningún enlace abierto).
Suponga que una arista se abre de forma independiente con probabilidad y cerrado de otra manera, entonces este es solo el proceso de percolación estándar de Bernoulli. La medida de probabilidad de una configuración. se da como
El modelo RC es una generalización de la percolación, donde cada grupo está ponderado por un factor de . Dada una configuración, dejamos ser el número de clústeres abiertos o, alternativamente, el número de componentes conectados formados por los enlaces abiertos. Entonces para cualquier, la medida de probabilidad de una configuración se da como
Z es la función de partición , o la suma de los pesos no normalizados de todas las configuraciones,
Tenga en cuenta que podemos recuperar el modelo de percolación configurando , en ese caso .
Representación de Edwards-Sokal
La representación de Edwards-Sokal (ES) [4] del modelo de Potts lleva el nombre de Robert G. Edwards y Alan D. Sokal . Permite una representación unificada del modelo de giro y el modelo RC como una distribución conjunta de los dos. Además, generaliza naturalmente el algoritmo de Swensden-Wang (SW) para modelos arbitrarios de espín ferromagnético.
Sea el número de vértices y el número de aristas sea . Denotamos un estado de giro como y una configuración de enlace como . La medida de se da como
dónde es la medida uniforme, y es la medida del producto con densidad . Además, es una constante de normalización apropiada, y la función indicadora hace cumplir la siguiente restricción,
lo que significa que un enlace solo puede abrirse en un borde si los giros adyacentes son del mismo estado, lo que se conoce como regla SW.
Para relacionar el modelo de espín con el modelo RC, se pueden mostrar las siguientes características estadísticas: [2]
- La medida marginal de los giros es la medida de Boltzmann del modelo de Potts del estado q a temperatura inversa.
- La medida marginal de los enlaces es la medida de agrupamiento aleatorio con parámetros q y p.
- La medida condicional del giro representa una asignación uniformemente aleatoria de estados de giro en cada componente de conexión.
- La medida condicional de los enlaces representa un proceso de percolación (de relación p ) en los bordes donde se alinean los espines adyacentes.
- La probabilidad de que dos vértices están en el mismo grupo abierto es proporcional a la función de correlación de dos puntos de los giros. [5]
Estas características garantizan que las estadísticas de giro se puedan recuperar por completo de las estadísticas del clúster.
Frustración
Hay varias complicaciones de la representación ES una vez que la frustración está presente en el modelo de giro. Por ejemplo, ya no existe una correspondencia entre las estadísticas de espín y las estadísticas de conglomerados, [6] y la longitud de correlación del modelo RC será mayor que la longitud de correlación del modelo de espín. Esta es la razón detrás de la ineficiencia del algoritmo SW para simular sistemas frustrados.
Relación con otros modelos
El modelo de conglomerados aleatorios es equivalente al modelo de Potts del estado q para (con el caso siendo la percolación de Bernoulli y el caso siendo el modelo de Ising). En general, puede ser cualquier número real positivo, con favoreciendo la formación de menos clusters y favoreciendo la formación de más racimos (en comparación con la percolación). Lalímite describe redes de resistencia lineal . [1]
La función de partición del modelo RC es una especialización del polinomio de Tutte , que a su vez es una especialización del polinomio multivariante de Tutte. [7]
Historia y aplicaciones
Los modelos RC fueron introducidos en 1969 por Fortuin y Kasteleyn , principalmente para resolver problemas combinatorios. [1] [8] [9] Después de sus fundadores, a veces se les conoce como modelos FK . [3] En 1971 lo utilizaron para obtener la desigualdad FKG . Después de 1987, se reavivó el interés por el modelo y las aplicaciones de la física estadística . Se convirtió en la inspiración para el algoritmo Swendsen-Wang que describe la evolución temporal de los modelos de Potts. [10] Michael Aizenman y col. lo usó para estudiar los límites de fase en los modelos 1D de Ising y Potts. [11] [8]
Ver también
- Polinomio de Tutte
- Modelo de ising
- Gráfico aleatorio
- Algoritmo de Swendsen-Wang
- Desigualdad FKG
Referencias
- ^ a b c Fortuin; Kasteleyn (1972). "Sobre el modelo de conglomerados aleatorios: I. Introducción y relación con otros modelos". Physica . 57 (4): 536. Bibcode : 1972Phy .... 57..536F . doi : 10.1016 / 0031-8914 (72) 90045-6 .
- ^ a b Grimmett (2002). "Modelos de conglomerados aleatorios". arXiv : matemáticas / 0205237 .
- ^ a b Newman, Charles M. (1994), Grimmett, Geoffrey (ed.), "Disordered Ising Systems and Random Cluster Representations" , Probability and Phase Transition , NATO ASI Series, Dordrecht: Springer Netherlands, págs. 247-260, doi : 10.1007 / 978-94-015-8326-8_15 , ISBN 978-94-015-8326-8, consultado el 18 de abril de 2021
- ^ Edwards, Robert G .; Sokal, Alan D. (15 de septiembre de 1988). "Generalización de la representación de Fortuin-Kasteleyn-Swendsen-Wang y algoritmo de Monte Carlo" . Physical Review D . 38 (6): 2009-2012. doi : 10.1103 / PhysRevD.38.2009 . PMID 9959355 .
- ^ Kasteleyn, PW; Fortuin, CM (1969). "Transiciones de fase en sistemas de celosía con propiedades locales aleatorias" . Suplemento de la Revista de la Sociedad Física de Japón, vol. 26. Actas de la Conferencia Internacional sobre Mecánica Estadística celebrada del 9 al 14 de septiembre de 1968 en Koyto., P.11 . 26 : 11. Código Bibliográfico : 1969PSJJS..26 ... 11K .
- ^ Cataudella, V .; Franzese, G .; Nicodemi, M .; Scala, A .; Coniglio, A. (7 de marzo de 1994). "Clústeres críticos y dinámicas eficientes para modelos de spin frustrados" . Cartas de revisión física . 72 (10): 1541-1544. doi : 10.1103 / PhysRevLett.72.1541 . hdl : 2445/13250 . PMID 10055635 .
- ^ Sokal, Alan (2005). "El polinomio multivariado de Tutte (modelo de Alias Potts) para gráficos y matroides" . Encuestas en Combinatoria 2005 . págs. 173–226. arXiv : matemáticas / 0503607 . doi : 10.1017 / CBO9780511734885.009 . ISBN 9780521615235.
- ^ a b Grimmett. El modelo de conglomerados aleatorios . http://www.statslab.cam.ac.uk/~grg/books/rcm1-1.pdf .Mantenimiento de CS1: ubicación ( enlace )
- ^ Kasteleyn, PW; Fortuin, CM (1969). "Transiciones de fase en sistemas de celosía con propiedades locales aleatorias". Suplemento de la Revista de la Sociedad Física de Japón, vol. 26. Actas de la Conferencia Internacional sobre Mecánica Estadística celebrada del 9 al 14 de septiembre de 1968 en Koyto., P.11 . 26 : 11. Código Bibliográfico : 1969PSJJS..26 ... 11K .
- ^ Swendsen, Robert H .; Wang, Jian-Sheng (12 de enero de 1987). "Dinámica crítica no universal en simulaciones de Monte Carlo". Cartas de revisión física . 58 (2): 86–88. Código Bibliográfico : 1987PhRvL..58 ... 86S . doi : 10.1103 / PhysRevLett.58.86 . PMID 10034599 .
- ^ Aizenman, M .; Chayes, JT; Chayes, L .; Newman, CM (abril de 1987). "El límite de fase en ferromagnetos de Ising y Potts diluidos y aleatorios". Revista de Física A: Matemática y General . 20 (5): L313 – L318. Código Bibliográfico : 1987JPhA ... 20L.313A . doi : 10.1088 / 0305-4470 / 20/5/010 . ISSN 0305-4470 .
enlaces externos
- Modelo de clúster aleatorio - Wolfram MathWorld