Disparitetsfilteralgoritm för vägt nätverk

Disparitetsfilter är en nätverksreduktionsalgoritm (alias grafsparsifieringsalgoritm) för att extrahera ryggradsstrukturen för oriktat vägt nätverk . Många verkliga nätverk som citeringsnätverk , matnät , flygplatsnätverk uppvisar en kraftig statistisk fördelning av nodernas vikt och styrka . Disparitetsfiltret kan reducera nätverket tillräckligt utan att förstöra nätverkets flerskaliga karaktär. Algoritmen är utvecklad av M. Angeles Serrano, Marian Boguna och Alessandro Vespignani .

Översikt över andra nätverksreduktionsalgoritmer och deras begränsningar

k -kärnnedbrytning

k -kärnupplösning är en algoritm som reducerar en graf till en maximalt sammankopplad subgraf av hörn med minst grad k . Denna algoritm kan endast tillämpas på oviktade grafer.

Minsta spännträd

Ett minimumspännande träd är en trädliknande subgraf av en given graf G , där den behåller alla noder i graf G men minimerar subgrafens totala vikt. Ett minimum spannträd är det billigaste sättet att behålla storleken på en ansluten komponent . Den betydande begränsningen för denna algoritm är att den alltför förenklar nätverkets struktur ( graf ) . Det minsta spännträdet förstör lokala cykler, klustringskoefficienter som vanligtvis finns i verkliga nätverk och anses viktiga vid nätverksmätning.

Global vikttröskel

En viktad graf kan lätt reduceras till en subgraf där någon av kanternas vikt är större än en given tröskel w _c . Denna teknik har använts för att studera motståndet hos näringsvävar och funktionella nätverk som förbinder korrelerade mänskliga hjärnplatser. Nackdelen med denna metod är att den bortser från noder med liten styrka. I verkliga nätverk följer både styrka och viktfördelning i allmänhet tunga svansfördelningar som spänner över flera magnitudsgrader. Genom att tillämpa ett enkelt gränsvärde på vikten tas all information under gränsvärdet bort.

Disparitetsfilteralgoritm

Nollmodellen för normaliserad viktfördelning

Inom nätverksvetenskap definieras styrkan noterad som s _i för en nod i som s _i = Σ _j w _ij , där w _ij är vikten av länken mellan i och j .

För att tillämpa disparitetsfilteralgoritmen utan att förbise noder med låg styrka, definieras en normaliserad vikt p _{ij som} p _ij = w _ij / s _i . I nollmodellen genereras de normaliserade vikterna för en viss nod med grad k så här: k − 1 stift tilldelas slumpmässigt mellan intervallet 0 och 1. Intervallet delas sedan upp i k delintervall. Längden på delintervallet representerar den normaliserade vikten för varje länk i nollmodellen.

I följd, och baserat på nollmodellen, kan vi härleda att den normaliserade viktfördelningen för en nod med grad k följer $\ rho (x)\,dx=(k-1)(1-x)^{k-2}\,dx$ .

Disparitetsfilter

Disparitetsfilteralgoritmen är baserad på p-värdes statistisk signifikanstest av nollmodellen: För en given normaliserad vikt p _{ij ges} p-värdet α _ij för p _ij baserat på nollmodellen av $\alpha _{ij}=1-(k-1)\int _{0}^{p_{ij}}(1 -x)^{k-2}\,dx$ som reducerar till $\alpha _{ij}=(1-p_{ij})^{ k-1}$ . Betydelsen av α _ij är sannolikheten att ha normaliserad vikt större eller lika med p _ij inom ramen för den givna nollmodellen. Genom att sätta en signifikansnivå α (mellan 0 och 1), för varje länk med normaliserad vikt p _ij , om α _ij är större än α , kommer den att filtreras bort. Genom att ändra α kan vi successivt ta bort irrelevanta länkar och på så sätt extrahera det viktade nätverkets ryggradsstruktur effektivt.

Generaliseringar

Pólya filter

Disparitetsfilteralgoritmen har visat sig vara ett speciellt fall av Pólya-filtret (byggt kring det berömda kombinatoriska schemat känt som Pólya-urnan ). Pólya-filtret kan anpassa filtreringsproceduren till nätverkets egen heterogenitet genom att använda en Maximum Likelihood-procedur för att ställa in dess fria parameter ${\displaystyle a} ,$ som representerar styrkan hos den självförstärkande mekanismen som styr det underliggande urnschemat. Givet en signifikansnivå $\alpha$ har Pólya-filtret visat sig producera ryggraden mycket glesare än disparitetsfiltret och ändå kunna behålla de mest framträdande länkarna i systemet.

Se även

externa länkar