Mjuk konfigurationsmodell

Inom tillämpad matematik är den mjuka konfigurationsmodellen (SCM) en slumpmässig grafmodell som är föremål för principen om maximal entropi under begränsningar av förväntan på gradsekvensen av samplade grafer . Medan konfigurationsmodellen (CM) enhetligt samplar slumpmässiga grafer av en specifik gradsekvens, behåller SCM endast den specificerade gradsekvensen i genomsnitt över alla nätverksförverkliganden. i denna mening har SCM mycket avslappnade begränsningar i förhållande till de för CM ("mjuka" snarare än "skarpa" begränsningar). SCM för grafer av storlek $n$ har en sannolikhet som inte är noll för att sampla vilken graf som helst med storlek ${\displaystyle n} ,$ medan CM är begränsad till endast grafer som har exakt den föreskrivna anslutningsstrukturen.

Modellformulering

SCM är en statistisk ensemble av slumpmässiga grafer $G$ med $n$ hörn ( ${\displaystyle n=|V(G)|} )$ märkta ${\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)} , som ger$ en sannolikhetsfördelning på ${\mathcal {G}}_{n}$ (uppsättningen grafer av storlek $n$ ). Pålagda för ensemblen är $n$ begränsningar, nämligen att ensemblemedelvärdet av graden $k_{j}$ av vertex $v_{j}$ är lika med ett angivet värde ${\widehat {k}}_{j}$ , för alla $v_{j}\in V(G)$ . Modellen är helt parametriserad av dess storlek $n$ och förväntad gradsekvens $\{{\widehat {k}}_{j}\}_{j=1 }^{n}$ . Dessa begränsningar är både lokala (en begränsning associerad med varje vertex) och mjuka (begränsningar på ensemblens medelvärde av vissa observerbara kvantiteter), och ger således en kanonisk ensemble med ett omfattande antal begränsningar. Villkoren $\langle k_{j}\rangle ={\widehat {k}}_{j}$ åläggs ensemblen med metoden Lagrange-multiplikatorer (se Maximal-entropi slumpmässig grafmodell ).

Härledning av sannolikhetsfördelningen

Sannolikheten $\mathbb {P} _{\text{SCM}}(G)$ för att SCM producerar en graf $G$ bestäms genom att maximera Gibbs-entropin $S[G]$ omfattas av begränsningar $\langle k_{j}\rangle ={\widehat {k}}_{j} ,\ j=1,\ldots ,n$ och normalisering $\sum _{G\in {\mathcal {G}}_{n}}\mathbb { P} _{\text{SCM}}(G)=1$ . Detta motsvarar att optimera Lagrange-funktionen med flera begränsningar nedan:

${\begin{aligned}&{\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)\\[6pt]={}&-\summa _{G\in {\mathcal {G}}_{ n}}\mathbb {P} _{\text{SCM}}(G)\log \mathbb {P} _{\text{SCM}}(G)+\alpha \left(1-\summa _{G \in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\right)+\summa _{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{aligned}}$

där $\alpha$ och ${\displaystyle \{\psi _{j}\}_{j=1}^{n}} är$ n $\displaystyle n +1}$ multiplikatorer som ska fixeras av $n+1$ -begränsningarna (normalisering och den förväntade gradsekvensen). Nollställning av derivatan av ovanstående med avseende på $\mathbb {P} _{\text{SCM}}(G)$ för en godtycklig $G\in { \mathcal {G}}_{n}$ ger

$0={\frac {\partial {\mathcal {L}}\left(\alpha ,\{ \psi _{j}\}_{j=1}^{n}\right)}{\partial \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)\höger],$

konstanten $Z:=e^{\alpha +1}=\summa _{G\in {\mathcal {G}}_{n}}\exp \left[-\summa _{j= 1}^{n}\psi _{j}k_{j}(G)\right]=\prod _{1\leq i<j\leq n}\left(1+e^{-(\psi _ {i}+\psi _{j})}\right)$ är partitionsfunktionen som normaliserar fördelningen; ovanstående exponentiella uttryck gäller för alla ${\displaystyle G\in {\mathcal {G}}_{n}} ,$ och därmed är sannolikhetsfördelningen. Därför har vi en exponentiell familj parametriserad av ${\displaystyle \{\psi _{j}\}_{j=1}^{n}} ,$ som är relaterade till den förväntade gradsekvensen $\{{\widehat {k}}_{j}\}_{j=1}^{n}$ av följande ekvivalenta uttryck:

$\langle k_{q}\rangle =\sum _{G\in {\mathcal {G}}_{n}}k_{q}(G)\mathbb {P} _{\text{SCM} }(G)=-{\frac {\partial \log Z}{\partial \psi _{q}}}=\summa _{j\neq q}{\frac {1}{e^{\psi _ {q}+\psi _{j}}+1}}={\widehat {k}}_{q},\ q=1,\ldots ,n.$