Model losowego wykresu o maksymalnej entropii - Maximum-entropy random graph model

Nauka o sieci
Teoria
Wykres Złożona sieć Zakażenie Mały świat Bez kamienia Struktura wspólnotowa Przesiąkanie Ewolucja Sterowalność Rysowanie wykresów Kapitał społeczny Analiza linków Optymalizacja Wzajemność Zamknięcie Homofilia Przechodniość Preferencyjne przywiązanie Teoria równowagi Efekt sieci Wpływ społeczny
Typy sieci
Informacyjne (informatyczne) Telekomunikacja Transport Społeczny Współpraca naukowa Biologiczny Sztuczny neuron Współzależny Semantyczny Przestrzenny Zależność Pływ na chipie
Wykresy
funkcje Klika Składnik Skaleczenie Cykl Struktura danych Brzeg Pętla Sąsiedztwo Ścieżka Wierzchołek Lista  / macierz sąsiedztwa Lista  / macierz zachorowań Rodzaje Dwustronny Kompletny Skierowany Hyper Wielo Losowy Ważona
Metryka Algorytmy
Centralność Stopień Między Bliskość PageRank Motyw Grupowanie Dystrybucja stopni Asortyment Dystans Modułowość Wydajność
Modele
Topologia Losowy wykres Erdős – Rényi Barabási – Albert Model fitness Watts – Strogatz Wykładniczy losowy (ERGM) Losowo geometryczne (RGG) Hiperboliczna (HGN) Hierarchiczne Blok stochastyczny Maksymalna entropia Konfiguracja miękka Benchmark LFR Dynamika Sieć boolowska na podstawie agenta Epidemia / SIR
Listy Kategorie
Tematy Oprogramowanie Naukowcy sieci Kategoria: Teoria sieci Kategoria: Teoria grafów
v t mi

Losowe modele grafów o maksymalnej entropii są losowymi modelami grafów używanymi do badania złożonych sieci podlegających zasadzie maksymalnej entropii w ramach zestawu ograniczeń strukturalnych, które mogą być globalne, dystrybucyjne lub lokalne.

Przegląd

Wszelkie przypadkowy wzór wykresu (przy stałym zestawem wartości parametrów) daje w wyniku rozkładu prawdopodobieństwa na wykresach , a te, które są maksymalna entropia wewnątrz badanym klasy rozkładów mają szczególną właściwość bycia maksymalnie bezstronne modele zerowe dla wnioskowania sieci (np sieć biologiczny wnioskowanie ). Każdy model definiuje rodzinę rozkładów prawdopodobieństwa na zbiorze wykresów o wielkości (dla każdego dla jakiejś skończonej ), sparametryzowanych przez zbiór ograniczeń na obserwablach zdefiniowanych dla każdego wykresu (takich jak ustalony oczekiwany średni stopień , rozkład stopni w określonej postaci, lub sekwencja stopni ), wymuszona w rozkładzie grafowym wraz z maksymalizacją entropii metodą mnożników Lagrange'a . Zauważ, że w tym kontekście „maksymalna entropia” nie odnosi się do entropii pojedynczego wykresu , ale raczej do entropii całego probabilistycznego zbioru losowych grafów. ${\ displaystyle n}$${\ displaystyle n> n_ {0}}$${\ displaystyle n_ {0}}$${\ displaystyle J}$${\ Displaystyle \ {Q_ {j} (G) \} _ {j = 1} ^ {J}}$${\ displaystyle G}$

Kilka powszechnie badanych losowych modeli sieci to w rzeczywistości maksymalna entropia, na przykład wykresy ER i (z których każdy ma jedno globalne ograniczenie liczby krawędzi), a także model konfiguracji (CM). i miękki model konfiguracji (SCM) (z których każdy ma lokalne ograniczenia, po jednym dla każdego węzłowego stopnia-wartości). W obu wspomnianych wyżej parach modeli istotne rozróżnienie dotyczy tego, czy ograniczenie jest ostre (tj. Spełniane przez każdy element zbioru wykresów rozmiarów z niezerowym prawdopodobieństwem w zespole), czy miękkie (tj. Spełnione średnio w całym ensemble). Pierwszy (ostry) przypadek odpowiada zespołowi mikrokanonicznemu , warunkowi maksymalnej entropii dającej wszystkie wykresy spełniające jako równoważne; ten drugi (miękki) przypadek jest kanoniczny , tworząc wykładniczy model wykresu losowego (ERGM). ${\ Displaystyle G (n, m)}$${\ Displaystyle G (n, p)}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle Q_ {j} (G) = q_ {j} \ forall j}$

