Refinamentos da aproximação de pares para análise de rede

Ao considerar as interações nas redes, geralmente é muito difícil calcular a dinâmica analiticamente , e as aproximações são empregadas. As aproximações de campo médio geralmente acabam ignorando completamente a estrutura da rede e, portanto, raramente são uma boa aproximação. Uma aproximação popular é a aproximação de pares, que considera as correlações inerentes entre os nós adjacentes (intuitivamente, podemos pensar nisso como um tipo de aproximação de campo médio nas arestas).

A aproximação é exata se estivermos considerando gráficos de Cayley, e muito boa se estivermos olhando para gráficos aleatórios regulares. Na prática, também fornece boas aproximações para casos em que temos um gráfico aleatório com grau médio k e uma distribuição restrita de grau em torno de k . Infelizmente, muitas das redes e interações que são de interesse não são bem modeladas por esse tipo de gráfico. Eles geralmente são bem modelados por gráficos com distribuições de graus muito diferentes (como redes sem escala, por exemplo), com coeficientes de cluster específicos (e altos) ou distância média do caminho mais curto (para mais informações, ver Albert & Barabasi 2001 ). .$k$$k$$k$

Existem refinamentos na aproximação de pares que funcionam bem para esses tipos de redes? Ou existem outras aproximações analíticas disponíveis?

Um exemplo de interações em redes

Eu pensei em dar um exemplo do que quero dizer com interações nas redes. Vou incluir um exemplo relativamente geral da teoria dos jogos evolucionários.

Você pode pensar em cada nó como um agente (geralmente representado apenas por uma estratégia), que joga algum jogo fixo em pares aos outros agentes aos quais tem uma vantagem. Assim, uma determinada rede com alguma atribuição de estratégia para cada nó produz uma recompensa para cada nó. Em seguida, usamos esses payoffs e a estrutura de rede para determinar a distribuição de estratégias entre os nós para a próxima iteração (Um exemplo comum pode ser para cada agente copiar o vizinho com o payoff mais alto ou alguma variante probabilística). As perguntas em que geralmente estamos interessados ​​correspondem a conhecer o número de agentes de cada estratégia e como isso muda com o tempo. Freqüentemente, temos uma distribuição estável (que queremos saber ou aproximar) ou, às vezes, ciclos-limite ou animais ainda mais exóticos.

Se fizermos uma aproximação do campo médio nesse tipo de modelo, usaremos a equação do replicador como dinâmica, que ignora flagrantemente a estrutura da rede e é precisa apenas para gráficos completos. Se usarmos a aproximação de pares (como Ohtsuki & Nowak 2006 ), obteremos uma dinâmica ligeiramente diferente (na verdade, será uma dinâmica de replicador com uma matriz de payoff modificada, onde a modificação depende do grau do gráfico e das especificidades da etapa de atualização) que corresponde bem à simulação para gráficos aleatórios, mas não para outras redes de interesse.

Para um exemplo mais físico: substitua os agentes por rotações e chame a matriz de payoff de interação hamiltoniana, depois refresque seu sistema enquanto realiza medições aleatórias periódicas.

Notas e perguntas relacionadas

• Generalizações diretas de aproximação de pares do tipo que considera um tipo de aproximação de campo médio em triplos ou quádruplos de nós) são difíceis de manejar e ainda não levam em conta distribuições de graus muito diferentes ou distância média do caminho mais curto.

• Fontes para a teoria algorítmica evolutiva dos jogos

Em geral, você pode estar interessado em métodos espectrais na teoria dos grafos, pois eles são uma ferramenta poderosa. Você pode analisar os autovalores da matriz de adjacência do gráfico (ou da matriz laplaciana do gráfico ).

Esses métodos não apenas levam em consideração as propriedades locais do gráfico (por exemplo, distribuição de graus), mas também globais (por exemplo, conectividade, presença ou ausência de atalhos). Em particular, o espectro está diretamente relacionado ao número de pares, triângulos e ao caminho mais curto (consulte a segunda referência).

Como referência (eu só passei por eles, mas eles parecem úteis):

• S. Boccaletti et al. (Phys Rep 2006), Redes complexas: Estrutura e dinâmica (ou aqui )
• K.-I. Goh et at. (PRE 2001), espectros e autovetores de redes sem escala, arXiv: cond-mat / 0103337

A maneira como você formula sua pergunta faz parecer que você se preocupa com a dinâmica, mas como o que você procura parece ser uma solução em estado estacionário, os estados fundamentais parecem ser uma rota muito mais produtiva a seguir.

$\frac{1}{2}(|00\rangle \langle 00| + |11\rangle \langle 11|).$

Além disso, não tenho certeza se esse é o tipo de coisa que você está procurando ou não, mas há alguns resultados recentes sobre a realização de redes sem escala, mostrando que elas exibem transições de duas fases que parecem ter sido aceitas apenas para PRL. Uma pré-impressão intitulada "Todas as redes sem escala são escassas" pode ser encontrada como arXiv: 1106: 5150 .

Duas coisas que você pode querer considerar:

Teoria Algorítmica dos Jogos Ch. 7: Jogos Gráficos

Flutuações nos Jogos Evolucionários

A primeira aborda como encontrar equilíbrios em jogos ou sistemas de giro, como você descreveu. Certas meta-estratégias para adoção de estratégias (especificamente a idêntica à Gibbs Sampling que leva a um equilíbrio correlacionado) permitem análises muito gerais e tratáveis.

A segunda tenta prever grandes flutuações ou mudanças nas "normas" em um modelo evolucionário da teoria dos jogos usando a teoria dos grandes desvios. Os exemplos abordados são de pequena escala, mas o autor tenta fazer com que o maquinário matemático que ele usa seja o mais genérico e poderoso possível, para que possa ser aplicável ao seu caso.