Bei der Betrachtung von Interaktionen in Netzwerken ist es normalerweise sehr schwierig, die Dynamik analytisch zu berechnen , und es werden Näherungen verwendet. Mittelfeldnäherungen ignorieren normalerweise die Netzwerkstruktur vollständig und sind daher selten eine gute Annäherung. Eine beliebte Näherung ist die Paarnäherung, bei der die Korrelationen zwischen benachbarten Knoten berücksichtigt werden (intuitiv können wir sie als eine Art Mittelfeldnäherung an Kanten betrachten).
Die Annäherung ist genau, wenn wir Cayley-Graphen betrachten, und sehr gut, wenn wir reguläre Zufallsgraphen betrachten. In der Praxis liefert es auch gute Annäherungen für Fälle, in denen wir einen Zufallsgraphen mit einem durchschnittlichen Grad k und einer engen Gradverteilung um k haben . Leider sind viele der Netzwerke und Interaktionen, die von Interesse sind, durch diese Art von Diagrammen nicht gut modelliert. Sie werden normalerweise durch Diagramme mit sehr unterschiedlichen Gradverteilungen (wie z. B. skalierungsfreien Netzwerken) mit bestimmten (und hohen) Clusterkoeffizienten oder bestimmten durchschnittlichen Entfernungen auf kürzestem Weg gut modelliert (weitere Informationen finden Sie unter Albert & Barabasi 2001 ). .
Gibt es Verfeinerungen der Paarannäherung, die für diese Arten von Netzwerken gut funktionieren? Oder gibt es andere analytische Näherungen?
Ein Beispiel für Interaktionen in Netzwerken
Ich dachte, ich würde ein Beispiel dafür geben, was ich unter Interaktionen in Netzwerken verstehe. Ich werde ein relativ allgemeines Beispiel aus der evolutionären Spieltheorie aufnehmen.
Sie können sich jeden Knoten als einen Agenten vorstellen (normalerweise nur durch eine Strategie dargestellt), der paarweise ein festes Spiel paarweise mit dem anderen Agenten spielt, für den er einen Vorteil hat. Somit erzeugt ein gegebenes Netzwerk mit einer gewissen Zuordnung der Strategie zu jedem Knoten eine Auszahlung für jeden Knoten. Wir verwenden diese Auszahlungen und die Netzwerkstruktur dann, um die Verteilung der Strategien unter den Knoten für die nächste Iteration zu bestimmen (ein häufiges Beispiel könnte sein, dass jeder Agent den Nachbarn mit der höchsten Auszahlung oder eine probabilistische Variante davon kopiert). Die Fragen, die uns normalerweise interessieren, entsprechen der Kenntnis der Anzahl der Agenten jeder Strategie und wie sich diese im Laufe der Zeit ändern. Oft haben wir eine stabile Verteilung (die wir dann wissen oder annähern wollen) oder manchmal Grenzzyklen oder sogar exotischere Bestien.
Wenn wir für diese Art von Modell eine Mittelfeldnäherung durchführen, verwenden wir die Replikatorgleichung als unsere Dynamik, die die Netzwerkstruktur offensichtlich ignoriert und nur für vollständige Diagramme genau ist. Wenn wir die Paarannäherung verwenden (wie Ohtsuki & Nowak 2006 ), erhalten wir eine geringfügig andere Dynamik (es handelt sich tatsächlich um eine Replikatordynamik mit einer modifizierten Auszahlungsmatrix, wobei die Modifikation vom Grad des Diagramms und den Besonderheiten des Aktualisierungsschritts abhängt). Dies passt gut zur Simulation für zufällige Graphen, jedoch nicht für andere interessierende Netzwerke.
Für ein physikalischeres Beispiel: Ersetzen Sie die Agenten durch Drehungen und nennen Sie die Auszahlungsmatrix einen Interaktions-Hamilton-Operator. Kühlen Sie dann Ihr System ab, während Sie periodische Zufallsmessungen durchführen.
Notizen und verwandte Fragen
Unkomplizierte Verallgemeinerungen der Paarnäherung der Art, die eine Art Mittelfeldnäherung an Dreifach- oder Vierfachknoten berücksichtigen, sind unhandlich und berücksichtigen immer noch keine sehr unterschiedlichen Gradverteilungen oder durchschnittlichen Entfernungen auf kürzestem Weg.
quelle
Antworten:
Im Allgemeinen könnten Sie an spektralen Methoden in der Graphentheorie interessiert sein, da diese ein leistungsfähiges Werkzeug sind. Sie können die Eigenwerte der Adjazenzmatrix des Diagramms (oder der Laplace-Matrix des Diagramms ) analysieren .
Solche Methoden berücksichtigen nicht nur lokale Eigenschaften des Graphen (z. B. Gradverteilung), sondern auch globale (z. B. Konnektivität, Vorhandensein oder Fehlen von Verknüpfungen). Insbesondere steht das Spektrum in direktem Zusammenhang mit der Anzahl der Paare, Dreiecke und dem kürzesten Weg (siehe zweite Referenz).
Als Referenz (ich habe sie nur durchgesehen, aber sie sehen nützlich aus):
quelle
Die Art und Weise, wie Sie Ihre Frage formulieren, klingt so, als ob Sie sich für Dynamik interessieren, aber da das, wonach Sie suchen, eine stationäre Lösung zu sein scheint, scheinen Grundzustände ein viel produktiverer Weg zu sein.
Da Sie über die paarweise Approximation hinausgehen möchten, scheinen Matrixproduktzustände die natürlichste Kandidatentechnik zu sein , was im Moment ein ziemlich heißes Thema für den Umgang mit Quantengrundzuständen ist. Die Art und Weise, wie dieser Ansatz funktioniert, besteht im Wesentlichen darin, maximal verschränkte Paare zwischen Knoten einzuführen und an jedem Knoten einen Projektor einzuführen. Durch Hinzufügen höherdimensionaler Systeme erfassen Sie mehr Funktionen des Diagramms. Ich weiß, dass Ihr Problem wahrscheinlich kein Quantenproblem ist, aber ich verstehe nicht, warum diese Technik immer noch nicht funktionieren sollte. Sie sollten in der Lage sein, die verschränkten Zustände einfach durch zu ersetzen12(|00⟩⟨00|+|11⟩⟨11|).
Ich bin mir auch nicht sicher, ob Sie danach suchen oder nicht, aber es gibt einige aktuelle Ergebnisse zur Realisierbarkeit von skalierungsfreien Netzwerken, die zeigen, dass sie zwei Phasenübergänge aufweisen, die anscheinend gerade akzeptiert wurden PRL. Ein Preprint mit dem Titel "Alle skalierungsfreien Netzwerke sind spärlich" ist unter arXiv: 1106: 5150 zu finden .
quelle
Zwei Dinge, die Sie vielleicht betrachten möchten:
Algorithmische Spieltheorie Kap. 7: Grafikspiele
Schwankungen in evolutionären Spielen
Im ersten Abschnitt wird erläutert, wie Sie Gleichgewichte in Spielen oder Spin-Systemen finden, wie Sie sie beschrieben haben. Bestimmte Metastrategien für die Strategieübernahme (insbesondere die mit Gibbs Sampling identische, die zu korrelierten Gleichgewichten führt) ermöglichen sehr allgemeine, nachvollziehbare Analysen.
Der zweite Versuch, große Schwankungen oder Änderungen der "Normen" in einem evolutionären spieltheoretischen Modell unter Verwendung der Theorie großer Abweichungen vorherzusagen. Die behandelten Beispiele sind kleinräumig, aber der Autor versucht, die von ihm verwendete mathematische Maschinerie so allgemein und leistungsfähig wie möglich zu gestalten, damit sie auf Ihren Fall anwendbar ist.
quelle