Model	Typ ograniczenia	Zmienna ograniczenia	Rozkład prawdopodobieństwa
ER ,${\ Displaystyle G (n, m)}$	Ostry, globalny	Całkowita liczba krawędzi ${\ displaystyle | E (G) |}$	${\ Displaystyle 1 / {\ binom {\ binom {n} {2}} {m.}}; \ m = | E (G) |}$
ER ,${\ Displaystyle G (n, p)}$	Miękkie, globalne	Oczekiwana łączna liczba krawędzi ${\ displaystyle | E (G) |}$	${\ Displaystyle p ^ {| E (G) |} (1-p) ^ {{\ binom {n} {2}} - | E (G) |}}$
Model konfiguracji	Ostry, lokalny	Stopień każdego wierzchołka, ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$	${\ Displaystyle 1 / \ lewo \ vert \ Omega (\ {{\ kapelusz {k}} _ {j} \} _ {j = 1} ^ {n}) \ prawo \ vert; \ Omega (\ {k_ { j} \} _ {j = 1} ^ {n}) = \ {g \ in {\ mathcal {G}} _ {n}: k_ {j} (g) = {\ hat {k}} _ { j} \ forall j \} \ subset {\ mathcal {G}} _ {n}}$
Model konfiguracji miękkiej	Miękkie, lokalne	Oczekiwany stopień każdego wierzchołka, ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$	${\ Displaystyle Z ^ {- 1} \ exp \ lewo [- \ suma _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ prawo]; \ - {\ Frac { \ Part \ ln Z} {\ Partial \ psi _ {j}}} = {\ hat {k}} _ {j}}$

Kanoniczny zbiór wykresów (ramy ogólne)

Załóżmy, że budujemy losowy modelu diagram składający się z rozkładem prawdopodobieństwa na zbiorze z prostych wykresów z wierzchołków. Gibbs entropia tego zespołu zostanie podana przez ${\ Displaystyle \ mathbb {P} (G)}$${\ displaystyle {\ mathcal {G}} _ {n}}$${\ displaystyle n}$ ${\ Displaystyle S [G]}$

${\ Displaystyle S [G] = - \ suma _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} (G) \ log \ mathbb {P} (G).}$

Chcielibyśmy, aby wartości obserwowalne uśrednione w zespole (takie jak średni stopień , średnie grupowanie lub średnia najkrótsza długość ścieżki ) były dostrajalne, więc nakładamy „miękkie” ograniczenia na rozkład wykresu: ${\ displaystyle \ {\ langle Q_ {j} \ rangle \} _ {j = 1} ^ {J}}$${\ Displaystyle \ {Q_ {j} (G) \} _ {j = 1} ^ {J}}$${\ displaystyle J}$

${\ displaystyle \ langle Q_ {j} \ rangle = \ suma _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} (G) Q_ {j} (G) = q_ {j },}$

gdzie oznacz ograniczenia. Zastosowanie metody mnożników Lagrange'a do wyznaczenia rozkładu maksymalizującego przy spełnieniu warunku normalizacji daje następujące wyniki: ${\ Displaystyle j = 1, ..., J}$${\ Displaystyle \ mathbb {P} (G)}$${\ Displaystyle S [G]}$${\ displaystyle \ langle Q_ {j} \ rangle = q_ {j}}$${\ Displaystyle \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} (G) = 1}$

${\ Displaystyle \ mathbb {P} (G) = {\ Frac {1} {Z}} \ exp \ lewo [- \ suma _ {j = 1} ^ {J} \ psi _ {j} Q_ {j} (G) \ right],}$

