Utilizando estructura de red para acelerar algoritmos de Monte Carlo de Cadena de Markov
Autores: Askarian, Ahmad; Xu, Rupei; Faragó, András
Idioma: Inglés
Editor: MDPI
Año: 2016
Acceso abierto
Artículo científico
2016
Utilizando estructura de red para acelerar algoritmos de Monte Carlo de Cadena de Markov
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Cadena de Markov Monte Carlo
Tasa de convergencia
Conglomerados
Cadenas de Markov cuasi-lumpables
Distribución de estados
Subconjuntos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Consideramos el problema de estimar la medida de subconjuntos en redes muy grandes. Una herramienta fundamental para este propósito es el algoritmo de Monte Carlo de Cadena de Markov (MCMC). Este algoritmo, aunque extremadamente útil en muchos casos, a menudo sufre de la desventaja de una convergencia muy lenta. Mostramos que en un caso especial, pero importante, es posible obtener límites significativamente mejores en la tasa de convergencia. Este caso especial es cuando el enorme espacio de estados se puede agregar en un menor número de grupos, en los cuales los estados se comportan de la misma manera (aunque su comportamiento aún puede no ser idéntico). Una cadena de Markov con esta estructura se llama . Esta propiedad permite la de los estados (nodos) en grupos. Nuestra principal contribución es un límite rigurosamente demostrado en la tasa a la que la distribución de estados agregada se acerca a su límite en cadenas de Markov cuasi-lumpables. También demostramos numéricamente que en ciertos casos esto puede conducir de hecho a una forma significativamente acelerada de estimar la medida de subconjuntos. El resultado puede ser una herramienta útil en el análisis de redes complejas, siempre que tengan un agrupamiento que agregue nodos con comportamientos similares (pero no necesariamente idénticos).
Descripción
Consideramos el problema de estimar la medida de subconjuntos en redes muy grandes. Una herramienta fundamental para este propósito es el algoritmo de Monte Carlo de Cadena de Markov (MCMC). Este algoritmo, aunque extremadamente útil en muchos casos, a menudo sufre de la desventaja de una convergencia muy lenta. Mostramos que en un caso especial, pero importante, es posible obtener límites significativamente mejores en la tasa de convergencia. Este caso especial es cuando el enorme espacio de estados se puede agregar en un menor número de grupos, en los cuales los estados se comportan de la misma manera (aunque su comportamiento aún puede no ser idéntico). Una cadena de Markov con esta estructura se llama . Esta propiedad permite la de los estados (nodos) en grupos. Nuestra principal contribución es un límite rigurosamente demostrado en la tasa a la que la distribución de estados agregada se acerca a su límite en cadenas de Markov cuasi-lumpables. También demostramos numéricamente que en ciertos casos esto puede conducir de hecho a una forma significativamente acelerada de estimar la medida de subconjuntos. El resultado puede ser una herramienta útil en el análisis de redes complejas, siempre que tengan un agrupamiento que agregue nodos con comportamientos similares (pero no necesariamente idénticos).