Vi presenterar en asymptotiskt exakt analys av problemet med att upptäcka samhällen i glesa slumpmässiga nätverk. Våra resultat är också tillämpliga på detektion av funktionella moduler, partitioner och färger i bullriga planterade modeller. Med hjälp av en analys av hålrumsmetoden presenterar vi en fasövergång från en region där den ursprungliga grupptilldelningen är omöjlig att upptäcka till en där det är möjligt att upptäcka. I vissa fall delas den detekterbara regionen upp i en algoritmiskt hård region och en enkel. Vår strategi översätts naturligt till en praktisk algoritm för att upptäcka moduler i glesa nätverk, och lära sig parametrarna i den underliggande modellen. PACS nummer: 64.60.aq,89.75.Hc,75.10.Hk I många nätverk, allt från online-samhällen till livsmedelsnät, metaboliska nätverk och genetiska regulatoriska nätverk, finns det samhällen eller moduler som spelar olika funktionella roller. Ett grundläggande problem är att upptäcka dessa samhällen och förstå vilken roll de spelar i nätverkets struktur och dynamik. I sociala nätverk är dessa samhällen ofta olika, vilket innebär att det finns en högre täthet av förbindelser inom samhällen än mellan dem, och många metoder för att upptäcka dessa samhällen har föreslagits (se t.ex. [1]) Stryk det som inte är tillämpligt. I andra nätverk kan dock dessa moduler bestå av noder med få anslutningar till varandra, men som ansluter till resten av nätverket på liknande sätt. I detta brev analyserar vi en slumpmässig generativ modell för glesa modulära nätverk, känd som den stokastiska blockmodellen. Det ger en användbar lekplats för teoretiska idéer och analys av algoritmer, och är en populär modell för funktionella moduler i verkliga nätverk. Med hjälp av den hålighetsmetod som utvecklats i fysiken av oordnade system [2, 3] analyserar vi exakt detekterbarheten av dessa moduler i gränsen för stora glesa nätverk. Som en funktion av parametrarna beräknar vi fasdiagrammet och lokaliserar tillhörande fasövergångar. Vi skiljer mellan en detekterbar fas där det är möjligt att lära sig modellens parametrar och gruppuppdragen av noderna, och en icke-intuitiv odetekterbar fas där lärande är omöjligt eftersom nätverkets topologi inte behåller tillräckligt med information om de ursprungliga gruppmedlemskapen. Förekomsten av en fas där en viss algoritmklass inte kan upptäcka samhällen förutsagdes tidigare [4], men dess placering var bara ungefärlig (och dess storlek överskattades). Till skillnad från tidigare arbeten som bygger på att hitta ett marktillstånd, d.v.s. att minimera en kostnadsfunktion i samband med ett gruppuppdrag [4, 5], är vår analys mer allmän eftersom den bygger på egenskaperna hos hela Boltzmann-distributionen av gruppuppdrag. Vi presenterar också en övergång från en algoritmiskt "hård" fas, där vi tror, ingen polynomal algoritm för att lära grupper och parametrar finns, till en "lätt" fas där polynomalgoritmer finns. I den senare fasen visar vi att Belief Propagation (BP) [6] arbetar på stora nätverk i huvudsak linjär tid som en funktion av deras storlek. BP föreslogs tidigare för detektering av samhället [7], men utan förmåga att lära sig parametrarna för den underliggande modellen. Vårt tillvägagångssätt ger också ett naturligt mått på betydelsen av modulerna i nätverket, eftersom det beräknar den marginella sannolikheten att en given nod tillhör en viss grupp. Om nätverket inte innehåller några moduler, kan vår metod på ett korrekt sätt sluta sig till detta faktum genom att göra dessa marginaler enhetliga. Detta är en aspekt som saknas i det stora flertalet av de nuvarande tillvägagångssätten för att upptäcka samhället. Vår teoretiska förståelse och algoritm är också tillämpliga på verkliga nätverk, som vi diskuterar kort i slutet av denna uppsats (och i detalj någon annanstans). Dessutom är vårt tillvägagångssätt inte begränsat av detaljerna i den generativa modellen, och är lätt generaliserat till mer utvecklade modeller (t.ex. [8]). Stochastic block modeller. Vi anser nätverk av N noder. Varje nod i har en dold etikett t i... {1,.., q}, ange vilken av q-grupper det är medlem i. Dessa etiketter väljs självständigt, där n a är sannolikheten för att en given nod har en etikett som är en... {1,..., q} (normaliserad så att q a=1 n a = 1). Om N a är antalet noder i varje grupp, har vi n a = lim N →∞ N a /N. När grupptilldelningen är vald genererar modellen en graf G enligt följande. För varje par av noder i, j med i < j, vi sätter en kant mellan i och j oberoende med sannolikhet p ti,tj, lämnar dem osammanhängande med sannolikhet 1 − p ti,tj. Vi kallar p ab affinitetsmatrisen. Eftersom vi är intresserade av det glesa fallet där p ab = O(1/N ), kommer vi att använda den omskalade affinitetsmatrisen c ab = N p ab och anta att c ab = O(1) i gränsen N → ∞.
SBM-modeller har sett ett på nytt intresse nyligen på grund av antagandet av REF ) att hypoteser fas övergång för svag återhämtning fall (den som vi är intresserade av detta dokument) och förekomsten av informations-beräkning gapet för fyra samhällen i det symmetriska fallet.
Phase transition in the detection of modules in sparse networks
{'venue': 'Phys. Rev. Lett. 107, 065701 (2011)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science', 'Medicine']}