Existe un método trivial para simular una caminata aleatoria a través de un gráfico exponiendo una matriz de adyacencia estocástica, pero el problema se vuelve más difícil si solicita que la caminata aleatoria se evite por sí misma. En otras palabras, el proceso debe atravesar el gráfico utilizando rutas, como una infección o algo así.
Si las probabilidades de borde son grandes, existe un algoritmo simple de Monte Carlo: en cada prueba, simplemente elimina cada borde con probabilidad 1 - p e , calcula los componentes conectados del nuevo gráfico e incrementa una matriz de conteo por matrices de 1s para cada componente contactado. Se divide por el número de pruebas al final.
¿Alguien sabe algún algoritmo para hacer este cálculo cuando las probabilidades son bastante pequeñas?
Si el gráfico no está demasiado conectado, puede encontrar algunos conjuntos de corte mínimos y contar con inclusión-exclusión, pero este enfoque es doblemente exponencial en el tamaño de los conjuntos de corte. También hay varias optimizaciones para casos específicos de alta conectividad, como tratar todas las subgrafías de camarillas por separado a través del cálculo obvio. ¿Alguna idea más general?
fuente
Respuestas:
No estoy seguro de si estoy interpretando su pregunta correctamente, pero me parece que está preguntando no sobre simular caminatas aleatorias autoevitantes, sino sobre enumerar caminatas aleatorias autoevitantes. Digo esto porque hablas de exponencializar una matriz de adyacencia, que te dará una enumeración (ponderada) de caminatas aleatorias.
No estoy seguro de si hay mucha literatura sobre la enumeración de caminatas de autoevaluación en gráficos generales; Creo que la mayor parte de la atención se ha centrado en las caminatas de autoevaluación en celosías en el espacio euclidiano, y en eso se basan mis comentarios a continuación. Sospecho que muchas de las ideas se transferirán a gráficos generales.
La herramienta clásica para reducir la mano de obra involucrada en enumerar exactamente las caminatas que se evitan por sí mismas es la expansión del encaje. Debería poder localizar fácilmente la literatura relevante con esa palabra clave. Sin embargo, para los gráficos altamente conectados, supongo que la idea de expansión de encaje no ayudará demasiado (pero tal vez nada ayudará mucho en ese caso).
Si está satisfecho con la enumeración aproximada , existen algunas opciones. Consulte el documento de EJJ van Rensburg 2009 sobre "Enumeración aproximada de caminatas que se evitan a sí mismo" para una encuesta. Ver también "Algoritmos de autoevaluación para caminatas de autoevaluación" de Randall y Sinclair (2000).
fuente