Měkký konfigurační model - Soft configuration model

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

V aplikované matematice je model měkké konfigurace (SCM) je náhodný graf model podléhá princip maximální entropie pod omezeními na očekávání z sekvence stupňů vzorku grafy.^[1] Vzhledem k tomu, že konfigurační model (CM) rovnoměrně vzorkuje náhodné grafy konkrétní sekvence stupňů, SCM zachovává pouze zadanou sekvenci stupňů průměrně ve všech realizacích sítě; v tomto smyslu má SCM velmi uvolněná omezení ve srovnání s omezeními CM („měkká“ spíše než „ostrá“ omezení^[2]). SCM pro grafy velikosti ${ displaystyle n}$ má nenulovou pravděpodobnost vzorkování libovolného grafu velikosti ${ displaystyle n}$, zatímco CM je omezen pouze na grafy, které mají přesně předepsanou strukturu připojení.

Modelová formulace

SCM je a statistický soubor náhodných grafů ${ displaystyle G}$ mít ${ displaystyle n}$ vrcholy (${ displaystyle n = | V (G) |}$) označené ${ displaystyle {v_ {j} } _ {j = 1} ^ {n} = V (G)}$, vyrábějící a rozdělení pravděpodobnosti na ${ displaystyle { mathcal {G}} _ {n}}$ (množina grafů velikosti ${ displaystyle n}$). Uloženy souboru jsou ${ displaystyle n}$ omezení, zejména že průměr souboru z stupeň ${ displaystyle k_ {j}}$ vrcholu ${ displaystyle v_ {j}}$ se rovná určené hodnotě ${ displaystyle { widehat {k}} _ {j}}$, pro všechny ${ displaystyle v_ {j} v V (G)}$. Model je plně parametrizováno svou velikostí ${ displaystyle n}$ a očekávaný sled stupňů ${ displaystyle {{ widehat {k}} _ {j} } _ {j = 1} ^ {n}}$. Tato omezení jsou jak místní (jedno omezení spojené s každým vrcholem), tak měkká (omezení průměru souboru určitých pozorovatelných veličin), a tak poskytují kanonický soubor s rozsáhlý počet omezení.^[2] Podmínky ${ displaystyle langle k_ {j} rangle = { widehat {k}} _ {j}}$ jsou uloženy souboru metoda Lagrangeových multiplikátorů (vidět Maximum-entropický model náhodného grafu ).

Odvození rozdělení pravděpodobnosti

Pravděpodobnost ${ displaystyle mathbb {P} _ { text {SCM}} (G)}$ SCM vytváří graf ${ displaystyle G}$ je určena maximalizací Gibbsova entropie ${ displaystyle S [G]}$ podléhá omezením ${ displaystyle langle k_ {j} rangle = { widehat {k}} _ {j}, j = 1, ldots, n}$ a normalizace ${ displaystyle sum _ {G v { mathcal {G}} _ {n}} mathbb {P} _ { text {SCM}} (G) = 1}$. To činí optimalizace multi-omezení Lagrangeova funkce níže:

${ displaystyle { begin {aligned} & { mathcal {L}} left ( alpha, { psi _ {j} } _ {j = 1} ^ {n} right) [6 bodů ] = {} & - sum _ {G in { mathcal {G}} _ {n}} mathbb {P} _ { text {SCM}} (G) log mathbb {P} _ { text {SCM}} (G) + alpha left (1- sum _ {G in { mathcal {G}} _ {n}} mathbb {P} _ { text {SCM}} ( G) right) + sum _ {j = 1} ^ {n} psi _ {j} left ({ widehat {k}} _ {j} - sum _ {G in { mathcal { G}} _ {n}} mathbb {P} _ { text {SCM}} (G) k_ {j} (G) right), end {zarovnáno}}}$

kde ${ displaystyle alpha}$ a ${ displaystyle { psi _ {j} } _ {j = 1} ^ {n}}$ jsou ${ displaystyle n + 1}$ multiplikátory, které stanoví ${ displaystyle n + 1}$ omezení (normalizace a očekávaný sled stupňů). Nastavení na nulu derivace výše s ohledem na ${ displaystyle mathbb {P} _ { text {SCM}} (G)}$ pro svévolné ${ displaystyle G v { mathcal {G}} _ {n}}$ výnosy

${ displaystyle 0 = { frac { částečné { mathcal {L}} vlevo ( alpha, { psi _ {j} } _ {j = 1} ^ {n} vpravo)} { částečný mathbb {P} _ { text {SCM}} (G)}} = - log mathbb {P} _ { text {SCM}} (G) -1- alpha - sum _ {j = 1} ^ {n} psi _ {j} k_ {j} (G) Rightarrow mathbb {P} _ { text {SCM}} (G) = { frac {1} {Z} } exp left [- sum _ {j = 1} ^ {n} psi _ {j} k_ {j} (G) right],}$

konstanta ${ displaystyle Z: = e ^ { alpha +1} = součet _ {G v { mathcal {G}} _ {n}} exp left [- sum _ {j = 1} ^ { n} psi _ {j} k_ {j} (G) vpravo] = prod _ {1 leq i$^[3] být funkce oddílu normalizace distribuce; výše uvedený exponenciální výraz platí pro všechny ${ displaystyle G v { mathcal {G}} _ {n}}$, a tedy i rozdělení pravděpodobnosti. Proto máme exponenciální rodina parametrizováno pomocí ${ displaystyle { psi _ {j} } _ {j = 1} ^ {n}}$, které souvisejí s očekávanou posloupností stupňů ${ displaystyle {{ widehat {k}} _ {j} } _ {j = 1} ^ {n}}$ následujícími ekvivalentními výrazy:

${ displaystyle langle k_ {q} rangle = součet _ {G v { mathcal {G}} _ {n}} k_ {q} (G) mathbb {P} _ { text {SCM} } (G) = - { frac { částečné log Z} { částečné psi _ {q}}} = součet _ {j neq q} { frac {1} {e ^ { psi _ {q} + psi _ {j}} + 1}} = { widehat {k}} _ {q}, q = 1, ldots, n.}$

Reference