Nätverksentropi

Inom nätverksvetenskap är nätverksentropin ett störningsmått som härletts från informationsteori för att beskriva nivån av slumpmässighet och mängden information som kodas i en graf . Det är ett relevant mått för att kvantitativt karakterisera verkliga komplexa nätverk och kan också användas för att kvantifiera nätverkskomplexitet

Formuleringar

Enligt en publikation från Entropy , en tidskrift publicerad av MDPI , finns det flera formuleringar för att mäta nätverksentropin och som regel kräver de alla att en speciell egenskap hos grafen ska fokuseras, såsom närliggande matris, grad sekvens, gradfördelning eller antal bifurkationer, vad som kan leda till entropivärden som inte är oföränderliga för den valda nätverksbeskrivningen.

Grad Distribution Shannon Entropy

Shannon -entropin kan mätas för nätverksgradsannolikhetsfördelningen som ett genomsnittligt mått på nätverkets heterogenitet.

${\mathcal {H}}=-\summa _{k=1}^{N-1}P(k) \ln {P(k)}$

Denna formulering har begränsad användning med avseende på komplexitet, informationsinnehåll, orsakssamband och tidsmässig information. Hur det än må vara, algoritmisk komplexitet har förmågan att karakterisera alla allmänna eller universella egenskaper hos en graf eller ett nätverk och det är bevisat att grafer med låg entropi har låg algoritmisk komplexitet eftersom de statistiska regelbundenheter som finns i en graf är användbara för datorprogram för att återskapa det. Detsamma kan dock inte sägas för nätverk med hög entropi, eftersom dessa kan ha något värde för algoritmisk komplexitet.

Random Walker Shannon Entropy

På grund av gränserna för den tidigare formuleringen är det möjligt att ta ett annat tillvägagångssätt samtidigt som man behåller användningen av den ursprungliga Shannon Entropy-ekvationen.

Betrakta en slumpmässig vandrare som färdas runt grafen och går från en nod $i$ till vilken nod som helst $j$ som gränsar till $i$ med lika stor sannolikhet. Sannolikhetsfördelningen $p_{ij}$ som beskriver beteendet hos denna slumpmässiga vandrare skulle alltså vara

$p_{ij}={\begin{cases}{\frac {1}{k_{i}}},& {\text{if }}A_{ij}=1\\0,&{\text{if }}A_{ij}=0\\\end{cases}}$ ,

där $(A_{ij})$ är grafens närliggande matris och $k_{i}$ är noden $i$ grad.

Från det kan Shannon-entropin från varje nod $\displaystyle {\mathcal {S}}_{i}}$ definieras som

${\mathcal {S}}_{i}=-\sum _{j=1}^{ N-1}p_{ij}\ln {p_{ij}}=\ln {k_{i}}$

och eftersom $max(k_{i})=N-1$ , den normaliserade nodens entropin ${\mathcal {H}}_{i}$ beräknas

