På många vetenskapliga områden finns det ett vanligt behov av att automatiskt extrahera en förenklad vy eller grovkornig bild av hur ett komplext systems komponenter interagerar. Denna allmänna uppgift kallas community detektering i nätverk och är jämförbar med att söka efter kluster i oberoende vektordata. Det är vanligt att utvärdera prestandan hos samhällets detektionsalgoritmer genom deras förmåga att hitta så kallade marksanningssamhällen. Detta fungerar bra i syntetiska nätverk med planterade samhällen eftersom sådana nätverks länkar bildas uttryckligen baserat på dessa kända samhällen. Det finns emellertid inga planterade samhällen i verkliga nätverk. Istället är det praxis att behandla några observerade diskret värderade nodattribut, eller metadata, som grundsanning. Här visar vi att metadata inte är samma sak som grundsanning, och att behandling av dem som sådana framkallar allvarliga teoretiska och praktiska problem. Vi bevisar att ingen algoritm unikt kan lösa community upptäckt, och vi bevisar en allmän No Free Lunch teorem för community upptäckt, vilket innebär att det inte kan finnas någon algoritm som är optimal för alla möjliga community upptäckt uppgifter. Men community upptäckt är fortfarande ett kraftfullt verktyg och nod metadata har fortfarande värde så en noggrann undersökning av deras relation till nätverksstruktur kan ge insikter om äkta värde. Vi illustrerar detta genom att införa två statistiska tekniker som kan kvantifiera förhållandet mellan metadata och samhällsstruktur för en bred klass av modeller. Vi demonstrerar dessa tekniker med hjälp av både syntetiska och verkliga nätverk, och för flera typer av metadata och samhällsstruktur. Gemenskapens upptäckt är en grundläggande uppgift för nätverksforskningen som syftar till att beskriva den storskaliga strukturen i ett nätverk genom att dela upp dess noder i samhällen (även kallade block eller grupper), endast baserat på mönstret av länkar. Denna uppgift liknar uppgiften att samla vektordata, eftersom båda försöker identifiera meningsfulla grupper inom vissa datamängder. Gemenskapens upptäckt har använts produktivt i många tillämpningar, inklusive att identifiera lojaliteter eller personliga intressen i sociala nätverk [1, 2], biologisk funktion i metaboliska nätverk [3, 4], bedrägeri i telekommunikationsnät [5], och homologi i genetiska likhetsnätverk [6]. Många tillvägagångssätt för community detektion finns, spänner inte bara olika algoritmer och partitionering strategier, men också fundamentalt olika definitioner av vad det innebär att vara en "gemenskap". Denna mångfald är en styrka, eftersom nätverk som genereras av olika processer och fenomen inte på förhand bör förväntas beskrivas väl av samma strukturella principer. Med så många olika metoder för att upptäcka människor i samhället är det naturligt att jämföra dem för att bedöma deras relativa styrkor och svagheter. Vanligtvis görs denna jämförelse genom att bedöma en metod förmåga att identifiera så kallade marksanning gemenskaper, en synd- * Insänt lika; leto.peel@uclouvain.be † Insänt lika; larremore@santafe.edu  och aaron.clauset@colorado.edu gle partition av nätverkets noder i grupper som anses vara rätt svar. Denna metod för utvärdering av metoder för detektering av samhällen fungerar bra i artificiellt genererade nätverk, vars länkar uttryckligen placeras enligt dessa sanningsgemenskaper på marken och en känd process för att generera data. Av denna anledning, uppdelningen av noder i marksanning samhällen i syntetiska nätverk kallas en planterad partition. För verkliga nätverk är dock både den korrekta partitionen och den sanna datagenereringsprocessen vanligtvis okända, vilket nödvändigtvis innebär att det inte kan finnas några verkliga sanningsgemenskaper för verkliga nätverk. Utan tillgång till just det som dessa metoder är avsedda att finna är det svårt att göra en objektiv utvärdering av deras resultat. Istället har det blivit standard praxis att behandla vissa observerade data på noderna i ett nätverk, som vi kallar nodmetadata, (t.ex. en persons etnicitet, kön eller tillhörighet för ett socialt nätverk, eller en gens funktionella klass för ett genregelverk) som om de vore grundsanningsgemenskaper. Även om denna utbredda praxis är lämplig, kan den leda till felaktiga vetenskapliga slutsatser under relativt vanliga omständigheter. I den här artikeln identifierar vi dessa konsekvenser och formulerar det epistemologiska argumentet mot att behandla metadata som sanningsgemenskaper på marken. Därefter ger vi rigorösa matematiska argument och bevisar två teorem som gör sökandet efter en universellt bästa mark-sanning återhämtningsalgoritm som fundamentalt bristfällig. Vi presenterar sedan två nya metoder som kan användas för att produktivt utforska förhållandet mellan observerade metadata och samhällsstruktur, och demonstrera båda metoderna på en mängd olika syntetiska och verkliga nätverk, med hjälp av molarXiv:1608.05878v2 [cs.SI] 3 maj 2017 2 tiple community detection ramar. Genom dessa exempel illustrerar vi hur en noggrann undersökning av förhållandet mellan metadata och samhällsstruktur kan belysa den roll nodattribut spelar för att skapa nätverkslänkar i verkliga komplexa system. Problemet med metadata och community detektion Användningen av nodmetadata som en proxy för marksanning beror på ett rimligt behov: eftersom konstgjorda nätverk kanske inte är representativa för naturligt förekommande nätverk, måste community detektionsmetoder också konfronteras med verkliga exempel för att visa att de fungerar bra i praktiken. Om de upptäckta samhällena korrelerar med metadata kan vi rimligen dra slutsatsen att metadata är involverade i eller beroende av generering av observerade interaktioner. Men det vetenskapliga värdet av en metod definieras lika mycket av det sätt på vilket den misslyckas som av dess förmåga att lyckas. Eftersom metadata alltid har ett osäkert förhållande till grundsanning, är underlåtenhet att hitta en bra uppdelning som korrelerar med våra metadata ett mycket komplicerat resultat, som uppstår av någon av flera skäl: (i) dessa specifika metadata är irrelevanta för nätverkets struktur, (ii) de upptäckta samhällena och metadatana fångar olika aspekter av nätverkets struktur, (iii) nätverket innehåller inga samhällen som i en enkel slumpmässig graf [7] eller ett nätverk som är tillräckligt glest att dess samhällen inte är detekterbara [8], eller (iv) samhällets detektionsalgoritm utförs dåligt. I ovanstående hänvisar vi till det observerade nätverket och metadata och noterar att buller i antingen kan leda till en av orsakerna ovan. Till exempel kan mätfel i nätverksstrukturen göra våra observationer opålitliga och i extrema fall kan dunkel gemenskapsstruktur helt och hållet, vilket resulterar i fall (iii). Det är också möjligt att mänskliga fel införs vid hanteringen av data, exemplifierat av det allmänt använda amerikanska college fotbollsnätverket [9] av lag som spelade varandra under en säsong, vars tillhörande metadata som representerar varje lags konferensuppdrag samlades in under en annan säsong [10]. Stora fel i metadata kan göra dem irrelevanta för nätverket [fall (i)]. De flesta arbeten med att upptäcka samhällen förutsätter att underlåtenhet att hitta samhällen som korrelerar med metadata innebär fall (iv), algoritmfel, även om vissa kritiska arbete har fokuserat på fall (iii), svårt eller omöjligt att återställa samhällen. Bristen på hänsyn i ärenden (i) och (ii) tyder på möjligheten att välja partiskhet i. Det högdimensionella utrymmet för alla möjliga delningar av nätverket har projicerats på x, y-planet (med hjälp av en metod som beskrivs i kompletterande text D 4) så att punkter som representerar liknande partitioner är närmare varandra. Ytan visar två tydliga toppar som representerar vetenskapligt rimliga skiljeväggar. Den lägre toppen motsvarar den sociala grupppartitionen som ges av metadata-ofta behandlad som marksanning, medan den högre toppen motsvarar en partition som följer ledare. den publicerade litteraturen på detta område (en punkt som nyligen föreslogs av [11] ). Den senaste tidens kritik av samhällsdetekteringens allmänna nytta i nätverk [11] [12] [13] kan ses som en bieffekt av förvirring om metadatas roll i utvärderingen av algoritmresultat. Av dessa skäl kan användning av metadata för att bedöma prestandan hos gemenskapens detektionsalgoritmer leda till tolkningsfel, falska jämförelser mellan metoder och tillsyn av alternativa mönster och förklaringar, inklusive sådana som inte korrelerar med kända metadata. Zachary's Karate Club [14] är till exempel ett litet realworld-nätverk med övertygande metadata som ofta används för att demonstrera samhällsdetektionsalgoritmer. Nätverket representerar de observerade sociala interaktionerna mellan 34 medlemmar i en karateklubb. Vid studietillfället hamnade klubben i en politisk dispyt och delades upp i två fraktioner. Dessa fraktionsetiketter är de metadata som vanligen används som sanningsgemenskaper på marken för att utvärdera metoder för att upptäcka samhällen. Det är dock värt att notera att Zacharys ursprungliga nätverk och metadata skiljer sig från dem som vanligen används för community detection [9]. Länkar i det ursprungliga nätverket var av de olika typer av social interaktion som Zachary observerade. Zachary spelade också in två metadata attribut: den politiska lutande av var och en av medlemmarna (stark, svag, eller neutralt stöd för en av fraktionerna) och den fraktion de slutligen gick med efter splittringen. Detektionslitteraturen använder dock endast metadata som representerar fraktionen som varje nod förenas med, ofta med en av noderna felmärkt. Denna nod ("person nummer 9") stödde presidenten under tvisten men gick med i instruktörens fraktion som att gå med i presidentens fraktion skulle ha inneburit omskolning som en nybörjare när han var bara två veckor från att ta sin svarta bälte examen. Uppdelningen av Karate Club noder i fraktioner är inte det enda vetenskapligt rimliga sättet att partitionera nätverket. Figur 1 visar log-likelihood landskapet för ett stort antal två grupper partitioner (inbäddade i två dimensioner för visualisering) av Karate Club, under den stokastiska blockmodellen (SBM) för community detektion [15, 16]. Partitioner som liknar varandra är inbäddade i de horisontella koordinaterna, vilket innebär att de två breda topparna i landskapet representerar två skilda uppsättningar av höglikliga partitioner, en centrerad kring fraktionsdivisionen och en som delar upp nätverket i ledare och anhängare. Andra gemensamma metoder för community detection [9, 17], tyder på att de bästa delarna av detta nätverk har mer än två samhällen [10, 18]. De goda partitionernas mångfald och mångfald illustrerar falangmetadatans tvetydiga status som ett önskvärt mål. Karate Club-nätverket är bland många exempel för vilka vanliga community detektionsmetoder returnerar samhällen som antingen delar upp metadatapartitionen [19] eller inte korrelerar med metadata alls [20, 21]. Mer allmänt, de flesta verkliga nätverk har många bra partitioner och det finns många rimliga sätt att sortera alla partitioner för att hitta bra sådana, ibland leder till ett stort antal rimliga resultat. Dessutom finns det ingen enighet om vilken metod som ska användas för vilken typ av nät [21, 22]. I det följande utforskar vi både de teoretiska orsakerna till dessa problem och de praktiska medlen för att ta itu med de förbryllande fall som beskrivs ovan. För att göra det använder vi ett generativt modellperspektiv för att upptäcka samhället. I detta perspektiv beskriver vi relationen mellan samhällstilldelningar C och grafer G via en gemensam distribution P (C, G) över alla möjliga samhällsuppdrag och grafer som vi kan observera. Vi tar detta perspektiv eftersom det ger en exakt och tolkningsbar beskrivning av förhållandet mellan samhällen och nätverksstruktur. Även om generativa modeller, liksom SBM, beskriver förhållandet mellan nätverk och samhällen direkt via ett matematiskt uttryck för P (C, G), andra metoder för community detektion ändå upprätthålla en implicit relation mellan nätverksstruktur och community uppdrag. Som sådan, de teorem vi presenterar, liksom deras konsekvenser är mer allmänt tillämpliga på alla metoder för att upptäcka samhället. I nästa avsnitt presenterar vi rigorösa teoretiska resultat med direkta konsekvenser för ärenden (i) och (iv), medan de återstående avsnitten inför två statistiska metoder för att ta itu med ärenden (i) respektive (ii). Dessa bidrag behandlar inte ärende iii, när det inte finns någon struktur att hitta, som tidigare har undersökts av andra författare, t.ex. för SBM [8, [23] [24][25][26][27] och moduläritet [28, 29]. Gemenskapens upptäckt är ett omvänt problem: med endast nätets kanter som data syftar vi till att hitta grupperingen eller partitionen av de noder som relaterar till hur nätverket kom att bli. Mer formellt, anta att vissa datagenererande process g bäddar in mark-truth communities T i mönster av länkar i ett nätverk G = g(T ). Vårt mål är att upptäcka dessa samhällen endast baserat på de observerade länkarna. För att göra det skriver vi ner ett community detection system f som använder nätverket för att hitta samhällen C = f (G). Om vi har valt f väl, då samhällena C kommer att vara lika med marken sanningen T och vi har löst det omvända problemet. Problemet med att upptäcka gemenskapen för ett enda nätverk söker därför en metod f * som minimerar avståndet mellan de identifierade samhällena och marksanningen: där d är ett mått på avståndet mellan skiljeväggarna. För att en metod f ska vara allmänt användbar, bör den vara minimeraren för många olika grafer, var och en med sin egen generativa process och marksanning. Ofta i gemenskapens detektionslitteratur testas flera algoritmer på en rad olika nätverk för att identifiera vilka som presterar bäst totalt [12, 30, 31]. Om en universellt optimal community detektionsmetod finns, måste den lösa Eq. (1) för alla typer av generativ process g och partition T, det vill säga, I själva verket, ingen sådan universell f * gemenskap detektionsmetod kan existera eftersom kartläggning från generativa modeller g och mark sanning partitioner T till grafer G är inte unikt inverterbar på grund av det faktum att kartan inte är en bijective. Med andra ord, något visst nätverk G kan produceras av flera, distinkta generativa processer, var och en med sin egen grund sanning, sådan att G = g 1 (T 1 ) = g 2 (T 2 ), med (g 1, T 1 ) = (g 2, T 2 ). Således kan ingen community detektionsalgoritm metod unikt lösa problemet för alla möjliga nätverk (Eq. (2)), eller till och med ett enda nätverk (Eq. 1 )................................................................................................................. Detta resonemang underbygger följande teorem, som vi anger och bevisar i Kompletterande Text C: Teorem 1: För ett fast nätverk G, lösningen till marksanning gemenskap upptäckt problem-given G, finner T sådan att G = g(T )-är inte unik. Att skapa metadata M för marksanning T förvärrar situationen genom att skapa ytterligare problem. I verkliga nätverk känner vi inte till sanningen på marken eller produktionsprocessen. Istället är det vanligt att söka en partition som matchar några nodmetadata M. Optimering 4 en community detektionsmetod för att upptäcka M är likvärdig med att hitta f * sådan att detta inte nödvändigtvis löser problemet med community detektion av Eq. (1) eftersom vi inte kan garantera att metadata är likvärdiga med den oobserverade marksanningen, d(M, T ) = 0. Följaktligen är både d(C, T ) = 0 och d(C, T ) > 0 möjligheter. Således, när vi utvärderar en community detektion metod med dess förmåga att hitta en metadata partition, vi förbryllade metadata korrespondens till de sanna samhällen, dvs d(M, T ) [case (ii) i föregående avsnitt] och gemenskapens detektionsmetod förmåga att hitta sanna samhällen, d(C, T ) [case (iv)]. På så sätt testar metadata som grundsanning samtidigt metadatas relevans och algoritmens prestanda, utan förmåga att skilja mellan de två. Till exempel, när man överväger konkurrerande partitioner av Karate Club (Figur 1 ), ledaren-följare partitionen är den mest sannolika partitionen under SBM, men det korrelerar dåligt med den kända metadata. Å andra sidan, under den gradkorrigerade SBM, är den optimala partitionen mer korrelerad med metadata (Fig. S1 )............................................................................................................... Baserat endast på prestandan av att återställa metadata, skulle man dra slutsatsen att den grad-korrigerade modellen är bättre. Men om Zachary inte hade tillhandahållit fraktionsinformationen, utan istället några metadata som korrelerade med graden (t.ex. identiteterna för klubbens fyra officerare) då vår slutsats kan ändras till den vanliga SBM är den bättre modellen. Vi skulle komma fram till en annan slutsats trots att nätverket, och den underliggande processen som genererade det, förblir oförändrad. Ett liknande fall av beroende av ett visst val av metadata exemplifieras av indelningar av high school sociala nätverk med hjälp av metadata av elevernas betygsnivå eller ras [21]. Tidigare utvärderingar av samhällsdetektionsalgoritmer som endast mäter prestanda genom metadataåterställning är därför ofullständiga. Det är endast med syntetiska data, där den generativa processen är känd, som grundsanningen är vetbar och prestanda objektivt mätbar. Men även när den generativa processen är känd för ett enda nätverk eller ens en uppsättning nätverk, det finns ingen bästa community detektionsmetod över alla nätverk. Detta beror på att, när genomsnitt över alla möjliga problem gemenskap upptäckt, varje algoritm har bevisligen identiska prestanda, ett begrepp som fångas i en No Free Lunch teorem för community detektion som vi rigoröst anger och bevisa i Kompletterande Text C och parafras här: Theorem 3 (parafraserad): För samhället detektion problem, med noggrannhet uppmätt genom justerad ömsesidig information, det enhetliga genomsnittet av noggrannheten hos någon metod f över alla möjliga problem gemenskap detektion är en konstant som är oberoende av f. Detta No Free Lunch teorem, baserat på No Free Lunch teorem för övervakad lärande [32], innebär att ingen metod har en förhandsfördel över alla andra möjliga community detektion uppgifter. (I själva verket, Theorem 3 och dess bevis gäller för klusterering och partitionering metoder i allmänhet, bortom gemenskap upptäckt.) Med andra ord, för en uppsättning fall som en viss metod f a outperforms f b, Det måste finnas en uppsättning fall där f b outperforms f a - i genomsnitt ingen algoritm presterar bättre än någon annan. Men detta gör inte samhällets upptäckt meningslös eftersom teorem också innebär att om uppgifterna av intresse motsvarar en begränsad del av fall (t.ex. att hitta samhällen i genreglerande nätverk eller vissa typer av grupper i sociala nätverk), då kan det verkligen finnas en metod som överträffar andra inom ramen för denna delmängd. Kort sagt, matchande föreställningar om datagenereringsprocessen g med antagandena av algoritmen f kan leda till bättre och mer exakta resultat, till priset av minskad allmängiltighet. (Se kompletterande text C för ytterligare diskussion.) De sammantagna konsekvenserna av de epistemologiska argumenten i föregående avsnitt med teorem 1 och 3 i detta avsnitt gör det inte omöjligt eller meningslöst att på något sätt upptäcka samhället. De innebär dock att ansträngningar för att hitta en universellt bästa community detektionsalgoritm är förgäves och att metadata inte bör användas som ett riktmärke för att utvärdera eller jämföra effektiviteten hos community detektionsalgoritmer. Dessa teorem visar att bättre detekteringsresultat i samhället kan härröra från en bättre förståelse av hur problemutrymmet kan delas upp i kategorier av detekteringsuppgifter i samhället, och slutligen identifiera klasser av algoritmer vars styrkor är i linje med kraven i en viss kategori. Ur ett vetenskapligt perspektiv har metadataetiketter ett direkt och genuint värde när det gäller att hjälpa till att förstå komplexa system. Metadata beskriver noderna, medan samhällen beskriver hur noderna interagerar. Korrespondens mellan metadata och samhällen tyder därför på ett samband mellan hur noder interagerar och egenskaperna hos noderna själva. Denna korrespondens har använts produktivt för att hjälpa till att dra slutsatser om samhällsstrukturen [21], lära sig förhållandet mellan metadata och nätverkstopologi [33, 34] och förklara beroenden mellan metadata och nätverksstruktur [35]. Här föreslår vi två nya metoder för att undersöka hur metadata relaterar till nätverkets struktur när metadata endast svagt korrelerar med de identifierade samhällena. Båda metoderna använder de kraftfulla verktygen i probabilistiska modeller, men är inte begränsade till någon särskild modell av samhällsstruktur. Den första metoden är ett statistiskt test för att bedöma om metadatapartitionen och nätverksstrukturen är relaterade [fall (i)]. Den 5 andra metoden undersöker utrymmet för nätverkspartitioner för att avgöra om metadata representerar samma eller olika aspekter av nätverksstrukturen som de "optimala" samhällen som härleds av en vald modell [case (ii)]. I princip skulle varje probabilistisk generativ modell (t.ex. [15, 16,][36][37][38][39]) av samhällen i nätverk kunna användas inom dessa metoder. Här får vi resultat för den populära stokastiska blockmodellen [15, 16] och dess gradkorrigerade version [20] (alternativa formuleringar som diskuteras i kompletterande texter B och A). SBM definierar samhällen som uppsättningar av noder som är stokastiskt likvärdiga. Detta innebär att sannolikheten p ij av en länk mellan ett par noder i och j beror endast på deras community uppdrag, dvs p ij =  och πi,πj, där π i är community uppdrag för node i och.j πi,πj är sannolikheten för att det finns en koppling mellan medlemmar i grupper π i och π j. Denna allmänna definition av samhällsstrukturen är ganska flexibel och möjliggör både olika och olika samhällsstrukturer, liksom godtyckliga blandningar av dessa. Vår första metod, som kallas blockmodellen entropi signifikanstest (BESTest), är ett statistiskt test för att avgöra om metadatapartitionen är relevant för nätverksstrukturen [case (i)], dvs. om den ger en bra beskrivning av nätverket enligt en viss modell. Vi kvantifierar relevans med hjälp av entropi, vilket är ett mått på hur många bitar av information det tar att registrera nätverket med tanke på både nätverksmodellen och dess parametrar. Ju lägre entropi under denna modell, desto bättre metadata beskriver nätverket, medan en högre entropi innebär att metadata och mönster av kanter i nätverket är relativt okorrelerade. Vi härleder och diskuterar de bästa med hjälp av fem olika modeller i kompletterande text B. Här beskriver vi en särskilt enkel version av detta test med hjälp av SBM. Den bästa fungerar genom att först dela ett nätverk noder enligt etiketterna på metadata och sedan datorisera entropi av SBM som bäst beskriver de partitionerade noder. Denna entropi jämförs sedan med en distribution av entropier som använder samma nätverk men slumpmässiga permutationer av metadataetiketterna, vilket resulterar i ett standardp-värde. Specifikt använder vi SBM med maximal sannolikhet parametrar för den partition som induceras av metadata, som ges av på rs = Mrs nrns där m rs är antalet länkar mellan grupp r och grupp s och n r är antalet noder i grupp r. Sedan beräknar vi entropi H(G; M), som vi härleder och diskuterar i detalj, tillsammans med härledning av entropier för andra modeller, i Kompletterande text B. Den statistiska signifikansen av entropivärdet H(G; M) erhålls genom att jämföra det med entropin i samma nätverk men slumpmässigt permuterade metadata. Specifikt beräknar vi en nollfördelning av sådana värden, härledd genom att beräkna de entropier som induceras av slumpmässiga permutationer {π} av de observerade metadatavärdena H(G;π). Detta val av nullmodell bevarar både den empiriska nätverksstrukturen och de relativa frekvenserna av metadatavärden, men tar bort korrelationen mellan de två. Resultatet är ett standardp-värde, definierat som vilket kan uppskattas empiriskt genom att beräkna H(G;π) för ett stort antal slumpmässigt permuterade metadatavektorerπ. Mindre p-värden indikerar att metadata ger en bättre beskrivning av nätverket, vilket gör det relativt mindre troligt att en slumpmässig permutation av metadatavärdena skulle kunna beskriva nätverket liksom de observerade metadata gör. Det är viktigt att notera att p-värden mäter statistisk signifikans men inte effektstyrka, vilket innebär att ett lågt p-värde inte indikerar någon stark korrelation mellan metadata och nätverksstrukturen. Nyligen, Bianconi et al. [40] föreslog ett relaterat entropitest för denna uppgift, baserat på en normal approximation till nollfördelningen enligt SBM. Blockmodellen entropi signifikanstest som beskrivs här är en generalisering av Bianconi et al.Testet som är både mer flexibelt, eftersom det kan användas med ett antal null modeller, och mer exakt, eftersom den verkliga null fördelning är i stort sett icke-Normal (Fig. S5).............................................................................. Blockmodellens signifikanstest är, genom konstruktion, känsligt för även låga korrelationer mellan metadata och nätverksstruktur. För att kvantifiera känsligheten hos detta p-värde använder vi det först på syntetiska nätverk med känd samhällsstruktur (se Kompletterande text B för en fullständig beskrivning av syntetisk nätverksgenerering). För dessa nätverk bestäms vår förmåga att upptäcka relevanta metadata gemensamt av styrkan i de planterade samhällena och korrelationen mellan metadata och samhällen. Figur 2 visar att för nätverk med stark samhällsstruktur kan vi på ett tillförlitligt sätt upptäcka relevanta metadata även för relativt låga korrelationsnivåer med den planterade strukturen. I själva verket kan vår metod fortfarande identifiera relevanta metadata när samhällsstrukturen är tillräckligt svag att samhällen är bevisligen odetekterbara av någon gemenskap detektionsalgoritm som endast förlitar sig på nätverket [8]. Statistisk betydelse kräver en ökande nivå av korrelation med den underliggande strukturen som gemenskap styrka minskar; om det inte finns någon struktur i nätverket ( = 1) då någon metadata-partition kommer att korrekt identifieras som irrelevant. Observera att ett lågt p-värde inte innebär att metadata ger den bästa beskrivningen av nätverket, inte heller innebär det att vi ska kunna återställa metadatapartitionen med hjälp av gemenskapdetektering. Vi tillämpar nu blockmodellen entropi signifikanstest på ett socialt nätverk av interaktioner inom en advokatbyrå, och på biologiska nätverk som representerar likheter mellan gener i den mänskliga malariaparasiten P. falciparum (se Kompletterande text D). Den första uppsättningen, Lazega Lawyers nätverk, består av tre nätverk på samma uppsättning noder och fem metadata attribut. De flera kombinationer av kant- och metadatatyper som ger mycket betydande p-värden (tabell I; se tabell S3 för resultat med hjälp av ytterligare modeller av samhällsstruktur) indikerar att varje uppsättning metadata ger icke-trivial information om strukturen i flera nätverk, och vice versa, vilket innebär att alla metadatauppsättningar är relevanta för eggbildningsprocessen, så ingen bör behandlas individuellt som marksanning. Den andra uppsättningen, malaria var gennätverk, omfattar nio nätverk på samma uppsättning noder och tre uppsättningar metadata. För varje nätverk finner vi ett icke-betydande p-värde när metadata betecknar parasitgenomet av ursprung (tabell II; se tabell S4 för resultat med hjälp av ytterligare modeller av samhällsstruktur och ytterligare metadata). I motsats till Lazega Lawyers-nätverket är dessa genommetadata statistiskt irrelevanta för att förklara de observerade genrekombinationernas mönster. Denna slutsats stärker i hög grad slutsatserna i Ref. [41] som använde ett mindre känsligt test baserat på etikettens sortivitet. Vissa metadata för dessa nätverk korrelerar dock (se kompletterande text B). Diagnostisera de strukturella aspekter som fångas upp av metadata och samhällen Vår andra metod ger ett direkt sätt att diagnostisera om vissa metadata och ett nätverk upptäckta samhällen skiljer sig åt eftersom de avslöjar olika aspekter av nätverkets struktur [case (ii)]. Vi åstadkommer detta genom att utöka SBM för att undersöka den lokala strukturen runt och mellan metadata-partitionen och de upptäckta strukturella samhällena. Denna utvidgade modell, som vi kallar neoSBM, utför community upptäckt under en begränsning där varje nod tilldelas en av två stater, som vi kallar blå eller röd, och en parameter q som styr antalet noder i varje tillstånd. Om en nod är blå, är dess gemenskap fast som sin metadata etikett, medan om den är röd, dess gemenskap är fri att väljas av modellen. Vi väljer q automatiskt inom inference steg av modellen genom att införa en sannolikhetspåföljd i form av en Bernoulli tidigare med parameter  på, som kontrollerar för den ytterligare frihet som kommer från varierande q. där  på ( på) kan tolkas som kostnaden för att befria en nod från sin metadata etikett (se Kompletterande text A för exakt formulering). Genom att variera kostnaden för att frigöra en nod, kan vi använda neoSBM för att producera en grafisk diagnostik av det inre av utrymmet mellan metadata-partitionen och den inferred gemenskapen partitionen. På detta sätt kan neoSBM sprida ljus över hur metadata och infererade community-partitioner är relaterade, bortom direkt jämförelse av partitionerna via standardtekniker såsom normaliserad ömsesidig information eller Rand-indexet. Eftersom kostnaden för att frigöra noder minskas, skapar neoSBM en väg genom utrymmet för partitioner från metadata till optimal gemenskap partition och, som det gör, vi övervaka förbättringen av partitionen genom ökningen av SBM log sannolikhet. En stadig ökning indikerar att neoSBM successivt förfinar metadata-partitionen tills den matchar de globalt optimala SBM-gemenskaperna. Detta beteende innebär att metadata och community-partitioner representerar relaterade aspekter av nätverksstrukturen. Å andra sidan, om SBM-sannolikheten förblir konstant för ett betydande utbud av  ska, följt av en kraftig ökning eller hopp, det indikerar att neoSBM har flyttat från en lokal optimal till en annan. Flera platåer och hopp indikerar att flera lokala optima har korsats, avslöjar att partitionerna fångar olika aspekter av nätverkets struktur. För att demonstrera användningen av neoSBM, undersöker vi vägen mellan partitioner för ett syntetiskt nätverk med fyra lokalt optimala partitioner som motsvarar de fyra distinkta topparna i ytplotten ( Bild. 3A; se kompletterande text A för en fullständig beskrivning av syntetisk nätverksgenerering). Vi tar partitionen av de lägsta av dessa toppar som metadata och använder neoSBM för att generera en väg till den globalt optimala partitionen genom att variera parametern för neoSBM från 0 till 1. Motsvarande förändringar i SBM log sannolikhet och antalet fria noder visar tre diskontinuerliga hopp (Fig. 3C), en för varje gång modellen möter en ny lokalt optimal partition. Att undersöka partitionerna längs neoSBM:s väg kan ge direkta insikter i förhållandet mellan metadata och nätverksstruktur. Figur 3B visar strukturen vid var och en av de fyra genomkorsade optima som blockvis interaktionsmatriser. Varje partition har en annan typ av storskalig struktur, från kärnperiferi till diverse mönster. På så sätt, när metadata inte nära matchar infererade samhällen, kan neoSBM belysa om och hur metadata fångar liknande eller olika aspekter av nätverksstruktur. Vi presenterar nu en tillämpning av neoSBM på Lazega Lawyers data analyseras i föregående avsnitt. När den initieras med juridikskolan och kontorsmetadata, producerar neoSBM tydliga mönster av avkoppling till den globala optimal (Fig. 4A,C) närmar sig den från motsatta sidor av toppen i sannolikhetsytan. Med början på juridikskolans metadata passerar modellen utrymmet för partitioner till den globala SBM-optimala partitionen utan att stöta på någon lokal optima. I kontrast, vägen från kontoret metadata korsar en lokal optimal (Fig. 4A,B), vilket indikerar att juridikskolan metadata är närmare förknippade med den storskaliga organisationen av nätverket än kontorsmetadata. Båda uppsättningarna metadataetiketter är dock relevanta, som vi bestämde i föregående avsnitt med hjälp av BESTest. Resultat för andra verkliga nätverk ingår i Kompletterande Text A, inklusive generaliseringar av neoSBM till andra community detektionsmetoder. Att behandla nodmetadata som sanningsgemenskaper på marken för verkliga nätverk är allmänt motiverat genom en felaktig övertygelse om att syftet med communitydetektion är att återställa grupper som matchar metadataetiketter [11, 13, 31, 43]. Följaktligen används ofta metadataåterställning för att mäta community detection prestanda [44] och metadata kallas ofta för marksanning [21, 45]. Organisationen av verkliga nätverk korrelerar dock vanligtvis med flera uppsättningar metadata, både observerade och oobserverade. På så sätt är det ett godtyckligt och i allmänhet omotiverat beslut att beteckna en viss sanning som "grundlig". Dessutom, när en community detektionsalgoritm misslyckas med att identifiera samhällen som matchar kända metadata, är dålig algoritmprestanda oskiljaktig från tre alternativa möjligheter: (i) metadata är irrelevanta för nätverksstrukturen, (ii) metadata och samhällen fångar olika aspekter av nätverksstrukturen, eller (iii) nätverket saknar gruppstruktur. Här har vi infört två nya statistiska verktyg för att direkt undersöka fall i) och ii), medan iii) fortfarande behandlas väl av andra författare [8, [23] [24][25][26][27][28][29]. Vi har också formulerat flera matematiska argument som drar slutsatsen att det är både teoretiska och praktiska problem att behandla metadata som en grundläggande sanning i detektionen av samhället. Men vi har också visat att metadata fortfarande är användbara och att en noggrann undersökning av förhållandet mellan nodmetadata och samhällsstruktur kan ge nya insikter i nätverkets underliggande genereringsprocess. Genom att endast söka efter samhällen som är starkt korrelerade med metadata riskerar vi att fokusera enbart på positiva korrelationer samtidigt som vi bortser från andra vetenskapligt relevanta organisationsmönster. I vissa fall, meningsskiljaktigheter mellan metadataetiketter och gemenskap detektion re- (B) Block densitet diagram visar gemenskapsstruktur för metadata, (1-2) mellanliggande optimala, och (3) globalt optimala partitioner, där mörkare färg indikerar högre sannolikhet för interaktion. (C) neoSBM går två skilda vägar till den globala optimal (3), men endast den väg som börjar vid kontoret metadata partitionen passerar en lokal optimal (1), indikeras av en platå i fria noder q och log sannolikhet. Sults kan i själva verket peka på intressanta eller oväntade generativa processer. I nätverket Karate Club finns det till exempel en nod vars metadataetikett inte återvinns av de flesta algoritmer. En noggrann läsning av Zacharys originalmanuskript visar att det finns en rationell förklaring till denna ennodeskillnad: även om eleven hade mer sociala band till presidentens grupp, valde han att gå med i instruktörsgruppen för att inte förlora sina framsteg mot sitt svarta bälte [14]. I andra fall kan metadata ge oss en berättelse som förblindar oss till ytterligare struktur, exemplifierad av ett nätverk av politiska bloggar [1] där liberala och konservativa bloggar bildade två mycket olika grupper. Följaktligen har återvinning av dessa två grupper använts som en signal om att en metod ger "bra" resultat [20]. En djupare analys tyder dock på att detta nätverk beskrivs bättre genom att dela upp dessa två grupper, ett steg som avslöjar betydande understruktur inom de dominerande mönstren för politisk konnektivitet [19, 39]. Dessa undergrupper förbisågs delvis eftersom metadataetiketterna låg tätt i linje med en lockande enkel berättelse. Uppgiften att upptäcka gemenskapen är nätverket analogt av datakluster. Medan klustering delar upp en uppsättning vektorer i grupper med liknande attributmönster, delar community detektion ett nätverk i grupper av noder med liknande konnektivitetsmönster. Det allmänna problemet med klusterbildning är emellertid notoriskt halt [46] och kan inte lösas universellt [47]. I grund och botten, vilken klusterbildning som är optimal beror på dess efterföljande användning, och våra teoretiska resultat här visar att liknande begränsningar håller för samhällsdetektion [48]. Men som med klusterbildning, trots bristen på en universell lösning, samhällsdetektion är fortfarande ett användbart och kraftfullt verktyg i analysen av komplexa nätverk. Det finns ingen allmänt accepterad definition av samhällsstrukturen, och det bör det inte heller finnas. Nätverken representerar ett brett spektrum av komplexa system, från biologiska till sociala till artificiella system, och deras storskaliga struktur kan genereras av fundamentalt olika processer. Goda community detektionsmetoder som SBM kan vara kraftfulla undersökande verktyg, kunna avslöja en mängd olika sådana mönster i verkliga nätverk. Men, som vi har visat här, det finns ingen gratis lunch i samhället upptäckt. I stället måste algoritmiska förutfattade meningar som förbättrar prestandan på en klass av nätverk minska prestandan på andra. Detta är en naturlig avsättning, och föreslår att bra gemenskap detektionsalgoritmer kommer i två smaker: allmänna algoritmer som utför ganska bra på en mängd olika uppgifter och ingångar, och specialiserade algoritmer som utför mycket bra på en mer smal uppsättning uppgifter, överträffar någon allmän algoritm, men som presterar sämre när tillämpas utanför deras föredragna domän [en insikt förebådas i tidigare arbete [49]]. I vissa fall kan det vara fördelaktigt att använda en uppsättning noggrant utvalda metadata och en smal uppsättning motsvarande nätverk för att träna specialiserade algoritmer. Historiskt sett har de flesta arbeten med samhällsdetektionsalgoritmer fokuserat på att utveckla allmänna strategier. En djupare granskning av hur utgångarna för gemenskapens detektionsalgoritmer därefter kommer att användas, t.ex. för att testa vetenskapliga hypoteser, förutsäga saknade uppgifter eller helt enkelt grovkorniga nätverket, kan sprida nytt ljus över hur man utformar bättre algoritmer för dessa specifika uppgifter. En viktig riktning för det framtida arbetet är således att bättre förstå både dessa avräkningar och de fel som kan förekomma i domänagnostiska tillämpningar [50, 51]. Ett kompletterande tillvägagångssätt är att införliva metadata i själva inferensprocessen, vilket kan hjälpa till att vägleda en metod för att producera mer användbara resultat. Den neoSBM som introduceras här är en sådan metod. Andra inkluderar metoder som använder metadata som en föregångare för samhällsuppdrag [21] och identifierar relevanta samhällen för att förutsäga saknade nätverk eller metadatainformation [33, 34, 52]. Men det finns potential att gå 9 längre än dessa domänagnostiska metoder kan ta oss. Verktyg som innehåller korrekt domänspecifik kunskap om de system de representerar kommer att ge den bästa linsen för att avslöja mönster bortom vad som redan är känt och i slutändan leda till viktiga vetenskapliga genombrott. Genom att noggrant undersöka dessa relationer kan vi gå förbi den falska uppfattningen om metadata som grundsanning, och istället avslöja de särskilda organisationsprinciper som ligger till grund för verkliga nätverk och deras metadata. TILLÄMPNINGEN AV KONKURRENSREGLERNA I EUROPEISKA UNIONEN
Slutligen, arbete av Peel et al. gjorde viktiga bidrag i 1) upprätta ett statistiskt test för att avgöra om attribut faktiskt korrelerar med gemenskapens struktur och 2) utveckla en SBM med flexibilitet i hur starkt att par attribut och gemenskap medlemskap i den stokastiska blockmodellen inference problem REF.
The ground truth about metadata and community detection in networks
{'venue': 'Science Advances 3(5) e1602548, 2017', 'journal': None, 'mag_field_of_study': ['Medicine', 'Computer Science', 'Physics', 'Mathematics']}