Gemenskapens upptäckt, uppdelningen av ett nät i täta delnät med endast glesa förbindelser mellan dem, har varit föremål för kraftfulla undersökningar under de senaste åren. Det finns dock en rad kraftfulla och flexibla metoder för att dela upp ett nätverk i ett visst antal samhällen, men det är en öppen fråga hur man ska avgöra exakt hur många samhällen man ska använda. Här beskriver vi ett matematiskt principiellt tillvägagångssätt för att hitta antalet samhällen i ett nätverk med hjälp av en maxlikelihood-metod. Vi demonstrerar detta tillvägagångssätt på en rad verkliga exempel med känd samhällsstruktur, och finner att det är möjligt att bestämma antalet samhällen korrekt i varje fall. Den storskaliga strukturen av empiriskt observerade nätverk, såsom sociala, biologiska och tekniska nätverk, är ofta komplex och svårbegriplig [1]. Detektion i gemenskapen, uppdelningen av knutpunkterna i ett nätverk i tätt sammankopplade grupper med endast glesa förbindelser mellan grupper, är ett av de mest effektiva verktyg som står till vårt förfogande för att minska denna komplexitet till en nivå där nättopologin lättare kan förstås och tolkas. Utvecklingen av algoritmiska metoder för gemenskapsdetektering har varit föremål för en stor del av den senaste forskningen [2] [3] [4], som ett resultat av detta har vi nu ett antal effektiva och känsliga detektionsmetoder som kan hitta meningsfulla samhällen i verkliga miljöer [4] [5] [6] [7] [7] [8] [9] [10] [11]. En grundläggande begränsning av de flesta av dessa metoder är dock att de endast delar upp nätverk i ett fast antal grupper, så att man i förväg måste veta hur många grupper man letar efter. Normalt har man inte denna information, vilket avsevärt minskar nyttan av samhällsdetektion som ett analytiskt verktyg. I detta dokument presenterar vi en rigorös, första principlösning på detta problem i form av en algoritm som, när den tillämpas på ett visst nätverk, returnerar det antal samhällen som nätverket innehåller. Algoritmen använder allmänt accepterade metoder för statistisk slutledning i kombination med ett numeriskt tillvägagångssätt som skalar effektivt till stora nätverk. Det har funnits ett antal tidigare tillvägagångssätt som föreslagits för detta problem, bland vilka kanske den mest kända är metoden för modularitet maximisering [5, 12], vilket är en metod både för att välja antalet samhällen och för att utföra gemenskap uppdelningen själv. Denna metod används t.ex. i den allmänt använda Louvain-algoritmen [8], men den lider av att bara vara heuritiskt motiverad och det finns fall där det är känt att ge felaktiga resultat [13, 14]. Mer rigorösa metoder inkluderar minsta längdmetoder [15] och olika approximationer till integrerade sannolikheter, inklusive varianter av Bayesian informationskriteriet [16, 17], Laplace-stil approximationer [18], och variations approximationer [19]. Kanske mest likt vårt arbete är det av [20] som använder en exakt integral av sannolikheten som vi gör, men gör approximationer på annat håll i beräkningen och även antar en Poisson grad distribution för det observerade nätverket, vilket gör det olämpligt för de flesta verkliga nätverksdata. Vår strategi, liksom mycket av det senaste arbetet på detta område, bygger på metoder för statistiska slutsatser. I dessa metoder definierar man en modell av ett nätverk med samhällsstruktur, sedan passar den modellen till observerade nätverksdata. Parametrarna för passformen berättar om samhällsstrukturen på ungefär samma sätt som passformen av en rak linje genom en uppsättning datapunkter kan berätta om deras lutning. Den modell som oftast används i detta sammanhang är den stokastiska blockmodellen [11, 21, 22]. I denna modell anger man antalet noder n i nätverket tillsammans med antalet k samhällen eller grupper, sedan tilldelar man varje nod i tur och ordning till en av grupperna slumpmässigt, med sannolikhet γ r för tilldelning till gemenskap r (där r löper från 1 till k). Observera att vi måste ha k r=1 γ r = 1 för konsekvens. När alla noder har tilldelats en grupp, en platser oriktade kanter oberoende slumpmässigt mellan par av olika noder med sannolikheter rs, där r och s är de grupper som noderna hör till. Om de diagonala parametrarna är större än de odiagonala, producerar detta ett nätverk med traditionella "assortativa" communitystruktur-grupper av noder med tätare i grupp anslutningar än mellan grupper en-även om andra val är möjliga också. I praktiken är denna modell ofta studeras i en något annorlunda formulering där man placerar inte bara en enda kant mellan varje par av noder i, j men en Poisson distribuerat nummer med genomsnittliga rs, eller hälften det antalet när i = j [11]. I denna variant av modellen kan det genererade nätverket innehålla både flerkants- och selfedges, vilket på sätt och vis är orealistiskt och mest verkliga nätverk inte innehåller någotdera. Men i typiska situationer kantsannolikheterna är så små att både flerkanter och självkanter förekommer med mycket låg frekvens, och modellen är praktiskt taget identisk med den första (Bernoulli) formulering som ges ovan. Samtidigt är Poissons formulering signifikant.
Paper REF använder också gradkorrigerad stokastisk blockmodell för att passa nätverket och betraktar antalet samhällen och samhällsuppdrag som variabler på samma gång.
Estimating the number of communities in a network
{'venue': 'Phys. Rev. Lett. 117, 078301 (2016)', 'journal': None, 'mag_field_of_study': ['Physics', 'Medicine', 'Computer Science']}