Udoskonalenia aproksymacji par do analizy sieci

Rozważając interakcje w sieci, zwykle bardzo trudno jest analitycznie obliczyć dynamikę i stosuje się przybliżenia. Przybliżenia pola średniego zwykle całkowicie ignorują strukturę sieci, a zatem rzadko są dobrym przybliżeniem. Popularnym aproksymacją jest aproksymacja pary, która uwzględnia korelacje nieodłączne między sąsiednimi węzłami (intuicyjnie możemy myśleć o tym jako o typie aproksymacji pola średniego na krawędziach).

Przybliżenie jest dokładne, jeśli bierzemy pod uwagę wykresy Cayleya, i bardzo dobrze, jeśli patrzymy na regularne losowe wykresy. W praktyce zapewnia również dobre przybliżenia dla przypadków, gdy mamy losowy wykres ze średnim stopniem k i wąskim rozkładem stopnia wokół k . Niestety wiele interesujących sieci i interakcji nie jest dobrze modelowanych przez tego rodzaju wykresy. Zazwyczaj są one dobrze modelowane za pomocą wykresów o bardzo różnych rozkładach stopni (na przykład sieci pozbawione skali), ze specyficznymi (i wysokimi) współczynnikami klastrowania lub określoną średnią odległością najkrótszej ścieżki (więcej, patrz Albert i Barabasi 2001 ) .$k$$k$$k$

Czy istnieją udoskonalenia aproksymacji par, które działają dobrze dla tego typu sieci? Czy są dostępne inne przybliżenia analityczne?

Przykład interakcji w sieci

Myślałem, że podam przykład tego, co rozumiem przez interakcje w sieci. Podam stosunkowo ogólny przykład z ewolucyjnej teorii gier.

Możesz myśleć o każdym węźle jako o agencie (zwykle reprezentowanym tylko przez strategię), który gra w pewną ustaloną grę parami z każdym agentem, do którego ma przewagę. Zatem dana sieć z pewnym przypisaniem strategii do każdego węzła powoduje wypłatę dla każdego węzła. Następnie wykorzystujemy te wypłaty i strukturę sieci, aby określić rozkład strategii między węzłami dla następnej iteracji (częstym przykładem może być kopiowanie przez sąsiada największej wypłaty lub jakiegoś wariantu tego prawdopodobieństwa). Pytania, którymi zazwyczaj jesteśmy zainteresowani, odpowiadają znajomości liczby agentów każdej strategii i zmianom w czasie. Często mamy stabilną dystrybucję (którą następnie chcemy poznać lub przybliżoną) lub czasami ograniczamy cykle lub nawet bardziej egzotyczne bestie.

Jeśli wykonamy aproksymację pola średniego w tego rodzaju modelu, użyjemy równania replikatora jako naszej dynamiki, która rażąco ignoruje strukturę sieci i jest dokładna tylko dla kompletnych wykresów. Jeśli użyjemy aproksymacji par (jak Ohtsuki i Nowak 2006 ) otrzymamy nieco inną dynamikę (w rzeczywistości będzie to dynamika replikatora ze zmodyfikowaną macierzą wypłat, gdzie modyfikacja zależy od stopnia wykresu i specyfiki kroku aktualizacji) który dobrze pasuje do symulacji dla losowych wykresów, ale nie dla innych interesujących sieci.

Dla przykładu bardziej fizycznego: zastąp agentów obrotami i wywołaj macierz wypłat interakcją hamiltonian, a następnie ochłodź swój system podczas wykonywania okresowych losowych pomiarów.

Uwagi i powiązane pytania

• Proste uogólnienia aproksymacji par tego rodzaju, które uwzględniają rodzaj aproksymacji pola średniego na potrójnych lub poczwórnych węzłach) są nieporęczne i wciąż nie uwzględniają bardzo różnych rozkładów stopni lub średniej odległości najkrótszej ścieżki.

• Źródła algorytmicznej ewolucyjnej teorii gier

Ogólnie rzecz biorąc, możesz być zainteresowany metodami spektralnymi w teorii grafów, ponieważ są one potężnym narzędziem. Można analizować wartości własne macierzy przyległości wykresu (lub macierzy Laplaciana na wykresie ).

Takie metody uwzględniają nie tylko lokalne właściwości wykresu (np. Rozkład stopni), ale także globalne (np. Łączność, obecność lub brak skrótów). W szczególności widmo jest bezpośrednio związane z liczbą par, trójkątów i najkrótszą ścieżką (patrz drugie odniesienie).

Jako odniesienie (tylko przeglądałem je, ale wyglądają na przydatne):

• S. Boccaletti i in. (Phys Rep 2006), Sieci złożone: Struktura i dynamika (lub tutaj )
• K.-I. Goh et at. (PRE 2001), Widma i wektory własne sieci pozbawionych skali, arXiv: cond-mat / 0103337

Sposób, w jaki formułujesz swoje pytanie, sprawia, że ​​brzmi to tak, jakbyś dbał o dynamikę, ale ponieważ to, czego szukasz, wydaje się rozwiązaniem stanu ustalonego, stany podstawowe wydają się znacznie bardziej produktywną drogą do zejścia.

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

Nie jestem też pewien, czy jest to coś, czego szukasz, czy nie, ale istnieją pewne najnowsze wyniki dotyczące wykonalności sieci pozbawionych skali, pokazujące, że wykazują one dwa przejścia fazowe, które wydaje się, że właśnie zostały zaakceptowane PRL. Przedruk zatytułowany „Wszystkie sieci bez skali są rzadkie” można znaleźć jako arXiv: 1106: 5150 .

Dwie rzeczy, na które możesz chcieć spojrzeć:

Algorytmiczna teoria gier Ch. 7: Gry graficzne

Wahania w grach ewolucyjnych

Pierwszy dotyczy tego, jak znaleźć równowagę w grach lub systemach spinowych, jak opisano. Niektóre meta-strategie przyjęcia strategii (szczególnie ta identyczna z próbkowaniem Gibbsa, która prowadzi do skorelowanych równowag) pozwalają na bardzo ogólne, możliwe do analizy analizy.

Druga próba przewidzenia dużych fluktuacji lub zmiany „norm” w ewolucyjnym modelu teorii gier z wykorzystaniem teorii dużych odchyleń. Podane przykłady są na małą skalę, ale autor stara się uczynić maszynę matematyczną, której używa, tak ogólną i potężną, jak to możliwe, aby mogła mieć zastosowanie w twoim przypadku.