Cuando se consideran las interacciones en las redes, generalmente es muy difícil calcular la dinámica analíticamente , y se emplean aproximaciones. Las aproximaciones de campo medio generalmente terminan ignorando la estructura de la red por completo, por lo que rara vez son una buena aproximación. Una aproximación popular es la aproximación de pares, que considera las correlaciones inherentes entre los nodos adyacentes (intuitivamente podemos considerarla como un tipo de aproximación de campo medio en los bordes).
La aproximación es exacta si estamos considerando gráficos de Cayley, y muy buena si estamos mirando gráficos aleatorios regulares. En la práctica, también proporciona buenas aproximaciones para casos en los que tenemos un gráfico aleatorio con un grado medio y una distribución estrecha del grado alrededor de . Desafortunadamente, muchas de las redes e interacciones que son de interés, no están bien modeladas por este tipo de gráficos. Por lo general, están bien modelados por gráficos con distribuciones de grados muy diferentes (como redes sin escala, por ejemplo), con coeficientes de agrupación específicos (y altos) , o una distancia promedio específica de la ruta más corta (para más información, vea Albert y Barabasi 2001 ) .k k
¿Existen refinamientos de aproximación de pares que funcionen bien para este tipo de redes? ¿O hay otras aproximaciones analíticas disponibles?
Un ejemplo de interacciones en redes.
Pensé que daría un ejemplo de lo que quiero decir con interacciones en redes. Incluiré un ejemplo relativamente general de la teoría de juegos evolutivos.
Puedes pensar en cada nodo como un agente (generalmente representado solo por una estrategia), que juega un juego fijo en parejas con otro agente al que tiene una ventaja. Por lo tanto, una red dada con una asignación de estrategia a cada nodo produce una recompensa por cada nodo. Luego usamos estos pagos y la estructura de la red para determinar la distribución de estrategias entre los nodos para la próxima iteración (un ejemplo común podría ser que cada agente copie al vecino con el pago más alto, o alguna variante probabilística de esto). Las preguntas que generalmente nos interesan corresponden a conocer el número de agentes de cada estrategia y cómo eso cambia las horas extras. A menudo tenemos una distribución estable (que luego queremos saber o aproximar) o, a veces, ciclos límite o bestias aún más exóticas.
Si hacemos una aproximación de campo medio en este tipo de modelo, usamos la ecuación del replicador como nuestra dinámica, que ignora descaradamente la estructura de la red y solo es precisa para gráficos completos. Si usamos la aproximación de pares (como Ohtsuki y Nowak 2006 ) obtendremos dinámicas ligeramente diferentes (en realidad serán dinámicas replicadoras con una matriz de pago modificada, donde la modificación depende del grado del gráfico y los detalles del paso de actualización) que coincide bien con la simulación para gráficos aleatorios, pero no para otras redes de interés.
Para un ejemplo más físico: reemplace los agentes por giros y llame a la matriz de pagos una interacción hamiltoniana, luego enfríe su sistema mientras realiza mediciones aleatorias periódicas.
Notas y preguntas relacionadas
Las generalizaciones directas de aproximación de pares del tipo que considera un tipo de aproximación de campo medio en triples o cuádruples de nodos) son difíciles de manejar y aún no tienen en cuenta distribuciones de grados muy diferentes o la distancia promedio de la ruta más corta.
fuente
Respuestas:
En general, puede interesarle los métodos espectrales en la teoría de grafos, ya que son una herramienta poderosa. Puede analizar los valores propios de la matriz de adyacencia del gráfico (o de la matriz laplaciana del gráfico ).
Dichos métodos no solo tienen en cuenta las propiedades locales del gráfico (por ejemplo, distribución de grados) sino también globales (por ejemplo, conectividad, presencia o ausencia de accesos directos). En particular, el espectro está directamente relacionado con el número de pares, triángulos y con la ruta más corta (ver la segunda referencia).
Como referencia (solo los hojeé, pero parecen útiles):
fuente
La forma en que formula su pregunta hace que parezca que le importa la dinámica, pero dado que lo que está buscando parece ser una solución de estado estable, los estados fundamentales parecen ser una ruta mucho más productiva para bajar.
Además, no estoy seguro de si este es el tipo de cosa que está buscando o no, pero hay algunos resultados recientes sobre la posibilidad de redes sin escala, que muestran que exhiben transiciones de dos fases que parecen haber sido aceptadas. PRL. Un preprint titulado "Todas las redes sin escala son escasas" se puede encontrar como arXiv: 1106: 5150 .
fuente
Dos cosas que tal vez quieras mirar:
Teoría de juego algorítmico Ch. 7: juegos gráficos
Fluctuaciones en juegos evolutivos
El primero trata sobre cómo encontrar equilibrios en juegos o sistemas de giros como describiste. Ciertas metaestrategias para la adopción de estrategias (específicamente la idéntica a Gibbs Sampling que conduce a equilibrios correlacionados) permiten análisis manejables muy generales.
El segundo intento de predecir grandes fluctuaciones o cambios en las "normas" en un modelo de teoría de juegos evolutivos utilizando la teoría de grandes desviaciones. Los ejemplos abordados son a pequeña escala, pero el autor intenta hacer que la maquinaria matemática que utiliza sea lo más general y poderosa posible, por lo que puede ser aplicable a su caso.
fuente