Vi studerar nätverk som visar community struktur-grupper av noder inom vilka anslutningar är ovanligt täta. Med hjälp av metoder från slumpmässig matristeori, beräknar vi spektra av sådana nätverk i gränsen av stor storlek, och därmed visa förekomsten av en fasövergång i matrismetoder för community detektion, såsom den populära modularitet maximization metod. Övergången skiljer en regim där sådana metoder framgångsrikt upptäcker samhällsstrukturen från en där strukturen är närvarande men inte upptäcks. Genom att jämföra dessa resultat med nya analyser av max-likelihood metoder kan vi visa att spektral modularitet maximization är en optimal detektionsmetod i den meningen att ingen annan metod kommer att lyckas i regimen där modularitetsmetoden misslyckas. Problemet med att upptäcka samhällen i nätverk har fått stor uppmärksamhet under de senaste åren [1, 2]. Samhällen i detta sammanhang är grupper av hörn inom ett nätverk som har en hög densitet inom gruppen anslutningar men en lägre densitet mellan grupper anslutningar. Utmaningen är att hitta sådana grupper exakt och effektivt i ett givet nätverk - förmågan att göra det skulle ha tillämpningar i analysen av observationsdata, nätverksvisualisering, och komplexitet minskning och parallellisering av nätverksproblem. I detta dokument fokuserar vi på matrismetoder för community detektion, som bygger på egenskaperna hos matris representationer av nätverk såsom adjacency-matrisen eller modularitetsmatrisen. Även om betydande insatser har gjorts för att utveckla praktiska algoritmer med hjälp av dessa metoder, har det gjorts mindre arbete med formell granskning av deras egenskaper och konsekvenser för algoritmprestanda. Här ger vi en analys av adjacens och modulära matrisers spektralegenskaper med hjälp av slumpmässiga matrismetoder, och i processen avslöja ett antal resultat av praktisk betydelse. Huvuddelen av dessa är förekomsten av en skarp övergång mellan ett system där spektrumet innehåller tydliga bevis för samhällsstruktur och ett system där det inte innehåller någon. I det tidigare systemet är det möjligt att upptäcka samhället och nuvarande algoritmer bör fungera bra. I det senare systemet måste alla metoder som förlitar sig på spektrumet för att utföra strukturdetektering misslyckas. En liknande fasövergång har nyligen rapporterats i en analys av en annan klass av detektionsmetoder, baserad på Bayesian inference [3]. Genom att jämföra de två analyserna kan vi visa att metoder som modularitetsmaximering är optimala, i den meningen att ingen annan metod kommer att lyckas där de misslyckas. För den formella analysen av gemenskapsstrukturerade nätverk måste vi definiera det eller de nätverk som vi kommer att studera. I detta dokument fokuserar vi på den mest studerade modellen av samhällsstruktur, den stokastiska blockmodellen, även om våra metoder kan tillämpas även på andra modeller. Den stokastiska blockmodellen, i dess enklaste form, delar ett nätverk av n hörn i ett antal q av grupper som betecknas med r = 1........... och sedan placerar oriktade kanter mellan vertex par i, j med oberoende sannolikheter p rs, där r, s är respektive de grupper som hörn i, j tillhör. Med andra ord beror sannolikheten för en kant mellan två hörn i denna modell endast på de grupper i vilka hörnen faller. Om de diagonala elementen i matrisen av sannolikheter p rs är större än de off-diagonala elementen, då nätverket visar klassiska gemenskap struktur med en större densitet av kanter inom grupper än mellan dem. Särskilda fall av den stokastiska blockmodellen används ofta som testbäddar för att bedöma prestandan hos gemenskapens detektionsalgoritmer – särskilt i "fyra grupper" testet [1] och den planterade partition modellen [4]. Låt oss först visa vårt argument för det enklaste möjliga fallet av ett nätverk med q = 2 grupper av lika storlek 1 2 n vardera och bara två olika sannolikheter p i och p ut för anslutningar inom och mellan grupper. Vi fokuserar särskilt på de glesa näten, för vilka den del av de möjliga kanterna som finns i nätet försvinner i gränsen för stora n, som verkar vara representativa för de flesta nät som observerats i den verkliga världen, även om våra resultat i princip även gäller täta nät. Adjacensmatris A för ett oriktat nätverk är n × n symmetrisk matris med element A ij = 1 om hörnen i och j är anslutna med en kant och 0 annars. Om vi genomsnitt adjacency matris över ensemblen av vår stokastiska block modell den resulterande matris A har element lika med p i för hörn i samma grupp och p ut för hörn i olika grupper. Definiera c i = np in och c out = np out, denna matris kan skrivas i form där 1 och u är enheten vektorer 1 = (1, 1, 1,....) / ε n och u = (1, 1,..., −1, −1,. .)/ ‹ n, de ±1 elementen i de senare som anger medlemmarna i de två samhällena. Nu kan den fullständiga adjacensmatrisen skrivas i form A = A + X där matrisen X är avvikelsen
Modularitetsmetodens detekterbarhet studeras i REF när de två delnätverken är av samma storlek och varje nodpar i varje delnätverk är slumpmässigt anslutna med samma sannolikhet för kantanslutning.
Graph spectra and the detectability of community structure in networks
{'venue': 'Phys. Rev. Lett. 108, 188701 (2012)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Medicine']}