Lorsque l'on considère les interactions sur les réseaux, il est généralement très difficile de calculer la dynamique analytiquement , et des approximations sont utilisées. Les approximations de champ moyen finissent généralement par ignorer complètement la structure du réseau, et sont donc rarement une bonne approximation. Une approximation populaire est l'approximation de paire, qui considère les corrélations inhérentes entre les nœuds adjacents (intuitivement, nous pouvons la considérer comme un type d'approximation de champ moyen sur les bords).
L'approximation est exacte si l'on considère les graphes de Cayley, et très bonne si l'on regarde les graphes aléatoires réguliers. En pratique, il fournit également de bonnes approximations pour les cas où nous avons un graphique aléatoire avec un degré moyen et une distribution étroite du degré autour de . Malheureusement, de nombreux réseaux et interactions qui présentent un intérêt ne sont pas bien modélisés par ce type de graphiques. Ils sont généralement bien modélisés par des graphiques avec des distributions de degrés très différentes (comme les réseaux sans échelle, par exemple), avec des coefficients de regroupement spécifiques (et élevés) , ou une distance moyenne spécifique sur le plus court chemin (pour en savoir plus, voir Albert et Barabasi 2001 ) .
Existe-t-il des améliorations de l'approximation des paires qui fonctionnent bien pour ces types de réseaux? Ou existe-t-il d'autres approximations analytiques disponibles?
Un exemple d'interactions sur les réseaux
J'ai pensé donner un exemple de ce que je veux dire par interactions sur les réseaux. Je vais inclure un exemple relativement général de la théorie des jeux évolutifs.
Vous pouvez considérer chaque nœud comme un agent (généralement représenté uniquement par une stratégie), qui joue un jeu fixe par paire avec l'autre agent avec lequel il a un avantage. Ainsi, un réseau donné avec une certaine affectation de stratégie à chaque nœud produit un gain pour chaque nœud. Nous utilisons ensuite ces gains et la structure du réseau pour déterminer la distribution des stratégies entre les nœuds pour la prochaine itération (un exemple courant pourrait être pour chaque agent de copier le voisin avec le gain le plus élevé, ou une variante probabiliste de cela). Les questions qui nous intéressent généralement correspondent à la connaissance du nombre d'agents de chaque stratégie et comment cela change au fil du temps. Souvent, nous avons une distribution stable (que nous voulons ensuite connaître, ou approximative) ou parfois des cycles limites ou des bêtes encore plus exotiques.
Si nous faisons une approximation de champ moyen sur ce type de modèle, nous utilisons l' équation du réplicateur comme notre dynamique, qui ignore de manière flagrante la structure du réseau et n'est précise que pour des graphiques complets. Si nous utilisons l'approximation des paires (comme Ohtsuki et Nowak 2006 ), nous obtiendrons une dynamique légèrement différente (ce sera en fait une dynamique de réplicateur avec une matrice de gain modifiée, où la modification dépend du degré du graphique et des spécificités de l'étape de mise à jour) qui correspond bien à la simulation pour les graphiques aléatoires, mais pas pour les autres réseaux d'intérêt.
Pour un exemple plus physique comme: remplacez les agents par des spins et appelez la matrice de gain une interaction hamiltonienne, puis refroidissez votre système tout en effectuant des mesures aléatoires périodiques.
Notes et questions connexes
Les généralisations simples d'approximation de paires du type qui considèrent un type d'approximation de champ moyen sur des triplets ou des quadruples de nœuds) sont peu maniables et ne tiennent toujours pas compte de distributions de degrés très différentes ou de la distance moyenne sur le chemin le plus court.
la source
Réponses:
En général, vous pouvez être intéressé par les méthodes spectrales en théorie des graphes, car elles sont un outil puissant. Vous pouvez analyser les valeurs propres de la matrice d'adjacence du graphe (ou de la matrice laplacienne du graphe ).
De telles méthodes prennent non seulement en compte les propriétés locales du graphique (par exemple la distribution des degrés) mais aussi globales (par exemple la connectivité, la présence ou l'absence de raccourcis). En particulier, le spectre est directement lié au nombre de paires, de triangles et au chemin le plus court (voir la deuxième référence).
À titre de référence (je les ai seulement parcourues, mais elles ont l'air utiles):
la source
La façon dont vous formulez votre question donne l'impression que vous vous souciez de la dynamique, mais comme ce que vous recherchez semble être une solution stable, les états fondamentaux semblent être une voie beaucoup plus productive pour descendre.
De plus, je ne sais pas si c'est le genre de chose que vous recherchez ou non, mais il y a des résultats récents sur la réalisabilité des réseaux sans échelle, montrant qu'ils présentent des transitions en deux phases qui semblent avoir été acceptées PRL. Une préimpression intitulée «Tous les réseaux sans échelle sont rares» peut être consultée sous la forme arXiv: 1106: 5150 .
la source
Deux choses que vous voudrez peut-être examiner:
Théorie algorithmique des jeux Ch. 7: Jeux graphiques
Fluctuations dans les jeux évolutionnaires
Le premier explique comment trouver des équilibres dans les jeux ou les systèmes de spin comme vous l'avez décrit. Certaines méta-stratégies d'adoption de stratégies (en particulier celle identique à l'échantillonnage de Gibbs qui conduit à des équilibres corrélés) permettent des analyses très générales et traitables.
La seconde tente de prédire de grandes fluctuations ou des changements de «normes» dans un modèle de théorie des jeux évolutifs utilisant la théorie des grandes déviations. Les exemples abordés sont à petite échelle, mais l'auteur tente de rendre la machinerie mathématique qu'il utilise aussi générale et puissante que possible, afin qu'elle puisse s'appliquer à votre cas.
la source