Vi undersöker möjligheterna att upptäcka moduler i stora nätverk när antalet moduler inte är känt i förväg. Vi använder den minsta beskrivningslängd (MDL) princip som syftar till att minimera den totala mängden information som krävs för att beskriva nätverket, och undvika övermontering. Enligt detta kriterium får vi allmänna gränser för detekterbarheten av alla föreskrivna blockstruktur, med tanke på antalet noder och kanter i det provade nätverket. Vi får också att det maximala antalet detekterbara block skalor som ‹ N, där N är antalet noder i nätverket, för en fast genomsnittlig grad k. Vi visar också att enkelheten i MDL-metoden ger en effektiv multilevel Monte Carlo inference algoritm med en komplexitet av O(τ N log N ), om antalet block är okänt, och O(τ N ) om det är känt, där τ är blandningstiden i Markov kedjan. Vi illustrerar tillämpningen av metoden på ett stort nätverk av skådespelare och filmer med över 10 6 kanter, och en dissortativ, bipartite block struktur. Upptäckten av moduler - eller samhällen - är ett av de mest intensivt studerade problemen i den senaste litteraturen om nätverkssystem [1, 2]. Användningen av generativa modeller för detta ändamål, såsom familjen stokastiska blockmodeller [3] [4] [5] [6] [7][8][9] [10] [11] [12] [13] [15] [16] [17] [18] [19] [20], har fått allt större uppmärksamhet. Detta tillvägagångssätt skiljer sig drastiskt från de flesta andra metoder som hittills använts inom området (t.ex. modularitetsmaximisering [21]), eftersom det inte bara härrör från första principer, utan också inte är begränsat till rent diverse och oriktade samhällsstrukturer. De flesta slutledningsmetoder som används för att få fram den mest sannolika blockmodellen förutsätter dock att antalet samhällen är känt i förväg [14, 18, [22] [23] [24] [25]. Tyvärr är denna mängd i de flesta praktiska fall helt okänd, och man skulle också vilja dra slutsatsen av uppgifterna. Här utforskar vi ett mycket effektivt sätt att få denna information från data, känd som minsta beskrivning längd princip (MDL) [26, 27], som bygger på att det bästa valet av modell som passar en viss data är den som mest komprimerar det, dvs... minimerar den totala mängden information som krävs för att beskriva den. Detta tillvägagångssätt har införts i uppgiften som blockmodellslutsats i Ref. [28]............................................................... Här generaliserar vi det för att ta emot ett godtyckligt stort antal samhällen, och för att få allmänna gränser för att upptäcka godtyckliga samhällsstrukturer. Vi visar också att, enligt detta kriterium, det maximala antalet detekterbara block skalor som ε N, där N är antalet noder i nätverket. Eftersom MDL-metoden resulterar i en enkel straff på log-likelihood, använder vi den för att genomföra en effektiv multilevel Monte Carlo algoritm med en övergripande komplexitet av O(τ N log N ), där τ är den genomsnittliga blandningstiden för Markov kedjan, som kan användas för att sluta godtyckliga blockstrukturer på mycket stora nätverk. Modellen -Den stokastiska blockmodell ensemble består av grafer med N noder, var och en tillhör en av B block, och antalet kanter mellan noder av block r och s ges av matrisen e rs (eller dubbelt så många om r = s). Den gradkorrigerade varianten [14] innebär vidare att varje nod i har en grad som anges av k i, där uppsättningen {k i } är en ytterligare parameteruppsättning av modellen. Den riktade versionen av båda modellerna är analogt definierad, med e rs blir asymmetrisk, och {k − i} tillsammans med {k + i } fastställande in- och utgrader av noderna, respektive. Dessa ensembler kännetecknas av deras mikrokanoniska entropi S = ln. Där är det totala antalet nätverksrealiseringar [29]. Entropin kan beräknas analytiskt i båda fallen [30], för den traditionella blockmodellensemblen och för den gradkorrigerade varianten, där i båda fallen E = rs e rs /2 är det totala antalet kanter, n r är antalet noder som hör till block r, och N k är det totala antalet noder med grad k, och e r = s e rs är antalet halvkanter incident på block r. Det riktade fallet är analogt [30] (se Kompletterande material för en översikt). Detektionsproblemet består i att erhålla blockpartitionen {b i } som är mest sannolik, när det ges ett omärkt nätverk G, där b i är blocketiketten för node i. Detta görs genom att maximera log-likelihood ln P som nätverket G observeras, med tanke på modellen kompatibel med en vald blockpartition. Eftersom vi har helt enkelt P = 1/ och maximering ln P motsvarar att minimera entropi S t/c, vilket är det språk vi kommer att använda hädanefter. Entropiminimering är väldefinierad, men bara så länge det totala antalet block B är känt i förväg. Annars blir det optimala värdet av St/c en strikt minskande funktion av B. Således, helt enkelt minimera entropi kommer att leda till triviala B = N partition, och blockmatrisen e rs blir helt enkelt adjacency matris. Ett principfast sätt att undvika sådan överutrustning är att beakta den totala mängden information som krävs för att beskriva uppgifterna, vilket inte bara omfattar entropi arXiv:1212.4794v4 [fysik.data-an]
I synnerhet har användningen av MDL för att hitta antalet block undersökts tidigare av Peixoto REF.
Parsimonious module inference in large networks
{'venue': 'Phys. Rev. Lett. 110, 148701 (2013)', 'journal': None, 'mag_field_of_study': ['Physics', 'Mathematics', 'Medicine']}