gdzie jest stałą normalizującą ( funkcja podziału ) i są parametrami (mnożnikami Lagrange'a) sprzężonymi z odpowiednio indeksowanymi obserwowalnymi wykresami, które można dostroić, aby uzyskać średnio próbki wykresu o pożądanych wartościach tych właściwości; wynikiem jest wykładnicza rodzina i zespół kanoniczny ; konkretnie dając ERGM . ${\ displaystyle Z}$${\ Displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {J}}$

Model Erdősa – Rényiego ${\ Displaystyle G (n, m)}$

W powyższym układzie kanonicznym ograniczenia zostały nałożone na wartości uśrednione w zespole . Chociaż te właściwości będą średnio przyjmować wartości określone przez odpowiednie ustawienie , może to mieć każdy konkretny przypadek , co może być niepożądane. Zamiast tego możemy narzucić znacznie bardziej rygorystyczny warunek: każdy wykres z niezerowym prawdopodobieństwem musi dokładnie spełniać . Pod tymi „ostrymi” ograniczeniami wyznaczany jest rozkład maksymalnej entropii. Przykładem tego jest model Erdősa – Rényiego . ${\ displaystyle \ langle Q_ {j} \ rangle}$${\ Displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {J}}$${\ displaystyle G}$${\ Displaystyle Q_ {j} (G) \ neq q_ {j}}$${\ Displaystyle Q_ {j} (G) = q_ {j}}$${\ Displaystyle G (n, m)}$

Ostre ograniczenie polega na ustalonej liczbie krawędzi , to znaczy na wszystkich wykresach narysowanych ze zbioru (utworzonych z oznaczonym prawdopodobieństwem ). To ogranicza przestrzeń próbkowania od (wszystkie wykresy na wierzchołkach) do podzbioru . Jest to bezpośrednia analogia do zespołu mikrokanonicznego w klasycznej mechanice statystycznej , w którym system jest ograniczony do cienkiej rozmaitości w przestrzeni fazowej wszystkich stanów o określonej wartości energii . ${\ Displaystyle G (n, m)}$ ${\ displaystyle m}$${\ displaystyle | \ operatorname {E} (G) | = m}$${\ displaystyle G}$${\ Displaystyle \ mathbb {P} _ {n, m.} (G)}$${\ displaystyle {\ mathcal {G}} _ {n}}$${\ displaystyle n}$${\ Displaystyle {\ mathcal {G}} _ {n, m} = \ {g \ in {\ mathcal {G}} _ {n}; | \ operatorname {E} (g) | = m \} \ podzbiór {\ mathcal {G}} _ {n}}$

Po ograniczeniu naszej przestrzeni próbkowania do , nie mamy żadnych zewnętrznych ograniczeń (poza normalizacją) do spełnienia, dlatego wybierzemy maksymalizację bez korzystania z mnożników Lagrange'a. Powszechnie wiadomo, że rozkład maksymalizujący entropię przy braku ograniczeń zewnętrznych jest równomiernym rozkładem w przestrzeni próbki (patrz rozkład prawdopodobieństwa maksymalnej entropii ), z którego otrzymujemy: ${\ displaystyle {\ mathcal {G}} _ {n, m.}}$${\ Displaystyle \ mathbb {P} _ {n, m.} (G)}$${\ Displaystyle S [G]}$

${\ Displaystyle \ mathbb {P} _ {n, m} (G) = {\ Frac {1} {| {\ mathcal {G}} _ {n, m} |}} = {\ binom {\ binom { n} {2}} {m}} ^ {- 1},}$

gdzie ostatni wyraz w kategoriach Symbol Newtona jest wiele sposobów na miejsce krawędziach wśród możliwych krawędzi , a więc jest to liczność od . ${\ displaystyle m}$${\ displaystyle {\ binom {n} {2}}}$${\ displaystyle {\ mathcal {G}} _ {n, m.}}$

Uogólnienia

Badano różne zespoły maksymalnej entropii na uogólnieniach prostych wykresów. Należą do nich na przykład zespoły uproszczonych kompleksów i ważone losowe wykresy z zadaną sekwencją oczekiwanego stopnia

Zobacz też

• Zasada maksymalnej entropii
• Maksymalny rozkład prawdopodobieństwa entropii
• Metoda mnożników Lagrange'a
• Model zerowy
• Losowy wykres
• Wykładniczy model wykresu losowego
• Zespół kanoniczny
• Zespół mikrokanoniczny

Bibliografia