I denna artikel introducerar vi nätverkets histogram: en statistisk sammanfattning av nätverksinteraktioner, som ska användas som ett verktyg för undersökande dataanalys. Ett nätverkshistogram erhålls genom att montera en stokastisk blockmodell till en enda observation av en nätverksdatauppsättning. Block av kanter spelar rollen av histogram bins, och gemenskap storlekar som av histogram bandbredder eller bin storlekar. Precis som standardhistogram möjliggör olika bandbredder, kan olika blockmodelluppskattningar betraktas som giltiga representationer av en underliggande sannolikhetsmodell, med förbehåll för bandbreddsbegränsningar. Här tillhandahåller vi metoder för automatisk bandbreddsval, genom vilket nätverkets histogram approximerar den genereringsmekanism som ger upphov till utbytbara slumpmässiga grafer. Detta gör blockmodellen till en universell nätverksrepresentation för omärkta grafer. Med denna insikt diskuterar vi tolkningen av nätverksgrupper mot bakgrund av att många olika samhällsuppdrag alla kan ge en lika giltig representation av ett sådant nätverk. För att visa den fidelityversus-tolkbarhet kompromiss som ingår i beaktandet av olika antal och storlekar av samhällen, analyserar vi två offentligt tillgängliga nätverkpolitiska webbloggar och studentvänskap-och diskutera hur man tolkar nätverket histogram när ytterligare information om nod och kantmärkning är närvarande. Nyckelord: gemenskapsdetektering, utbytbara slumpvisa grafer, grafoner, icke-parametrisk statistik, statistisk nätverksanalys, stokastiska blockmodeller Syftet med denna artikel är att införa nätverkets histogram-en icke-parametrisk statistisk sammanfattning som erhålls genom att montera en stokastisk blockmodell till en enda observation av ett nätverksdataset. En viktig punkt i vår konstruktion är att det inte är nödvändigt att anta de data som ska ha genererats av en blockmodell. Detta är avgörande, eftersom nätverk är ett allmänt sätt att beskriva relationer mellan objekt. Eftersom n objekt under studie, totalt n 2 parvisa relationer är möjliga. När endast en liten del av dessa relationer är närvarande-som ofta är fallet i modern högdimensionell dataanalys över vetenskapliga områden-en nätverksrepresentation förenklar vår förståelse av denna beroendestruktur. En grundläggande karakterisering av ett nätverk kommer genom identifiering av gemenskapsstruktur [1], motsvarande grupper av noder som uppvisar liknande konnektivitetsmönster. Den kanoniska statistiska modellen i denna inställning är den stokastiska blockmodellen [2]: det visar sig att sannolikheten för en kant mellan två nätverksnoder endast beror på de communitygrupperingar som dessa noder hör till. Att gruppera noder på detta sätt tjänar som en naturlig form av dimensionalitetsminskning: när n blir stort kan vi inte behålla en godtyckligt komplex syn på alla möjliga parvisa relationer. Beskriva hur hela uppsättningen av n objekt samverkar sedan reduceras till att förstå interaktioner i k n samhällen. Att studera egenskaperna hos monterade blockmodeller är därför viktigt [3, 4]. Trots blockmodellens popularitet och dess tydliga nytta har forskare observerat att den ofta inte beskriver all den struktur som finns i ett nätverk [5, 6, 7, 8]. Eftersom ett nät blir större är det inte längre rimligt att anta att en majoritet av dess struktur kan förklaras av en blockmodell med ett fast antal block. Förlängningar av blockmodellen har fokuserat på att fånga upp ytterligare variationer, till exempel genom blandat samhällsmedlemskap [5] och gradkorrigering [6, 9]. Men den enklaste och mest naturliga metoden för att utvidga den beskrivande av blockmodellen är att lägga till block, så att k växer med n. Eftersom fler och fler block är monterade, förväntar vi oss en ökande grad av struktur i data som ska förklaras. De naturliga frågorna att ställa då är många: Vad händer när vi passar fler block till en godtycklig nätverksdatauppsättning, om den sanna datagenererande mekanismen inte är en blockmodell? I vilken takt bör vi öka antalet block som används, beroende på variabiliteten i nätet? Vi tar upp dessa och andra frågor i den här artikeln. Vi kommer att fastställa hur dimensionen k i den monterade blockmodellen ska tillåtas öka med nätverkets storlek n. Denna ökning kommer att dikteras av en avvägning mellan nätets gleshet och dess heterogenitet eller smidighet. Om man antar att en k-community blockmodell är den faktiska datagenererande mekanismen, då teorin har redan utvecklats som tillåter k att växa med n [10, 11, 12], och metoder har föreslagits för att välja antalet block baserat på data [13, 14]. Allmän teori för det fall när blockmodellen endast approximerar den observerade nätverksstrukturen är nascent, med [15] behandla fallet med täta bipartitgrafer med ett fast antal block, och [16] fastställa de första sådana resultat för fastställande av relevans här. 1 Från stokastiska nätverk till histogram Vi kodar förhållandet mellan n objekt med n 2 binära slumpvariabler. Var och en av dessa variabler anger förekomsten eller frånvaron av en kant mellan två noder, och kan samlas in i en n × n adjacensmatris A, sådan att A ij = 1 om noderna i och j är anslutna, och A ij = 0 annars, med 2 A ii = 0. Detta ger vad som kallas en enkel slumpmässig graf. Modeller för omärkta grafer är starkt relaterade till det statistiska begreppet utbytbarhet, ett grundläggande begrepp som beskriver slumpmässiga variabler vars beställning är utan information. För att relatera till utbytbara variabler vädjar vi till Aldous-Hoover theorem [3], och modellera vårt nätverk hierarkiskt med hjälp av tre komponenter: 1. En fast, symmetrisk funktion f (x, y) benämnd grafon [18], som beter sig som en sannolikhetstäthetsfunktion för 0 < x, y < 1; 2. För varje n, ett slumpmässigt urval av n enhetliga slumpvariabler { och 1,. ., N } som kommer att tjäna till att indexera grafon f (x, y); och 3. För varje n, en deterministisk skalning konstant ρ n > 0, ange den förväntade fraktionen av kanter För varje n, är vår enkla stokastiska nätverksmodell då för statistisk identififiability av ρ n vi antar På detta sätt vi modellera nätverksstrukturen själv-snarare än den särskilda ordning där nätverkets noder är arrangerade i A. Som ett exempel, Bild Vi ser från denna generativa mekanism att varje (symmetrisk) omarrangemang av x-och y-axes av f kommer att leda till samma sannolikhetsfördelning på omärkta grafer, och i själva verket en grafon beskriver en hel ekvivalens klass av funktioner. Vi antar att minst en medlem av denna ekvivalens klass är Hölder kontinuerlig, som vi kallar f utan förlust av generalitet; att f avgränsas bort från 0 och ρ n f avgränsas bort från 1; och att sekvensen ρ n är monoton icke-ökande och sönderfaller långsammare än n −1 log 3 n, så att den genomsnittliga nätgraden växer snabbare än log 3 n. För att sammanfatta nätverket vill vi därför uppskatta grafon f (x, y), upp till omarrangering av dess axlar. Genom inspektion, och så vi kan uppskatta ρ n via prov proportion uppskattningen Med tanke på en enda adjakensmatris A av storlek n × n, kommer vi att uppskatta f (x, y) (upp till omarrangemang av dess axlar) med hjälp av en stokastisk blockmodell med en enda, förspecificerad gemenskap storlek h, för att ge ett nätverk histogram. Att välja bandbredd h motsvarar att välja ett visst antal samhällen som motsvarar antalet bins i en vanlig histograminställning. För att definiera nätverkets histogram skriver vi först det totala antalet nätverksnoder n i termer av heltalen h, k och r som n = hk + r, där k = n/h är det totala antalet samhällen; h är motsvarande bandbredd, från 2 till n; och r = n mod h är en resterande term mellan 0 och h − 1. För att samla ihop noderna i vårt nätverk som ska ligga i samma grupp, introducerar vi en gemenskap medlemskap vektor z av längd n. Alla komponenter i z kommer att ta värden i {1,..., k}, och kommer att dela samma värden när noder tilldelas samma gemenskap. Den största utmaningen i att bilda ett nätverk histogram ligger i att uppskatta gemenskapens uppdrag vektor z från A. För detta ändamål, för varje n, låt uppsättningen Z k  till {1,.., k} n innehålla alla gemenskapens tilldelning vektorer z som respekterar den givna formen av n = hk + r. Således Z k består av alla vektorer z med h komponenter lika med vart och ett av heltalen från 1 till k − 1 (upp till ommärkning), och h + r komponenter lika med k (igen, upp till ommärkning). På detta sätt indexerar Z k alla möjliga histogramarrangemang av nätverk noder i k − 1 samhällen av lika storlek h, plus en ytterligare gemenskap av storlek h + r. Många sätt att uppskatta z från en enda observerad adjakensmatris A har utforskats i litteraturen. I huvudsak noder som uppvisar liknande konnektivitetsmönster kommer sannolikt att grupperas tillsammans (en idé som kan utnyttjas direkt om flera observationer av samma nätverk finns tillgängliga; se [19] ). Vi kan formalisera detta begrepp genom metoden för maximal sannolikhet, genom att uppskatta att = argmax där för alla 1 ≤ a, b ≤ k vi definierar histogram bin höjder Varje bin höjd på ab är andelen framgångar (kanter närvarande) i histogrammet bin motsvarar ett block av Bernoulli prövningar, med gruppering av noder i samhällen som bestäms av den objektiva funktionen i (4). Eftersom A är symmetriskt har vi ab = och ba. Kombination (3) och (5), vi får vårt nätverk histogram: medρ + n den generaliserade inversen avρ n. 2 Universalitet blockmodell approximation För att förstå prestanda blockmodell approximation, måste vi jämföra med f på ett sätt som är invariant till alla symmetriska omarrangemang av axlarna i f. Vi kommer att basera vår jämförelse på graf-teoretiska begreppet skäravstånd, som i matematisk terminologi definierar ett kompakt metriska utrymme på grafoner [18]. Precis som vår uppfattning om omärkta grafer behandlar två adjakensmatriser som samma om en kan erhållas genom att symmetriskt permutera raderna och kolumnerna i den andra, kommer vi att jämföra två grafoner via en invertibel, symmetrisk omläggning av x- och y-axlarna som relaterar den ena grafonen till den andra. Vi kallar M uppsättningen av alla sådana omläggningar-formellt, det är uppsättningen av alla åtgärder-bevarande bijects av formen I [16] vi formulerade konvergensgrader där det resulterande felet mellan f och f krymper till noll som n → ❌ enligt antagandena ovan. Här vi anser att menar integrerad kvadrat fel (MISE), typiskt används i standard histogram teori (se, t.ex., [20] ), och ta sin största lägre gräns över alla möjliga omgrupperingar σ  på M: 5 Denna definition faktorer ut den okända beställningen av data A inducerade av { ska 1,. .,  till n } i modellen för (1), redovisning av det faktum att A kan representera en omärkt graf. Utseendet av σ kan till en början verka kontraintuitivt, men dess introduktion är nödvändig när vi använder (1) för att modell A. I motsats till optimeringen av (7) över alla σ  på M, som är rent begreppsmässigt, resulterar vektorn z från algoritmisk optimering av (4) givet en observerad adjakensmatris A, och bestämmer vilka poster av A som är genomsnittliga för att uppskatta f (x, y). Att använda en enda bandbredd h till formf (x, y; h) i (7) representerar ett konceptuellt paradigmskifte bort från standardanvändningen av den stokastiska blockmodellen. I stället för att representera samhällsstrukturen kan en blockmodell användas som en universell mekanism för att representera ett godtyckligt omärkt nätverk. I praktiken, naturligtvis, kan vi mycket väl ha information som innebär vissa märkningar eller beställningar av nätverksnoder. Antagandet om utbytbarhet modellerar vår okunnighet om denna information som en baslinje, precis som vi kan välja att samla en Euclidean dataset utan att ta hänsyn till eventuella åtföljande etiketter. Således kräver vi vårt felmått för att respektera denna okunnighet, även om vi senare väljer att tolka ett monterat histogram i ljuset av nodetiketter (som man kan göra med euklideiska datakluster, och som vi ska göra nedan). Målet i skapandet av utbytbara nätverk är därför inte längre att upptäcka latent gemenskap struktur, utan snarare helt enkelt att gruppera ihop noder vars mönster av interaktioner är liknande. På så sätt har tolkningen av de grupper som monterats ändrats. Istället för att avslöja verkliga underliggande samhällen som kan ha gett upphov till data, våra block nu ungefär den generativa processen, upp till en upplösning som valts av användaren-nämligen bandbredden, h. Detta kan relateras till tidigare förståelse av felbeteendet när data genereras av en blockmodell, både i regimer av ρ n som motsvarar växande grader [11] samt även glesare dem [21]. Vi visar sedan hur den idealiska eller orakelmärkningsinformationen, om den skulle finnas tillgänglig, skulle ge den optimala bandbreddsparametern h för varje givet nätverkshistogram. Denna orakle information uppstår från latent slumpvariabler {. 1,. ..,  på n } finns i den generativa modellen av (1). I denna inställning, i stället för att montera block av olika storlekar på nätverket, att tolkas som gemenskap struktur, vi förlitar oss på det faktum att den enklaste typen av blockmodell kommer att räcka, med endast en enda inställning parameter h. Förekomsten av en smidig begränsning objektet-namely grafon f (x, y)-implies att en enda gemenskap storlek eller bandbredd kommer att ge en adekvat sammanfattning av hela nätverket. För att välja h, använder vi därför begreppet ett nätverk oracle. Som i standard statistiska inställningar [20], ger oraklet information som normalt inte är tillgänglig, vilket tjänar till att begränsa resultatet av någon datadriven skattning förfarande. Oraklet uppskattningen för varje histogram bin höjd tar samma form som (5), men använder en unik (nästan säkert) etiketteringz beräknas från latent slumpmässig vektor  på. Denna märkning ges byz i = min (i) −1 /h, k, där (i) −1 är rangen, från minsta till största, av ith elementet av  på. Således, 6 z order element av den oobserverade vektorn, sortera indexen för data enligt denna beställning, och sedan grupperar dessa index i uppsättningar av storlek h, med en ytterligare uppsättning av storlek h + r. Med oraklet märkningz, kan vi definiera grafon oracle estimator från block medelvärden på * ab enligt ten Comparing (8) med dess motsvarighet i (6), ser vi att oraklet tjänar till att ersätta estimatorer av (3) och (4) med deras ideala mängder. Oraklets estimator är alltså baserad på en förkunskap om gleshetsparametern ρ n och den latenta vektorn  på förhand. I detta avseende visar det den bästa prestanda som kan uppnås för en fast bandbredd h, genom att ge kunskap om den skalning och beställning som krävs för att estimatorn ska bli en linjär funktion av data. 3 Bestämma histogrammet bandbredd Genom att använda nätverket oracle, kan vi avgöra vilka prestandagränser som är möjliga, och i sin tur härleda en tumregel för att välja bandbredd h. Vi antar här att f är differentiable, notera att detta resultat sträcker sig till Hölder kontinuerliga funktioner, som visas i bilaga A. Theorem 1 (Network histogram oracle bandbredd val). Anta att h växer långsammare än n, och att grafon f (x, y) är differentiable, med en gradient magnitud avgränsad av M. Sedan som n växer oraklet medelvärde integrerad kvadrat fel uppfyller gränsen Den högra sidan av detta uttryck minimeras genom att ställa h = h * : wherce MISE f * utvärderas vid h * sönderfaller med hastigheten 1/ n 2 ρ n : Bevis. Vi utvärderar (7) medf som är lika med tof * som definieras i (8), och med σ(x) som är lika med x för att erhålla en övre gräns på felkriteriet MISE f *. Denna 7 ger partisk-varians sönderdelning med b den domän för integration som motsvarar blocket ab. Nu letf ab =  och ab -1 ab f (x, y) dx dy vara det genomsnittliga värdet av f över ab, och f 2 ab det genomsnittliga värdet f 2. Genom att använda den förmodade smidigheten av f på ett sätt som kvantifieras av Proposition 1 i bilaga A, ersätter vi Var. * ab och E. * ab för att erhålla med O(h/n) termen på grund av grupperingen av storlek h + r. Använda (2) Att kombinera dessa förenklingar ger det angivna uttrycket. Detta teorem informerar valet av ett nätverk histogram bandbredd h. Det kvantifierar hur orakel integrerad genomsnittliga kvadrat fel beror på smidigheten i grafon f, i förhållande till storleken och sparty av den observerade adjacency 8 matris A. Teorem sönderdela detta fel i tre bidrag: utjämning partisk, som skalar som M 2 (h/n) 2; upplösning partisk, som skalar som M 2 /n; och varians bidrag, som skalar som omvänt av de effektiva graderna av frihet h 2 ρ n i varje bin. Som visas i [16], säkerställa att h 2 ρ n växer snabbare än log 3 n kommer att möjliggöra konsekvent uppskattning av grafon när z uppskattas enligt (4); detta står för den ytterligare varians som är involverad i uppskattningen z i non-orcle inställning. Teorem 1 gör det sedan möjligt för oss att välja en bandbredd h som respekterar nätverkets globala egenskaper. Om vi skulle veta ρ n och M, Då teorem ger direkt för en orakel val av bandbredd h * enligt (9). Från detta uttryck ser vi att för fallet med ett tätt nätverk, med ρ n  på 1, oraklet valet av bandbredd h * skalor som ε n. Mer allmänt, Vi observerar att när glesheten i nätverket ökar, h * måste också öka, medan som lutningen magnituden av grafon ökar, h * måste minska. Om f inte är differential men fortfarande Hölder kontinuerlig, kommer Hölder exponenten visas i Theorem uttryck, vilket leder till en mindre bandbredd för en given n och ρ n. Slutligen, Theorem 1 ger en övre gräns på orakel medelvärde integrerad kvadrat fel när nätverket histogram bandbredd är inställd på h *. Denna gräns avslöjar den bästa möjliga uppskattning prestanda vi kan uppnå för givna värden av n, ρ n, och M. Teorem 1 är viktigt för vår teoretiska förståelse av bandbredd urvalsproblem, eftersom det visar avvägningar mellan gleshet, jämnhet och provstorlek. Det tyder på att h bör växa i en takt som är proportionell mot ρ −1/4 n ε n, med ρ n uppskattas via (3) och med en konstant proportionalitet beroende på kvadratstorleken M 2 i grafongradienten. För att uppskatta M 2 från A, kommer vi att bilda en enkel endimensionell approximation av grafon f med hjälp av vektor d av sorterade grader. Detta ger en icke-parametrisk estimator för vad som kallas den kanoniska versionen av 1 0 f (x, y) dy [3]. När jämnheten i denna kanoniska marginal är likvärdig med den för f, Då detta förfarande ger en lämplig uppskattning M 2 enligt stegen nedan. I vissa fall kan dock marginalen vara smidigare än f; till exempel, låt B(x) betecknar fördelningsfunktionen för en Beta(a, b) slumpmässig variabel, och anta f (x, y) B −1 (x)B −1 (y) + B −1 (1‐x)B −1 (1−y). Då marginalen är konstant, men motsvarande M 2 (och faktiskt Hölder regelbundenhet f ) beror på a och b. För att fortsätta, anta att raderna och kolumnen i A har beställts på nytt så att d i = j =i A ij ökar med i. Om man räknar med de provade elementen f ( till i,  till j ) av grafonen i en n × n matris F under samma omordning, får vi i analogi med (6) en rank-one uppskattning av den provade grafon a Uppskattning av lutningen för det beställda d över index n/2 ± c ε n för något val av c; normalt är c = 4 lämpligt. Behandla de beställda posterna i d nära n/2 som en uppsättning observationer, passa en linje med lutning m och snap b med hjälp av ekvationssystemet Genom metoden för minst kvadrater, ger detta uppskattningar m och b. 3. Vad är det som händer? Definiera den vektor-värderade funktionen av första skillnader som leder till följande gradient uppskattning: Via  påf 2, Vi uppskattar den genomsnittliga kvadratstorleken på f : 4. Substitution M 2 in (9), vi får bandbredd uppskattning Utrustad med denna tumregel för att välja bandbredd h, kan vi nu beräkna nätverket histogramf x, y; h *. Programvara för dataanalys för att beräkna nätverkets histogram finns på webbplatsen https://github.com/p-wolfe/network-histogram-kod. För att visa nyttan av nätverkets histogram analyserar vi först en välstuderad datauppsättning av politiska webbloggar som beskrivs i [17] och illustreras i Bild. 1................................................................ Denna datauppsättning samlades in för att kvantifiera graden av interaktion mellan liberala och konservativa bloggar runt tiden för det amerikanska presidentvalet 2004, och består av en ögonblicksbild av nästan 1500 webbloggar från den 8 februari 2005. En kant anses vara närvarande mellan två bloggar när åtminstone en av bloggarnas förstasideslänkar till den andra. Den relativa sparsamheten hos konservativa-liberala blogglänkar i detta dataset framgår tydligt av bild. 1................................................................ Den används därför ofta för att illustrera begreppet nätverksstruktur (se t.ex. [7] ). Samtidigt, Fig. 1 gör också klart att datasetet uppvisar ytterligare heterogenitet inte helt fångas av en enkel uppdelning av sina webbloggar i två samhällen, och faktiskt nyligen arbete ger också bevis på sin ytterligare blockstruktur [21]. Således nätverket histogram ger ett naturligt verktyg för att utforska data. Figur 2 visar en bifogad histogramf (x, y) som erhållits från n = 1224 bloggar med minst en länk till en annan blogg i datasetet. Från (11) fick vi en uppskattning M 2 i intervallet 1.1-1.25 för c i intervallet 3-5, och så den uppskattade oraklet fel bundet av (10) utvärderar till cirka 1,8 × 10 −2. bandbredden h * bestämdes sedan med hjälp av (12), och befanns utvärdera till 72-74 för c i intervallet 3-5. Vi avrundade detta till h = 72 för att få k = 17 lika stora histogrambehållare som består av figurer. 2 och 3. Marginalkantens sannolikhetsestimatorρ = i <j A ij / n 2 utvärderar till 16,715 / 748.476 = 2.2332 × 10 −2, vilket innebär att varje icke-diagonal histogram bin har cirka 116 effektiva frihetsgrader. Eftersom det är känt att exakt maximering av sannolikheten för (4) är omöjlig att beräkna, fick vi den passform som visas i bild. 2 genom att implementera en enkel stokastisk sökalgoritm som byter par och tripletter av nod grupp medlemskap väljs slumpmässigt tills en lokal optimal uppnås i sannolikheten för (4). Den log-likelihood av data under den monterade modellen, normaliseras av den uppskattade effektiva grader av frihet slumpmässiga konfigurationer, inspekterade de största 5% av returnerade lokala maxima, och sedan upprepade gånger återoptimeras efter slumpmässigt byta upp till 100 grupp medlemspar i den bäst returnerade lösningen. Histogrambinindexet, i förhållande till x- och y-axlarna i bild. 2, gör det möjligt att jämföra med den vänstra panelen av Bild. 1................................................................ Bin-index arrangeras först av majoriteten gruppering-liberal eller konservativ-och sedan av styrkan i varje monterad grupps partiöverskridande anslutningar. Varje nods politiska anknytning kan ses som en observerad binär kovariat som delvis förklarar nätverksstrukturen. Nedan kommer vi att överväga den mer allmänna inställningen av flera kategoriska kovariater. Som sammanfattas i figurer. 2 och 3, Det grövsta draget i detta nätverk är dess polarisering i uppsättningar av täta kopplingar inom de två politiska blocken av liberala och konservativa ideologier. Vi observerar också från Fig. 2 att nästan 40% av histogramkärlen är tomma, i enlighet med sparsamhetsmönstret hos de data som observerats i den vänstra panelen av Bild. 1................................................................ De mest tätt sammankopplade grupperna av webbloggar i båda parter uppvisar en betydande kopplingsstruktur över partigränserna. Detta är uppenbart både från centrumregionen av Fig. 2, samt grupperingarna av Fig. 3, där de mest inflytelserika bloggar som identifieras av [17] ses placeras i mitten av histogrammet. Sådana funktioner är exempel på nätverksmikrostruktur, vilket motsvarar variation på skalor som är mindre än de stora fraktionerna i ett nätverk som skulle fångas upp av en blockmodell med ett fast antal grupper. Nätverksdatauppsättningar har ofta ytterligare kovariater mätt vid noder eller kanter. För att illustrera hur man använder sådan information för att tolka nätverkshistogram analyserar vi ett studentnätverk från US National Longitudinal Study of Adolescent Health (Add Health) [22]. Som en del av denna studie, ombads eleverna att identifiera sitt kön, ras, och skolår (grad 7-12), och sedan till Vi valde att analysera School 44 från Add Health studien, ett relativt stort och rasiskt varierande exempel bland de över 80 skolor för vilka data samlades [23], och en som tidigare har analyserats i [24] med hjälp av exponentiellt slumpmässiga diagrammodeller. Den består av en huvudhögskola med årskurs 9-12 och en syster "feeder" skola med årskurs 7 och 8. Vi tog bort 21 noll grader noder samt 5 noder som motsvarar studenter för vilka två av kön, grad, eller ras kovariater saknades, vilket ger n = 1122 noder. För att passa det histogram som visas i bild. 4, Vi använde samma bandbredd urvalsförfarande och optimering algoritm som ovan. Detta gav en bandbredd h * i intervallet 69-70 för c i intervallet 3-5, som vi avrundade nedåt 13 till h = 66 för att erhålla k = 17 lika stora histogram bins. Detta är glesare än det politiska webbloggnätverk som behandlas ovan, men samtidigt utvärderar M 2 till 3,2–3,5, vilket tyder på relativt mindre smidighet. Det uppskattade orakelfelet som är bundet till (10) är då ungefär 5,6 × 10 −2, och vår passform gav ett normaliserat datalogglikviditet på −4.1714. För detta exempel, den marginella kanten sannolikhetsestimatorρ = i <j A ij / n 2 utvärderar till 5,048/628,881 = 8,0270 × 10 −3, vilket innebär att varje off-diagonal histogram bin har cirka 35 effektiva grader av frihet. För att utforska de monterade grupperna beställde vi dem post-hoc via det genomsnittliga kovariatvärdet per bin för race (kod 0-5), grad (kod 6-12) och antal nominerade vänner (kod 0-10). De resulterande histogrammen visas i den översta raden av bild. 4, Medan den nedre raden visar antalet kovariata kategorier som omfattar varje bin. I den vänstra kolumnen av Bild. 4, Vi observerar att konnektivitetsstrukturen i samband med ras delar de flesta av de vita och svarta studenter i två separata grupperingar, med en minskad tendens att länka över dessa kategorier. I den mellersta kolumnen observerar vi en liknande effekt för betyg, samt en ännu starkare effekt mellan de två separata skolorna: elever i årskurs 7-8 har relativt få interaktioner med studenter i årskurs 9-12. Det finns belägg för mer blandning inom den senare skolan, med undantag för årskurs 12, medan uppdelningen mellan årskurs 7 och 8 är stark i den förra skolan. Slutligen, i den högra kolumnen av Bild. 4 vi ser en stark effekt i samband med antalet nominerade vänner, som fungerar som en grov fullmakt för graden av varje nätverk nod. Diagonala bins i detta histogram är beställda nästan uteslutande från minsta till största, och vi ser ingen av sortativitet i samband med ras eller klass som var så uppenbart i de tidigare histogrambeställningar. Av detta exempel drar vi slutsatsen att nätverkets histogram inte bara kan ge en effektiv sammanfattning av nätverksinteraktioner, utan också kan tolkas i samband med ytterligare kovariatinformation. Denna typ av aggregerad sammanfattning ger en finkornig men koncis bild av ungdomars vänskapsnätverk, och tyder på att aggregerad statistik om ras och betyg inom en viss skola kanske inte är tillräcklig för att ge en fullständig bild av de rapporterade sociala interaktionerna mellan sina elever. Vi hävdar att blockmodellen är universell som ett verktyg för att representera interaktioner i ett omärkt nätverk. När vi använder fler block i vår representation förbättrar vi vår approximation av den underliggande datagenererande mekanismen, om än på bekostnad av ökad komplexitet. Resultaten i den här artikeln ger oss insikt i hur man kan kontrollera avvägningen mellan komplexitet och precision, vilket leder till en flexibel icke-parametrisk sammanfattning av ett nätverk som liknar en vanlig histogram. Det finns en tydlig filosofisk skillnad mellan nätverkshistogrammet och den stokastiska blockmodellen. Nätverkets histogram ger en icke-parametrisk sammanfattning av länkarnas densiteter över ett nätverk. I kontrast, den stokastiska blockmodellen var ursprungligen tänkt som en generativ statistisk modell, vilket innebär att det är 14 normalt analyseras i inställningar där det antas vara korrekt specificerat som den data-genererande mekanismen. Vi har i stället visat hur det kan vara användbart i fallet när blockmodellen helt enkelt används för att approximera genereringsmekanismen i nätverket – ett mycket mildare antagande. För att göra nätverkshistogrammet till ett användbart praktiskt verktyg har vi härlett en procedur för att automatiskt välja en analysbandbredd under antagande av en jämn (Hölder kontinuerlig) grafon. Om grafon har ändligt många diskontinuiteter parallellt med dess x-och y-axes, till exempel om det motsvarar en faktisk blockmodell, då goda skattningsegenskaper kan fortfarande uppnås, analogt med vanliga histogram uppskattningar [25]. I sådana scenarier är de hastigheter med vilka skattningsfelen förfaller ännu inte fastställda; att undersöka olika diagram över jämnhetsklasser, och de nätverk som de ger upphov till, förblir en viktig väg för framtida undersökningar. Som en sista punkt utforskas sällan nätverk i avsaknad av andra uppgifter. Ett nätverk histogram definieras endast upp till permutation av sina behållare, och så för att underlätta dess tolkning kan vi använda andra observerade variabler, etiketter, eller kovariater för att informera vårt val av bin beställning. Som vårt andra exempel på dataanalys har visat i samband med studentvänskapsnätverk, kan flera representationer vara användbara på olika sätt, och mer än en sådan visuell representation kan ge insikt i nätverkets genereringsmekanism. På så sätt är blockmodellens universalitet en nyckelpjäs i den allmänna nätverksförståelsens pussel. Våra resultat tyder på en grundläggande ny syn på tolkningen av nätverksgrupper, mot bakgrund av att många olika samhällsuppdrag alla kan ge en lika giltig representation av nätverket.
Det finns flera andra metoder för grafonuppskattningar, t.ex. genom att montera en stokastisk blockmodell REF.
Network histograms and universality of blockmodel approximation
{'venue': 'Proceedings of the National Academy of Sciences of the USA 2014, Vol. 111, No. 41, 14722-14727', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Medicine', 'Mathematics']}