${\mathcal {H$

Detta leder till en normaliserad nätverksentropi ${\displaystyle {\mathcal {H}}} ,$ beräknad genom att medelvärdet av den normaliserade nodentropin över hela nätverket

${\mathcal {H}}={\frac {1}{N} }\summa _{i=1}^{N}{\mathcal {H}}_{i}={\frac {1}{N\ln(N-1)}}\summa _{i=1} ^{N}\ln {k_{i}}$

Den normaliserade nätverksentropin är maximal ${\mathcal {H}}=1$ när nätverket är helt anslutet och minskar ju glesare nätverket blir ${\mathcal {H}}=0$ . Lägg märke till att isolerade noder $k_{i}=0$ inte har sin sannolikhet $p_{ij}$ definierad och därför inte beaktas vid mätning av nätverksentropin. Denna formulering av nätverksentropi har låg känslighet för hubbar på grund av den logaritmiska faktorn och är mer meningsfull för viktade nätverk., vilket i slutändan gör det svårt att differentiera skalfria nätverk med enbart detta mått.

Random Walker Kolmogorov–Sinai entropi

Begränsningarna för Shannon-entropin för random walker kan övervinnas genom att anpassa den för att använda en Kolmogorov-Sinai-entropi . I detta sammanhang är nätverksentropi entropin av en stokastisk matris som $\displaystyle (A_{ij})}$ associerad med grafens närliggande matris ( och den slumpmässiga vandraren Shannon-entropin kallas nätverkets dynamiska entropi . Från det, låt $\lambda$ vara det dominerande egenvärdet för $(A_{ij})$ . Det är bevisat att $\ln \lambda$ uppfyller en variationsprincip som är ekvivalent med den dynamiska entropin för oviktade nätverk, dvs. närliggande matris består uteslutande av booleska värden. Därför definieras den topologiska entropin som

${\mathcal {H}}=\ln \lambda$

Denna formulering är viktig för studiet av nätverkets robusthet , dvs nätverkets förmåga att motstå slumpmässiga strukturella förändringar. Robusthet är faktiskt svårt att mäta numeriskt medan entropin lätt kan beräknas för vilket nätverk som helst, det som är speciellt viktigt i samband med icke-stationära nätverk. Den entropiska fluktuationssatsen visar att denna entropi är positivt korrelerad till robusthet och därmed en större okänslighet hos en observerbar för dynamiska eller strukturella störningar i nätverket. Dessutom är egenvärdena i sig relaterade till mångfalden av interna vägar, vilket leder till en negativ korrelation mellan den topologiska entropin och den kortaste genomsnittliga väglängden.

Annat än det är Kolmogorov-entropin relaterad till Ricci-krökningen av nätverket, ett mått som har använts för att skilja stadier av cancer från gensamuttrycksnätverk, samt för att ge kännetecken för finansiella krascher från aktiekorrelationsnätverk

Von Neumann entropi

Von Neumann-entropin är förlängningen av den klassiska Gibbs-entropin i ett kvantsammanhang. Denna entropi är konstruerad från en densitetsmatris $\rho$ : historiskt sett har den första föreslagna kandidaten för en sådan densitetsmatris varit ett uttryck för den laplaciska matrisen L som är associerad med nätverket. Den genomsnittliga von Neumann-entropin för en ensemble beräknas som:

$${S}_{VN}=-\langle \mathrm {Tr} \rho \log(\rho )\rangle$$

För slumpmässig nätverksensemble G $\displaystyle G(N,p)}$$S_{VN}$ relationen mellan och $S$ icke-monoton när den genomsnittliga anslutningsmöjligheten $p(N-1)$ varieras.

För kanoniska maktlagsnätverk ensembler är de två entropierna linjärt relaterade.

$${S}_{VN}=\eta {S/N}+\beta$$

Nätverk med givna förväntade gradsekvenser tyder på att heterogenitet i den förväntade gradfördelningen innebär en ekvivalens mellan ett kvantum och en klassisk beskrivning av nätverk, vilket motsvarar von Neumann- och Shannon-entropin.

Denna definition av Von Neumann-entropin kan också utvidgas till flerskiktsnätverk med tensoriellt tillvägagångssätt och har använts framgångsrikt för att reducera deras dimensionalitet ur ett strukturellt perspektiv.

Det har dock visat sig att denna definition av entropi inte tillfredsställer egenskapen subadditivitet (se Von Neumann entropins subadditivitet ), som förväntas hålla teoretiskt. En mer grundad definition, som uppfyller denna grundläggande egenskap, har introducerats av De Domenico och Biamonte som ett kvantliknande Gibbs-tillstånd

$$\rho (\beta )={\frac {e^{-\beta L}}{Z(\beta )}}$$

var

$$Z(\beta )=Tr[e^{-\beta L}]$$

är en normaliserande faktor som spelar rollen som partitionsfunktionen, och $\beta$ är en avstämbar parameter som tillåter multi-upplösningsanalys. Om $\beta$ tolkas som en tidsparameter, är denna densitetsmatris formellt proportionell mot utbredningen av en diffusiv process på toppen av nätverket.

Denna funktion har använts för att bygga en statistisk fältteori om komplex informationsdynamik, där densitetsmatrisen kan tolkas i termer av superpositionen för strömoperatörer vars åtgärd är att aktivera informationsflöden mellan noder. Ramverket har framgångsrikt använts för att analysera protein-protein-interaktionsnätverken av virus-mänskliga interaktomer, inklusive SARS- CoV-2, för att reda ut de systemiska egenskaperna hos infektion av de senare i mikroskopisk, mesoskopisk och makroskopisk skala, såväl som för att bedöma nodernas betydelse för att integrera informationsflöden inom nätverket och vilken roll de spelar för nätverkets robusthet.

Detta tillvägagångssätt har generaliserats för att hantera andra typer av dynamik, såsom slumpmässiga promenader, på toppen av flerskiktsnätverk, vilket ger ett effektivt sätt att minska dimensionaliteten hos sådana system utan att ändra deras struktur. Med användning av både klassiska och med maximal entropi har motsvarande densitetsmatriser använts för att koda nätverkstillstånden i den mänskliga hjärnan och för att bedöma, i flera skalor, connectomes informationskapacitet vid olika stadier av demens.

Maximal entropiprincip

Maximal entropiprincipen är en variationsprincip som anger att sannolikhetsfördelningen som bäst representerar det aktuella tillståndet i ett system är den som maximerar Shannon-entropin. Detta koncept kan användas för att generera en ensemble av slumpmässiga grafer med givna strukturella egenskaper härledda från den maximala entropimetoden som i sin tur beskriver den mest sannolika nätverkskonfigurationen: principen om maximal entropi tillåter maximalt opartisk information när den saknar fullständig kunskap (mikroskopisk konfigurationen är inte tillgänglig, t.ex.: vi känner inte till närliggande matris). Å andra sidan fungerar denna ensemble som en nollmodell när den faktiska mikroskopiska konfigurationen av nätverket är känd, vilket gör det möjligt att bedöma betydelsen av empiriska mönster som finns i nätverket

Komplexa nätverksensembler

Det är möjligt att utöka nätverksentropiformuleringarna för att istället mäta ensembleentropin. Låt $\Omega$ vara en ensemble av alla grafer $G$ med samma antal $N$ av noder och typ av länkar, $P(G)$ är definieras som förekomstsannolikheten för en graf $G\in \Omega$ . Från principen om maximal entropi är det önskvärt att uppnå $P(G)$ så att det maximerar Shannon-entropin

${\mathcal {H}}=-\summa _{G\in \Omega }P(G)\ln P(G)$

Dessutom ska begränsningar införas för att dra slutsatser. Mjuka begränsningar (begränsningar satta över hela ensemblen $\Omega$ ) kommer att leda till den kanoniska ensemblen medan hårda begränsningar (begränsningar satta över varje graf ${\displaystyle G} )$ kommer att definiera den mikrokanoniska ensemblen . I slutändan leder dessa ensembler till modeller som kan validera en rad nätverksmönster och till och med rekonstruera grafer från begränsad kunskap, vilket visar att maximala entropimodeller baserade på lokala begränsningar kan kvantifiera relevansen av en uppsättning observerade egenskaper och extrahera meningsfull information från enorma stora dataströmmar i realtid och högdimensionell bullrig data.

Se även Entropi av nätverksensembler .