Gradbevarande randomisering

Gradbevarande randomisering är en teknik som används inom nätverksvetenskap som syftar till att bedöma om variationer som observeras i en given graf helt enkelt kan vara en artefakt av grafens inneboende strukturella egenskaper snarare än egenskaper som är unika för noderna, i ett observerat nätverk.

Bakgrund

Katalogiserades så tidigt som 1996, den enklaste implementeringen av gradbevarande randomisering bygger på en Monte Carlo -algoritm som omarrangerar eller "kopplar om" nätverket slumpmässigt så att, med ett tillräckligt antal omledningar, nätverkets gradfördelning är identisk med den initiala graden distribution av nätverket, även om nätverkets topologiska struktur har blivit helt skild från det ursprungliga nätverket.

En demonstration av en enda iteration av algoritmen för gradbevarande randomisering.

Gradbevarande randomisering, även om den har många olika former, tar vanligtvis formen av ett relativt enkelt tillvägagångssätt: för alla nätverk som består av $N$ -noder med $E$ -kanter, välj två dyadiskt knutna noder. För vart och ett av dessa dyadiska par, byt kanterna så att de nya dyadiska paren inte matchar. Efter ett tillräckligt antal av dessa felmatchningar förlorar nätverket i allt högre grad sin ursprungliga observerade topografi.

Som är vanligt med algoritmer baserade på Markov-kedjor är antalet iterationer, eller individuella omledningar, som måste ske på en given graf så att grafen är tillräckligt slumpmässig och distinkt från den ursprungliga grafen okänt, även om Espinoza hävdar att ett säkert minimigränsvärde är $Q*E$ , där $Q$ "är minst 100" (Espinoza). Andra har lämnat input för detta problem, inklusive en författare som säger att ett säkert minimum istället kan vara minst ${\frac {E}{2}}*ln(1/ \epsilon )$ , där epsilon ligger i ett intervall mellan $10^{-6}$ och $10^{-7}$ , även om det korrekta talet i slutändan inte är känt för närvarande.

Används

Det finns flera fall där publicerad forskning uttryckligen har använt gradbevarande randomisering för att analysera nätverksegenskaper. Dekker använde omkoppling för att mer exakt modellera observerade sociala nätverk genom att lägga till en sekundär variabel, ${\displaystyle \pi } ,$ som introducerar en höggradig anknytningsbias. Liu et al. har dessutom använt gradbevarande randomisering för att hävda att kontrollcentraliteten, ett mått de identifierar, ändrar lite jämfört med kontrollcentraliteten för en Erdős–Rényi-modell som innehåller samma antal $N$ -noder i sina simuleringar - Liu et al. har också använt gradbevarande randomiseringsmodeller i efterföljande arbete med att utforska nätverksstyrbarhet .

Dessutom har en del arbete gjorts för att undersöka hur gradbevarande randomisering kan användas för att hantera överväganden om anonymitet i nätverksdataforskning, vilket har visat sig vara en anledning till oro i Social Network Analysis, som i fallet med en studie av Lewis et al. I slutändan har det arbete som utförts av Ying och Wu, med utgångspunkt från en grund av Degree Preserving Randomization, och sedan vidarebefordrat flera modifieringar, visat måttliga framsteg när det gäller att skydda anonymitet utan att kompromissa med integriteten hos det underliggande verktyget för det observerade nätverket.

Dessutom liknar metoden till sin natur de brett använda exponentiella slumpmässiga grafmodellerna som populariserats inom samhällsvetenskapen, och faktiskt de olika formerna av modellering av nätverk mot observerade nätverk för att identifiera och teoretisera om skillnaderna uttryckta i verkliga nätverk. Viktigt är att Degree Preserving Randomization ger en enkel algoritmisk design för dem som är bekanta med programmering för att applicera en modell på ett tillgängligt observerat nätverk.

Exempel

Vad som följer är ett litet exempel som visar hur man kan tillämpa gradbevarande randomisering på ett observerat nätverk i ett försök att förstå nätverket mot annars slumpmässig variation samtidigt som nätverkets gradfördelningsaspekt bibehålls. Föreningen Internetforskare har en Listserv som utgör majoriteten av diskussionstrådarna kring deras arbete. På den lägger medlemmarna upp uppdateringar om sin egen forskning, kommande konferenser, utlysningar och engagerar också varandra i sakliga diskussioner inom sitt område. Dessa e-postmeddelanden kan i sin tur utgöra en riktad och tidsmässig nätverksgraf, där noder är individuella e-postkonton som tillhör Listserv och edges är fall där en e-postadress svarar på en annan e-postadress på Listserv.

Resultat från examensbevarande randomiseringsförsök.

I detta observerade nätverk är egenskaperna för Listserv relativt enkla att beräkna - för nätverket med 3 235 individuella e-postkonton och totalt 9 824 utbyten är den observerade ömsesidigheten för nätverket cirka 0,074, och [Genomsnittlig väglängd| medelvärde ] väglängd] är cirka 4,46. Kan man komma fram till dessa värden helt enkelt genom arten av nätverkets inneboende struktur?

Om man tillämpar ${\displaystyle {\frac {E}{2}}*ln(1/\epsilon )}-$ regeln, skulle detta nätverk kräva cirka 67 861 individuella omledningar för att bygga en sannolikt tillräckligt slumpmässig gradbevarad graf. Om vi konstruerar många slumpmässiga, gradbevarande grafer från den verkliga grafen, kan vi sedan skapa ett sannolikhetsutrymme för egenskaper, såsom ömsesidighet och genomsnittlig väglängd, och bedöma i vilken grad nätverket kunde ha uttryckt dessa egenskaper slumpmässigt. 534 nätverk genererades med hjälp av gradbevarande randomisering. Eftersom både ömsesidighet och genomsnittlig väglängd i denna graf är normalfördelade, och eftersom standardavvikelsen för både ömsesidighet och genomsnittlig väglängd är alldeles för snäv för att inkludera det observerade fallet, kan vi rimligen anta att detta nätverk uttrycker egenskaper som inte är slumpmässigt (och därmed öppen för ytterligare teori och modellering).

externa länkar

Dataset tillhandahålls till exempel