Maximal-entropi slumpmässig grafmodell

Slumpmässiga grafmodeller för maximal entropi är slumpmässiga grafmodeller som används för att studera komplexa nätverk som omfattas av principen om maximal entropi under en uppsättning strukturella begränsningar, som kan vara globala, distributionsmässiga eller lokala.

Översikt

Vilken slumpmässig grafmodell som helst (vid en fast uppsättning parametervärden) resulterar i en sannolikhetsfördelning på grafer , och de som är maximal entropi inom den betraktade klassen av distributioner har den speciella egenskapen att vara maximalt opartiska nollmodeller för nätverksslutledning (t.ex. biologiskt nätverk slutledning ). Varje modell definierar en familj av sannolikhetsfördelningar på uppsättningen grafer av storlek $n$ (för varje $n>n_{0}$ för några ändliga $n_{0}$ ) , parametriserad av en samling begränsningar på $J$ observerbara $\{Q_{j}(G)\}_{j=1}^{J}$ definieras för varje graf $G$ (såsom fast förväntad medelgrad , gradfördelning av en viss form eller specifik gradsekvens ), framtvingad i graffördelningen tillsammans med entropimaximering med metoden Lagrange-multiplikatorer . Observera att "maximal entropi" i detta sammanhang inte hänvisar till entropin för en enda graf, utan snarare entropin för hela den probabilistiska ensemblen av slumpmässiga grafer.

Flera vanligt studerade slumpmässiga nätverksmodeller är i själva verket maximal entropi, till exempel ER- graferna $G(n,m)$ och $G(n,p)$ (som var och en har en global begränsning för antalet kanter), såväl som konfigurationsmodellen ( CM ). och mjuk konfigurationsmodell (SCM) (som var och en har $n$ lokala begränsningar, en för varje nodvis gradvärde). I de två modellparen som nämns ovan är en viktig skillnad i huruvida begränsningen är skarp (dvs. uppfylld av varje element i uppsättningen av storleks-n {\ $n}$ -grafer med en sannolikhet som inte är noll i ensemblen), eller mjuk (dvs. nöjda i genomsnitt över hela ensemblen). Det tidigare (skarpa) fallet motsvarar en mikrokanonisk ensemble , villkoret för maximal entropi ger alla grafer $G$ som uppfyller $Q_{j}(G)=q_{ j}\forall j$ som equiprobable; det senare (mjuka) fallet är kanoniskt , vilket ger en exponentiell slumpmässig grafmodell (ERGM).

Modell	Begränsningstyp	Begränsningsvariabel	Sannolikhetsfördelning
ER , $G(n,m)$	Skarp, global	Totalt kantantal $\|E(G)\|$	$1/{\binom {\binom {n}{2}}{m}};\ m=\|E(G)\|$
ER , $G(n,p)$	Mjuk, global	Förväntat totalt kantantal $\|E(G)\|$	$p^{\|E(G)\|}(1-p)^{{\binom {n}{2}}-\|E(G)\|}$
Konfigurationsmodell	Skarpt, lokalt	Grad av varje vertex, $\{{\hat {k}}_{j}\}_{j=1}^{n}$	$1/\left\vert \Omega (\{{\hat {k}}_{j}\}_{j=1}^{n})\right\vert ;\Omega (\{k_{j}\}_{j=1}^{n})=\ {g\in {\mathcal {G}}_{n}:k_{j}(g)={\hat {k}}_{j}\forall j\}\subset {\mathcal {G}}_ {n}$
Mjuk konfigurationsmodell	Mjuk, lokal	Förväntad grad av varje vertex, $\{{\hat {k}}_{j}\}_{j=1}^{n}$	$Z^{-1}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}( G)\right];\ -{\frac {\partial \ln Z}{\partial \psi _{j}}}={\hat {k}}_{j}$

Kanonisk ensemble av grafer (allmän ram)

Antag att vi bygger en slumpmässig grafmodell som består av en sannolikhetsfördelning $\mathbb {P} (G)$ på mängden ${\mathcal {G}}_{n}$ av enkla grafer med $n$ hörn. Gibbs -entropin $S[G]$ för denna ensemble kommer att ges av

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

Vi skulle vilja ha ensemble-medelvärdena $\{\langle Q_{j}\rangle \}_{j=1}^{J}$ för observerbara ${\displaystyle \{Q_{j}(G)\}_{j=1}^{J}} ($ såsom genomsnittlig grad , genomsnittlig klustring eller genomsnittlig kortaste väglängd ) för att kunna justeras , så vi lägger $J$ "mjuka" begränsningar på graffördelningen:

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

där $j=1,...,J$ märka begränsningarna. Tillämpning av metoden med Lagrange-multiplikatorer för att bestämma fördelningen $\mathbb {P} (G)$ som maximerar $S[G]$ samtidigt som den uppfyller $\langle Q_{j}\rangle =q_{j}$ , och normaliseringsvillkoret $\sum _{G\in {\mathcal {G}} _{n}}\mathbb {P} (G)=1$ resulterar i följande:

\mathbb {P} (G)={\frac {1}{Z}}\exp \ vänster[-\sum _{j=1}^{J}\psi _{j}Q_{j}(G)\höger],

där $Z$ är en normaliseringskonstant ( partitionsfunktionen ) och $\{\psi _{j}\}_{j=1}^{J}$ är parametrar (Lagrange-multiplikatorer) kopplade till de motsvarande indexerade grafen observerbara, som kan ställas in för att ge grafprover med önskade värden för dessa egenskaper, i genomsnitt; resultatet är en exponentiell familj och kanonisk ensemble ; specifikt ger en ERGM .

Erdős–Rényi-modellen $G(n,m)$

I det kanoniska ramverket ovan infördes begränsningar för ensemble-genomsnittliga kvantiteter $\langle Q_{j}\rangle$ . Även om dessa egenskaper i genomsnitt kommer att anta värden som kan specificeras genom lämplig inställning av ${\displaystyle \{\psi _{j}\}_{j=1}^{J}},$ varje specifik instans $G$ kan ha $Q_{j}(G)\neq q_{j}$ , vilket kan vara oönskat. Istället kan vi ställa ett mycket striktare villkor: varje graf med en sannolikhet som inte är noll måste uppfylla $Q_{j}(G)=q_{j}$ exakt. Under dessa "skarpa" begränsningar bestäms den maximala entropifördelningen. Vi exemplifierar detta med Erdős–Rényi-modellen $G(n,m)$ .

Den skarpa begränsningen i $G(n,m)$ är den för ett fast antal kanter $m$ , det vill säga $|\operatörsnamn {E} (G)|=m$ , för alla grafer $G$ ritade från ensemblen (instansierad med en sannolikhet betecknad $\mathbb {P} _{n,m}(G)$ ). Detta begränsar provutrymmet från ${\mathcal {G}}_{n}$ (alla grafer på $n$ hörn) till delmängden ${\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|\operatörsnamn {E} (g)| =m\}\subset {\mathcal {G}}_{n}$ . Detta är i direkt analogi med den mikrokanoniska ensemblen i klassisk statistisk mekanik , där systemet är begränsat till ett tunt grenrör i fasutrymmet för alla tillstånd av ett visst energivärde .

När vi begränsar vårt provutrymme till ${\mathcal {G}}_{n,m}$ , har vi inga externa begränsningar (förutom normalisering) att uppfylla, och därför väljer vi $\mathbb {P} _{n,m}(G)$ för att maximera $S[G]$ utan att använda Lagrange-multiplikatorer. Det är välkänt att den entropimaximerande fördelningen i frånvaro av externa begränsningar är den enhetliga fördelningen över provutrymmet (se maximal entropi-sannolikhetsfördelning ), från vilken vi får:

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

där det sista uttrycket i termer av binomialkoefficienter är antalet sätt att placera $m$ kanter bland ${\binom {n}{2}}$ möjliga kanter , och därmed är kardinaliteten av ${\mathcal {G}}_{n,m}$ .

Generaliseringar

En mängd ensembler med maximal entropi har studerats på generaliseringar av enkla grafer. Dessa inkluderar till exempel ensembler av enkla komplex och viktade slumpmässiga grafer med en given förväntad gradsekvens

Se även